#include "islands.h"
#include<bits/stdc++.h>
#include <variant>
#include <vector>
using namespace std;
#define sz(a) (int)(a.size())
#define pb push_back
#define fi first
#define se second
typedef pair<int,int> pii;
const int MAXN = 5e5+5;
bool dead[MAXN],mark[MAXN];
int outdeg[MAXN],par[MAXN],vis[MAXN];
vector<pii>g[MAXN],gr[MAXN];
vector<int>path,cycle;
void rev(vector<int>&a){reverse(a.begin(),a.end());}
bool dfs(int v,int root){
vis[v] = 1;
for(pii z:g[v]){
int x = z.fi;
if(mark[x])continue;
if(vis[x]){
int cur = v;
while(cur != x){
cycle.pb(cur);
cur = par[cur];
}
cycle.pb(x);
rev(cycle);
if(cur != root){
while(cur != root){
path.pb(cur);
cur = par[cur];
}
}
path.pb(root);
rev(path);
return 1;
}else{
par[x] = v;
if(dfs(x,root))return 1;
}
}
return 0;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V){
for(int i=0;i<M;i++){
gr[V[i]].pb({U[i],i});
g[U[i]].pb({V[i],i});
outdeg[U[i]]++;
}
vector<int>del;
for(int i=0;i<N;i++){
//cout<<i<<" "<<sz(g[i])<<'\n';
if(g[i].empty()){
del.pb(i);
mark[i] = 1;
}
}
int cur = 0;
vector<int>ans;
while(true){
if(mark[cur])return false;
while(!del.empty()){
vector<int>tmp;
for(int u:del){
//cout<<u<<'\n';
for(pii x:gr[u]){
int v = x.fi;
outdeg[v]--;
dead[x.se] = 1;
if(!outdeg[v] && !mark[v]){
tmp.pb(v);
mark[v] = 1;
}
}
}
del = tmp;
}
if(mark[cur])return false;
int cnt = 0;
for(pii x:g[cur]){
if(!mark[x.fi])cnt++;
}
if(cnt > 1)break;
if(cnt == 0)return false;
for(pii x:g[cur]){
if(!mark[x.fi]){
del.pb(cur);
mark[cur] = 1;
ans.pb(x.se);
cur = x.fi;
break;
}
}
}
int fix = 0;
vector<vector<int>>p,c;
for(pii x:g[cur]){
if(mark[x.fi])continue;
if(sz(p)>1)break;
path.clear();
cycle.clear();
for(int i=0;i<N;i++)vis[i] = par[i] = 0;
fix = x.se;
vis[cur] = 1;
par[x.fi] = cur;
dfs(x.fi,cur);
p.pb(path);
c.pb(cycle);
}
bool case2 = 0;
vector<int>tmp = ans;
vector<int>p1,p2,c1,c2;
vector<bool>incyc(N,0);
for(int i=0;i+1<sz(p[0]);i++){
int v = p[0][i];
int u = p[0][i+1];
for(pii x:g[v]){
if(x.fi == u){
p1.pb(x.se);
break;
}
}
}
for(int i=0;i<sz(c[0]);i++){
int v = c[0][i];
int u = c[0][(i+1)%sz(c[0])];
incyc[v] = 1;
for(pii x:g[v]){
if(x.fi == u){
c1.pb(x.se);
break;
}
}
}
int tail = 0;
for(int i=0;i+1<sz(p[1]);i++){
int v = p[1][i];
int u = p[1][i+1];
for(pii x:g[v]){
if(x.fi == u){
if(i)p2.pb(x.se);
else p2.pb(fix);
break;
}
}
if(incyc[u]){
tail = u;
case2 = 1;
break;
}
}
if(!case2){
for(int i=0;i<sz(c[1]);i++){
int v = c[1][i];
int u = c[1][(i+1)%sz(c[1])];
for(pii x:g[v]){
if(x.fi == u){
c2.pb(x.se);
break;
}
}
if(incyc[u]){
tail = u;
case2 = 1;
break;
}
}
}
//////
if(case2){
for(int x:p1)ans.pb(x);
for(int x:c1)ans.pb(x);
rev(p1);
for(int x:p1)ans.pb(x);
for(int x:c2)p2.pb(x);
for(int x:p2)ans.pb(x);
int shft = 0;
for(int i=0;i<sz(c[0]);i++){
if(c[0][(i+1)%sz(c[0])]==tail){
shft = i;
break;
}
}
int m = sz(c1);
for(int i=0;i<sz(c1);i++)ans.pb(c1[(shft+m-i)%m]);
rev(p2);
for(int x:p2)ans.pb(x);
}else{
for(int x:p1)ans.pb(x);
for(int x:c1)ans.pb(x);
rev(p1);
for(int x:p1)ans.pb(x);
rev(p1);rev(c1);
for(int x:p2)ans.pb(x);
for(int x:c2)ans.pb(x);
rev(p2);
for(int x:p2)ans.pb(x);
rev(p2);rev(c2);
for(int x:p1)ans.pb(x);
for(int x:c1)ans.pb(x);
rev(p1);
for(int x:p1)ans.pb(x);
rev(p1);
for(int x:p2)ans.pb(x);
for(int x:c2)ans.pb(x);
rev(p2);
for(int x:p2)ans.pb(x);
rev(p2);
}
rev(tmp);
for(int x:tmp)ans.pb(x);
return ans;
}
