#include<bits/stdc++.h>
#include"islands.h"
#define pb push_back
#define SZ(x) ((int)x.size())
const int N=100005;typedef std::pair<int,int> pi;
int n,dg[N];std::vector<pi> e[N],r[N];
int _q[N],_l,_r;bool mark[N];
std::vector<int> operator + (const std::vector<int> &a,const std::vector<int> &b){auto c(a);c.insert(c.end(),b.begin(),b.end());return c;}
std::vector<int> rev(std::vector<int> a){std::reverse(a.begin(),a.end());return a;}
void extend(){
	while(_l!=_r+1){
		int x=_q[_l++];mark[x]=1;
		for(auto v:r[x])if(!--dg[v.first])_q[++_r]=v.first;
	}
}
int pre[N],w[N];bool tag[N];std::vector<int> res,cyc;bool flag,loop[N*2];
void dfs(int x,int id){
	if(flag)return;
	tag[x]=1;
	for(auto it:e[x])if(it.second!=id&&!mark[it.first]){
		if(tag[it.first]){
			loop[it.second]=1,cyc.pb(it.second);
			for(int i=x;i!=it.first;i=pre[i])loop[w[i]]=1,cyc.pb(w[i]);
			res.pb(it.second);
			for(int i=x;~i;i=pre[i])if(pre[i]!=-1)res.pb(w[i]);
			std::reverse(res.begin(),res.end());
			for(int i=it.first;~i;i=pre[i])if(pre[i]!=-1)res.pb(w[i]);
			flag=1;return;
		}
		else pre[it.first]=x,w[it.first]=it.second,dfs(it.first,it.second);
		if(flag)return;
	}
}
void dfs2(int x,int id){
	if(flag)return;
	tag[x]=1;
	for(auto it:e[x])if(it.second!=id&&!mark[it.first]){
		if(loop[it.second]){
			auto p=std::find(cyc.begin(),cyc.end(),it.second);
			std::rotate(cyc.begin(),p+1==cyc.end()?cyc.begin():p+1,cyc.end());
			for(int i=x;~i;i=pre[i])if(pre[i]!=-1)res.pb(w[i]);
			res=rev(res)+cyc+res;flag=1;return;
		}
		else if(!tag[it.first])pre[it.first]=x,w[it.first]=it.second,dfs2(it.first,it.second);
		if(flag)return;
	}
}
std::variant<bool,std::vector<int>> find_journey(int n,int m,std::vector<int> U,std::vector<int> V){
	::n=n;for(int i=0;i<m;++i)e[U[i]].pb({V[i],i}),r[V[i]].pb({U[i],i}),++dg[U[i]];
	_l=1,_r=0;for(int i=0;i<n;++i)if(!dg[i])_q[++_r]=i;
	extend();int u=0;std::vector<int> cur;
	while(true){
		if(mark[u])return false;
		std::vector<pi> out,in;
		for(auto v:e[u])if(!mark[v.first])out.pb(v);
		for(auto v:r[u])if(!mark[v.first])in.pb(v);
		if(SZ(out)>=2){
			int x=out[0].first,y=out[1].first,id1=out[0].second,id2=out[1].second;
			memset(tag,0,sizeof(tag)),res.clear(),flag=0,tag[u]=1,pre[u]=-1,pre[x]=u,w[x]=id1,dfs(x,id1);auto a=res;
			memset(tag,0,sizeof(tag)),res.clear(),flag=0,tag[u]=1,pre[u]=-1,pre[y]=u,w[y]=id2,dfs2(y,id2);
			std::vector<int> ans;
			if(flag)ans=cur+a+res+rev(cur);
			else{
				memset(tag,0,sizeof(tag)),res.clear(),flag=0,tag[u]=1,pre[u]=-1,pre[y]=u,w[y]=id2,dfs(y,id2);
				ans=cur+a+res+rev(a)+rev(res)+rev(cur);
			}
			return ans;
		}
		if(SZ(out)==0)return false;
		for(auto it:in)if(!--dg[it.first])_q[++_r]=it.first;
		extend(),mark[u]=1,u=out[0].first;cur.pb(out[0].second);
	}
}