#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 spojna[200009];
vector<int>V[200009];
vector<pair<int,int>>Ziomek[200009];
bool zaj[200009];
bool CzyGit[200009];
int JakiTyp[200009][2];
pair<int,int>Last[200009][2];
int LastNum[200009][2];
int Last2[200009],Last2Num[200009];
bool CzyCykl[200009];
vector<int>U;
int h=0,n,m;
void DFS(int v)
{
if(zaj[v]){return;}
zaj[v]=1;
for(int som : D[v])
{
DFS(som);
}
U.push_back(v);
}
void DFS2(int v)
{
if(spojna[v]!=0){return;}
spojna[v]=h;
V[h].push_back(v);
for(int som : T[v])
{
DFS2(som);
}
}
void DFS3(int v, int u)
{
for(int i=0;i<(int)D[v].size();i++)
{
const int som=D[v][i];
const int ind=Num[v][i];
int z=JakiTyp[v][u];
if(v==0){z=ind;}
if(JakiTyp[som][0]==-1)
{
JakiTyp[som][0]=z;
Last[som][0]={v,u};
LastNum[som][0]=ind;
DFS3(som,0);
}
else if(JakiTyp[som][1]==-1&&JakiTyp[som][0]!=z)
{
JakiTyp[som][1]=z;
Last[som][1]={v,u};
LastNum[som][1]=ind;
DFS3(som,1);
}
}
}
void DFS4(int v)
{
for(int i=0;i<(int)T[v].size();i++)
{
const int som=T[v][i];
const int ind=Num2[v][i];
if(Last2[som]!=-1||spojna[v]!=spojna[som]){continue;}
Last2[som]=v;
Last2Num[som]=ind;
DFS4(som);
}
}
void SSS()
{
for(int i=0;i<n;i++)
{
DFS(i);
}
reverse(U.begin(),U.end());
for(int u : U)
{
if(spojna[u]==0)
{
h++;
DFS2(u);
}
}
}
void VectorAdd(vector<int>&A, const vector<int>&B)
{
for(int u : B)
{
A.push_back(u);
}
}
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++)
{
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);
}
SSS();
for(int i=0;i<n;i++)
{
int ile=0;
for(int som : D[i])
{
if(spojna[i]!=spojna[som]){continue;}
ile++;
}
CzyGit[i]=(ile>=2);
}
for(int i=0;i<n;i++)
{
Last[i][0]={-1,-1};
Last[i][1]={-1,-1};
}
memset(Last2,-1,sizeof(Last2));
memset(JakiTyp,-1,sizeof(JakiTyp));
JakiTyp[0][0]=0;
JakiTyp[0][1]=0;
DFS3(0,0);
JakiTyp[0][1]=-1;
for(int i=0;i<n;i++)
{
for(int j=0;j<2;j++)
{
if(JakiTyp[i][j]!=-1&&spojna[i]!=spojna[Last[i][j].first]&&(int)Ziomek[spojna[i]].size()<2)
{
Ziomek[spojna[i]].push_back({i,j});
}
}
}
vector<int>Odp;
for(int i=1;i<=h;i++)
{
int a,b,u1,u2,v,u;
if((int)Ziomek[i].size()==0){continue;}
vector<int>A,B,Cykl1,Cykl2,Droga;
if((int)Ziomek[i].size()==1)
{
if(CzyGit[Ziomek[i][0].first]==0){continue;}
v=Ziomek[i][0].first;
u1=Ziomek[i][0].second;
DFS4(v);
int v2=v;
while(true)
{
CzyCykl[v2]=1;
Cykl1.push_back(Last2Num[v2]);
v2=Last2[v2];
if(v==v2){break;}
}
for(int i=0;i<(int)D[v].size();i++)
{
const int som=D[v][i];
const int ind=Num[v][i];
if(spojna[v]!=spojna[som]||Last2Num[v]==ind){continue;}
Droga.push_back(ind);
v2=som;
break;
}
int spotkanie=-1;
while(true)
{
if(spotkanie==v2){break;}
if(spotkanie==-1&&CzyCykl[v2]){spotkanie=v2;}
if(spotkanie==-1){Droga.push_back(Last2Num[v2]);}
else{Cykl2.push_back(Last2Num[v2]);}
v2=Last2[v2];
}
reverse(Cykl2.begin(),Cykl2.end());
v2=v;
while(v2!=0)
{
A.push_back(LastNum[v2][u]);
tie(v2,u)=Last[v2][u];
}
reverse(A.begin(),A.end());
VectorAdd(Odp,A);
VectorAdd(Odp,Cykl1);
VectorAdd(Odp,Droga);
VectorAdd(Odp,Cykl2);
reverse(Droga.begin(),Droga.end());
VectorAdd(Odp,Droga);
reverse(A.begin(),A.end());
VectorAdd(Odp,A);
return Odp;
}
else if(V[i].size()>1)
{
a=Ziomek[i][0].first;u1=Ziomek[i][0].second;
b=Ziomek[i][1].first;u2=Ziomek[i][1].second;
DFS4(a);
v=a;
while(true)
{
CzyCykl[v]=1;
Cykl1.push_back(Last2Num[v]);
v=Last2[v];
if(v==a){break;}
}
v=b;
int spotkanie=-1;
while(true)
{
if(v==spotkanie){break;}
if(spotkanie==-1&&CzyCykl[v]){spotkanie=v;}
if(spotkanie==-1){Droga.push_back(Last2Num[v]);}
else{Cykl2.push_back(Last2Num[v]);}
v=Last2[v];
}
reverse(Cykl2.begin(),Cykl2.end());
v=a;
u=u1;
while(v!=0)
{
A.push_back(LastNum[v][u]);
tie(v,u)=Last[v][u];
}
reverse(A.begin(),A.end());
v=b;
u=u2;
while(v!=0)
{
B.push_back(LastNum[v][u]);
tie(v,u)=Last[v][u];
}
reverse(B.begin(),B.end());
VectorAdd(Odp,A);
VectorAdd(Odp,Cykl1);
reverse(A.begin(),A.end());
VectorAdd(Odp,A);
VectorAdd(Odp,B);
VectorAdd(Odp,Droga);
VectorAdd(Odp,Cykl2);
reverse(Droga.begin(),Droga.end());
VectorAdd(Odp,Droga);
reverse(B.begin(),B.end());
VectorAdd(Odp,B);
return Odp;
}
}
return false;
}
