#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=2e5+5;
int n,m,u,tp,tp1,tp2,ps,ps1,ps2,dg[N],q[N];bool vs1[N],vs2[N];
struct Edge {int v,w;}z[N],z1[N],z2[N];
vector<int> U,V,ans,e2[N];vector<Edge> e[N],e1[N];
void upd()
{
	while(q[0]<=q[1])
	{
		int u=q[q[0]++];
		for(auto v:e2[u]) if(dg[v]) {--dg[v];if(!dg[v]) q[++q[1]]=v;}
	}
}
void slv(int u)
{
	bool fl=0;
	for(int i=0,u,v;i<m;++i)
	{u=U[i]+1;v=V[i]+1;if(dg[u] && dg[v]) e[u].pb((Edge) {v,i});}
	
	vs1[u]=1;z1[++tp1]=e[u][0];
	for(int i=e[u][0].v;;i=e[i][0].v)
	{if(vs1[i]) break;vs1[i]=1;z1[++tp1]=e[i][0];}
	for(int i=tp1-1;i;--i) if(z1[i].v==z1[tp1].v) {ps1=i;break;}
	for(int i=1;i<=n;++i) vs1[i]=0;
	for(int i=ps1+1;i<=tp1;++i) vs1[z1[i].v]=1;
	
	vs2[u]=1;z2[++tp2]=e[u][1];
	for(int i=e[u][1].v;;i=e[i][0].v)
	{if(vs1[i]) {fl=1;break;}if(vs2[i]) break;vs2[i]=1;z2[++tp2]=e[i][0];}
	for(int i=tp2-1;i;--i) if(z2[i].v==z2[tp2].v) {ps2=i;break;}
	
	for(int i=1;i<=tp1;++i) ans.pb(z1[i].w);
	for(int i=ps1;i;--i) ans.pb(z1[i].w);
	
	if(fl)
	{
		for(int i=1;i<=tp2;++i) ans.pb(z2[i].w);
		for(int i=tp1;i>ps1;--i) if(z1[i].v==z2[tp2].v) {ps=i;break;}
		for(int i=ps;i>ps1;--i) ans.pb(z1[i].w);
		for(int i=tp1;i>ps;--i) ans.pb(z1[i].w);
		for(int i=tp2;i;--i) ans.pb(z2[i].w);return;
	}
	
	for(int i=1;i<=tp2;++i) ans.pb(z2[i].w);
	for(int i=ps2;i;--i) ans.pb(z2[i].w);
	for(int i=1;i<=ps1;++i) ans.pb(z1[i].w);
	for(int i=tp1;i>ps1;--i) ans.pb(z1[i].w);
	for(int i=ps1;i;--i) ans.pb(z1[i].w);
	for(int i=1;i<=ps2;++i) ans.pb(z2[i].w);
	for(int i=tp2;i>ps2;--i) ans.pb(z2[i].w);
	for(int i=ps2;i;--i) ans.pb(z2[i].w);
	
}
variant<bool,vector<int>> find_journey(int n1,int m1,vector<int> U1,vector<int> V1)
{
	n=n1;m=m1;U=U1;V=V1;
	for(int i=0,u,v;i<m;++i)
		u=U[i]+1,v=V[i]+1,e1[u].pb((Edge) {v,i}),e2[v].pb(u),++dg[u];
	u=1;q[0]=2;q[1]=1;for(int i=1;i<=n;++i) if(!dg[i]) q[++q[1]]=i;upd();
	while(1)
	{
		if(!dg[u]) return false;
		if(dg[u]>1)
		{
			for(int i=1;i<=tp;++i) ans.pb(z[i].w);slv(u);
			for(int i=tp;i;--i) ans.pb(z[i].w);return ans;
		}int t=0;for(auto i:e1[u]) if(dg[i.v]) {z[++tp]=i;t=i.v;break;}
		dg[u]=0;q[++q[1]]=u;upd();u=t;
	}return false;
}