#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int n,m,jlx[N],jly[N],out[N],tg[N],nx[N],pre[N],pre2[N],nx2[N],rl[N],zt[N],vis[N];
multiset <int> v[N],w[N];
vector <int> inv[N];
queue <int> q;
map <pair<int,int>,int> mp;
void del (int x=0) {
	if (x) {q.push(x);}
	while (q.size()) {
		int a=q.front();
		q.pop();
		tg[a]=0;
		for (auto x:w[a]) {
			v[x].erase(v[x].find(a));
			if (--out[x]==0) {q.push(x);}
		}
		for (auto x:v[a]) {w[x].erase(w[x].find(a));}
	}
}
void solvec (int x,int flg,int &y,int &ye,vector <int> &ans) {
	if (flg) {
		mp.clear();
		for (int i=0;i<m;i++) {
			if (i!=ye) {mp[make_pair(jlx[i],jly[i])]=i;}
		}
	}
	memset(vis,0,sizeof(vis));
	int nw=y,cls=0;
	vis[x]=1,pre[y]=x;
	ans.push_back(ye);
	while (!vis[nw]) {
		vis[nw]=1;
		if (zt[nw]) {ans.push_back(mp[make_pair(nx[nw],nw)]);}
		else {ans.push_back(mp[make_pair(nw,nx[nw])]);}
		if (!vis[nx[nw]]) {pre[nx[nw]]=nw;}
		else {cls=nw;}
		nw=nx[nw];
	}
	if (nw==x) {
		y=nx[x]=cls;
		nw=cls;
		zt[x]^=1;
		while (nw!=x) {
			zt[nw]^=1;
			nx[nw]=pre[nw];
			nw=pre[nw];
		}
		ye=mp[make_pair(cls,x)];
	} else {
		int dd=nw;
		nx[dd]=cls;
		nw=cls;
		zt[dd]^=1;
		while (nw!=dd) {
			zt[nw]^=1;
			nx[nw]=pre[nw];
			nw=pre[nw];
		}
		while (nw!=y) {
			ans.push_back(mp[make_pair(pre[nw],nw)]);
			nw=pre[nw];
		}
		ans.push_back(ye);
	}
}
vector <int> solve (int x) {
	vector <int> ans;
	int nw=x;
	while (nw!=1) {nw=pre2[nw];}
	while (nw!=x) {
		ans.push_back(mp[make_pair(nw,nx2[nw])]);
		nw=nx2[nw];
	}
	for (int i=1;i<=n;i++) {
		if (tg[i]&&i!=x) {
			nx[i]=(*v[i].begin());
			inv[(*v[i].begin())].push_back(i);
		}
	}
	q.push(x);
	while (q.size()) {
		int a=q.front();
		q.pop();
		rl[a]=1;
		for (auto x:inv[a]) {q.push(x);}
	}
	int y=0,z=0,ye=0,ze=0;
	for (int i=0;i<m;i++) {
		if (jlx[i]==x&&tg[jly[i]]) {
			if (!y) {y=jly[i],ye=i;}
			else if (!z) {z=jly[i],ze=i;}
		}
	}
	//cout << x << "  " << y << "  " << ye << "  " << z << "  " << ze << "  " << nx[5] << endl;
	if (!rl[z]) {swap(y,z),swap(ye,ze);}
	if (!rl[y]) {
		solvec(x,0,y,ye,ans);
		solvec(x,0,z,ze,ans);
		solvec(x,0,y,ye,ans);
		solvec(x,0,z,ze,ans);
	} else {
		memset(rl,0,sizeof(rl));
		int tmp=y,flg=0;
		while (tmp!=x) {rl[tmp]=1;tmp=nx[tmp];}
		tmp=z;
		while (tmp!=x) {flg|=rl[tmp];tmp=nx[tmp];}
		if (!flg) {
			solvec(x,0,y,ye,ans);
			solvec(x,0,z,ze,ans);
			solvec(x,0,y,ye,ans);
			solvec(x,0,z,ze,ans);
		} else {
			if (y!=z) {
				solvec(x,0,y,ye,ans);
				solvec(x,0,z,ze,ans);
				solvec(x,0,y,ye,ans);
			} else {
				vector <int> tmp;
				int cur=y,len=0;
				while (cur!=x) {tmp.push_back(mp[make_pair(cur,nx[cur])]);len++;cur=nx[cur];}
				ans.push_back(ye);
				for (int i=0;i<len;i++) {ans.push_back(tmp[i]);}
				ans.push_back(ze);
				ans.push_back(ye);
				for (int i=len-1;i>=0;i--) {ans.push_back(tmp[i]);}
				ans.push_back(ze);
			}
		}
	}
	while (nw!=1) {
		ans.push_back(mp[make_pair(pre2[nw],nw)]);
		nw=pre2[nw];
	}
	return ans;
}
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++) {
		v[U[i]+1].insert(V[i]+1),w[V[i]+1].insert(U[i]+1),out[U[i]+1]++;
		jlx[i]=U[i]+1,jly[i]=V[i]+1;
		mp[make_pair(U[i]+1,V[i]+1)]=i;
	}
	for (int i=1;i<=n;i++) {
		tg[i]=1;
		if (!out[i]) {q.push(i);}
	}
	del();
	int cur=1;
	while (cur) {
		if (out[cur]==0) {return false;}
		if (out[cur]>=2) {return solve(cur);}
		int tmp=*(v[cur].begin());
		del(cur);
		nx2[cur]=tmp,pre2[tmp]=cur;
		cur=tmp;
	}
}