#include<bits/stdc++.h>
#include "islands.h"
#include <variant>
using namespace std;
vector<int>D[200009];
vector<int>Num[200009];
vector<int>T[200009];
vector<int>Num2[200009];
int n,m;
bool usu[200009];
int stopien[200009];
bool zaj[200009];
int Last[200009],LastNum[200009];
vector<int>A,U;
void UsuVert(int v)
{
usu[v]=1;
for(int som : T[v])
{
stopien[som]--;
if(usu[som]==0&&stopien[som]==0){U.push_back(som);}
}
}
void VectorAdd(vector<int>&Odp,const vector<int>&Dod, bool CzyRevers=0)
{
if(CzyRevers==0)
{
for(int u : Dod)
{
Odp.push_back(u);
}
}
else
{
for(int i=(int)Dod.size()-1;i>=0;i--)
{
Odp.push_back(Dod[i]);
}
}
}
variant<bool, vector<int>> find_journey(
int N, int M, vector<int> E1, vector<int> E2)
{
n=N;
m=M;
for(int i=0;i<m;i++)
{
stopien[E1[i]]++;
D[E1[i]].push_back(E2[i]);
Num[E1[i]].push_back(i);
T[E2[i]].push_back(E1[i]);
Num2[E2[i]].push_back(i);
}
for(int i=0;i<n;i++)
{
if(stopien[i]==0)
{
U.push_back(i);
}
}
int start=0;
while(true)
{
if((int)U.size()>0)
{
const int u=U.back();
U.pop_back();
UsuVert(u);
}
else if(stopien[start]==1)
{
int som=-1,ind=-1;
for(int i=0;i<(int)D[start].size();i++)
{
som=D[start][i];
ind=Num[start][i];
if(usu[som]==0){break;}
}
UsuVert(start);
A.push_back(ind);
start=som;
}
else{break;}
}
if(usu[start]){return false;}
memset(Last,-1,sizeof(Last));
memset(LastNum,-1,sizeof(LastNum));
vector<int>V1,K1,Droga1,Cykl1;
vector<int>V2,K2,Droga2,Cykl2;
int v;
v=start;
int casee=-1;
while(true)
{
int som=-1,ind=-1;
for(int i=0;i<(int)D[v].size();i++)
{
som=D[v][i];
ind=Num[v][i];
if(usu[som]==0){break;}
}
zaj[v]=1;
Last[som]=v;
LastNum[som]=ind;
V1.push_back(v);
K1.push_back(ind);
if(zaj[som])
{
while(true)
{
bool czyBreak=0;
if(V1.back()==som){czyBreak=1;}
Cykl1.push_back(K1.back());
V1.pop_back();
K1.pop_back();
if(czyBreak){break;}
}
reverse(Cykl1.begin(),Cykl1.end());
Droga1=K1;
break;
}
v=som;
}
v=start;
while(true)
{
int som=-1,ind=-1;
for(int i=D[v].size()-1;i>=0;i--)
{
som=D[v][i];
ind=Num[v][i];
if(usu[som]==0){break;}
}
zaj[v]=1;
V2.push_back(v);
K2.push_back(ind);
if(zaj[som])
{
if(Last[som]==-1)
{
while(true)
{
bool czyBreak=0;
if(V2.back()==som){czyBreak=1;}
Cykl2.push_back(K2.back());
V2.pop_back();
K2.pop_back();
if(czyBreak){break;}
}
reverse(Cykl2.begin(),Cykl2.end());
Droga2=K2;
casee=1;
}
else
{
Droga2=K2;
v=som;
while(true)
{
Cykl2.push_back(LastNum[v]);
v=Last[v];
if(v==som){break;}
}
reverse(Cykl2.begin(),Cykl2.end());
casee=2;
}
break;
}
v=som;
}
vector<int>Odp;
VectorAdd(Odp,A);
if(casee==1)
{
VectorAdd(Odp,K1);
VectorAdd(Odp,Cykl1);
VectorAdd(Odp,K1,1);
VectorAdd(Odp,K2);
VectorAdd(Odp,Cykl2);
VectorAdd(Odp,K2,1);
VectorAdd(Odp,K1);
VectorAdd(Odp,Cykl1,1);
VectorAdd(Odp,K1,1);
VectorAdd(Odp,K2);
VectorAdd(Odp,Cykl2,1);
VectorAdd(Odp,K2,1);
}
else if(casee==2)
{
VectorAdd(Odp,K1);
VectorAdd(Odp,Cykl1);
VectorAdd(Odp,K1,1);
VectorAdd(Odp,K2);
VectorAdd(Odp,Cykl2,1);
VectorAdd(Odp,K2,1);
}
VectorAdd(Odp,A,1);
return Odp;
}
