#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
const int maxn=(1e5)+10;
int n,m; vector<int> bk[maxn];
int out[maxn],q[maxn],hd,tl;
bool del[maxn];
vector<int> ans,vec,res;
vector<pair<int,int> > g[maxn];
int to[maxn];
int d[maxn],t1,e[maxn],t2;
int pos[maxn],vis[maxn],To[maxn];
int D[maxn],E[maxn];
int at[maxn*2];
variant<bool,vector<int> > find_journey(int _n,int _m,vector<int> U,vector<int> V) {
n=_n,m=_m;
for (int i=0;i<m;i++) bk[V[i]].push_back(U[i]),g[U[i]].push_back(MP(V[i],i)),out[U[i]]++;
int x=0;
for (int i=0;i<n;i++) if (!out[i]) q[++tl]=i,del[i]=1; hd=1;
while (hd<=tl||out[x]==1) {
while (hd<=tl) {
int x=q[hd]; hd++;
for (int &y : bk[x]) { out[y]--; if (!out[y]) q[++tl]=y,del[y]=1; }
}
while (out[x]==1) {
del[x]=1;
for (int &y : bk[x]) { out[y]--; if (!out[y]&&!del[y]) q[++tl]=y,del[y]=1; }
bool fd=0;
for (auto [y,id] : g[x]) if (!del[y]) { fd=1; vec.push_back(id); x=y; break; }
// printf("x=%d\n",x);
if (!fd) return false;
}
// printf("x=%d\n",x);
}
if (out[x]<2) return false;
for (int i=0;i<n;i++) if (!del[i]) {
for (auto [j,id] : g[i]) if (!del[j]) to[i]=j,To[i]=id;
}
int a=-1,b=-1;
for (auto [y,id] : g[x]) if (!del[y]) {
if (a==-1) a=y,D[1]=id; else b=y,E[1]=id;
}
// cerr<<x<<" "<<a<<" "<<b<<endl;
int l,r;
int y=a; vis[x]=1; d[t1=1]=x;
while (!vis[y]) vis[y]=1,d[++t1]=y,D[t1]=To[y],y=to[y];
for (int i=1;i<=t1;i++) if (y==d[i]) l=i;
memset(vis,0,sizeof(vis));
y=b; vis[x]=1; e[t2=1]=x;
while (!vis[y]) vis[y]=1,e[++t2]=y,E[t2]=To[y],y=to[y];
for (int i=1;i<=t2;i++) if (y==e[i]) r=i;
for (int i=1;i<=t1;i++) pos[d[i]]=i;
int fd=0;
for (int i=2;i<=t2;i++) if (pos[e[i]]) { fd=i; break; }
//printf("fd=%d\n",fd);
//for (int i=1;i<=t1;i++) printf("%d ",d[i]); puts("");
//for (int i=1;i<=t2;i++) printf("%d ",e[i]); puts("");
//printf("l=%d,fd=%d\n",l,fd);
//puts("OK");
if (fd) {
if (pos[e[fd]]<l) {
for (int i=1;i<=t1;i++) ans.push_back(D[i]);
for (int i=l-1;i>=1;i--) ans.push_back(D[i]);
for (int i=1;i<fd;i++) ans.push_back(E[i]);
for (int i=pos[e[fd]];i<l;i++) ans.push_back(D[i]);
for (int i=t1;i>=pos[e[fd]];i--) ans.push_back(D[i]);
for (int i=fd-1;i>=1;i--) ans.push_back(E[i]);
} else {
for (int i=1;i<=t1;i++) ans.push_back(D[i]);
for (int i=l-1;i>=1;i--) ans.push_back(D[i]);
for (int i=1;i<fd;i++) ans.push_back(E[i]);
for (int i=pos[e[fd]]-1;i>=l;i--) ans.push_back(D[i]);
for (int i=t1;i>=pos[e[fd]];i--) ans.push_back(D[i]);
for (int i=fd-1;i>=1;i--) ans.push_back(E[i]);
}
} else {
for (int i=1;i<=t1;i++) ans.push_back(D[i]);
for (int i=l-1;i>=1;i--) ans.push_back(D[i]);
for (int i=1;i<=t2;i++) ans.push_back(E[i]);
for (int i=r-1;i>=1;i--) ans.push_back(E[i]);
for (int i=1;i<l;i++) ans.push_back(D[i]);
for (int i=t1;i>=1;i--) ans.push_back(D[i]);
for (int i=1;i<r;i++) ans.push_back(E[i]);
for (int i=t2;i>=1;i--) ans.push_back(E[i]);
}
for (int &x : vec) res.push_back(x);
for (int &x : ans) res.push_back(x);
reverse(vec.begin(),vec.end());
for (int &x : vec) res.push_back(x);
/* for (int &x : res) printf("%d ",x); puts("");
int now=0;
for (int &x : res) {
printf("%d %d %d\n",x,U[x],V[x]);
if (at[x]) assert(now==V[x]); else assert(now==U[x]);
at[x]^=1,now=(V[x]^U[x]^now);
}
assert(now==0);
for (int i=0;i<m;i++) assert(!at[i]);*/
return res;
}
