#include "islands.h"
#include<bits/stdc++.h>
using namespace std;
#define N 100009
#define M 200009
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
int n,m;pair<int,int> e[M];
namespace full{
	int hd[N],hr[N],tot,deg[N],p0[N],p1[N],p2[N],s1,s2,e0,e1,e2;
	bool dl[M<<1],v1[N],v2[N];
	struct edge{int t,nxt;} es[M<<1];
	void adde(int u,int v){es[++tot]=(edge){v,hd[u]},hd[u]=tot;}
	void addr(int u,int v){es[++tot]=(edge){v,hr[u]},hr[u]=tot;}
	vector<int> ans;queue<int> q;
	void upd(int u){int&i=hd[u];while(dl[i])i=es[i].nxt;}
	void topsort(){
		while(q.size()){//反图
			int u=q.front();q.pop();
			for(int i=hr[u];i;i=es[i].nxt)if(!dl[i]){
				dl[i]=dl[i^1]=1;int v=es[i].t;--deg[v];if(!deg[v])q.push(v);
			}
		}
	}
	variant<bool,vector<int>> solve(){
		tot=1;rep(i,1,m){adde(e[i].fi,e[i].se);addr(e[i].se,e[i].fi);++deg[e[i].fi];}
		rep(i,1,n)if(!deg[i])q.push(i);topsort();
		int s=0;if(!deg[s])return false;
		while(deg[s]==1){
			for(int i=hr[s];i;i=es[i].nxt)if(!dl[i]){dl[i]=dl[i^1]=1;--deg[es[i].t];if(!deg[es[i].t])q.push(es[i].t);}topsort();
			upd(s);int i=hd[s];hd[s]=es[i].nxt;p0[++e0]=i;s=es[i].t;
		}
		if(!deg[s])return false;
		rep(i,0,n-1)upd(i);
		for(int u=s;!v1[u];u=es[hd[u]].t)v1[u]=1,p1[++e1]=hd[u];///p1
		for(s1=1;es[p1[s1]].t!=es[p1[e1]].t;++s1);if(s1==e1)s1=0;
		hd[s]=es[hd[s]].nxt;upd(s);v1[s]=0;
		bool flag=0;
		for(int u=s;;u=es[hd[u]].t){///p2
			if(v1[u]){flag=1;break;}else if(v2[u])break;
			v2[u]=1;p2[++e2]=hd[u];
		}
		rep(i,1,e0)ans.pb(p0[i]);
		rep(i,1,e1)ans.pb(p1[i]);per(i,s1,1)ans.pb(p1[i]);
		if(flag){
			for(s2=1;es[p1[s2]].t!=es[p2[e2]].t;++s2);
			rep(i,1,e2)ans.pb(p2[i]);
			if(s2<=s1){
				rep(i,s2+1,s1)ans.pb(p1[i]);per(i,e1,s2+1)ans.pb(p1[i]);
			}else{
				per(i,s2,s1+1)ans.pb(p1[i]);per(i,e1,s2+1)ans.pb(p1[i]);
			}
			per(i,e2,1)ans.pb(p2[i]);
		}else{
			for(s2=1;es[p2[s2]].t!=es[p2[e2]].t;++s2);if(s2==e2)s2=0;
			rep(i,1,e2)ans.pb(p2[i]);per(i,s2,1)ans.pb(p2[i]);
			rep(i,1,s1)ans.pb(p1[i]);per(i,e1,1)ans.pb(p1[i]);
			rep(i,1,s2)ans.pb(p2[i]);per(i,e2,1)ans.pb(p2[i]);
		}per(i,e0,1)ans.pb(p0[i]);
		for(int&i:ans)i=i/2-1;
		return ans;
	}
}
#undef N
#undef M
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V){
	n=N,m=M;rep(i,1,m)e[i]=mp(U[i-1],V[i-1]);
	return full::solve();
}
/////////////////////////TianyiLemon