#include<bits/stdc++.h>
//#include "islands.h"
bool test=0;
using namespace std;
const int c=300005, k=20;
int n, m, szint[c], fel[c], felel[c], fel2[c][k], bal[c], jobb[c], kezd, veg, specid;
vector<int> alaput, alapkor, ans, ut2;
vector<pair<int, int> > sz[c];
bool kesz, v[c], v2[c][2], korben[c], uton[c];
int lca(int a, int b) {
if (szint[a]<szint[b]) swap(a, b);
for (int i=k-1; i>=0; i--) {
if (szint[fel2[a][i]]>=szint[b]) a=fel2[a][i];
}
for (int i=k-1; i>=0; i--) {
if (fel2[a][i]!=fel2[b][i]) {
a=fel2[a][i], b=fel2[b][i];
}
}
if (a==b) return a;
return fel2[a][0];
}
void conc(vector<int> & a, vector<int> b) {
for (auto x:b) {
a.push_back(x);
}
}
vector<int> valt(vector<int> a) {
vector<int> b;
for (auto x:a) {
if (b.size()>0 && b.back()==x) b.pop_back();
else b.push_back(x);
}
return b;
}
vector<int> calc(int a, int b) {
assert(lca(a, b)==b);
vector<int> res;
while (a!=b) {
res.push_back(felel[a]);
a=fel[a];
}
return res;
}
void ket_kor(int a, int b, int c, int d) {
// a-b es b-d a ket specialis el, b es d nek nagyobb a szintje
if (kesz) return;
kesz=true;
for (int i=0; i<2; i++) {
vector<int> ut=calc(a, 1);
reverse(ut.begin(), ut.end());
conc(ans, ut);
vector<int> kor=calc(b, a);
reverse(kor.begin(), kor.end());
for (auto p:sz[b]) {
bool jo=0;
if (p.first==a) {
kor.push_back(p.second);
jo=1;
break;
}
assert(jo);
}
if (i==1) reverse(kor.begin(), kor.end());
conc(ans, kor);
reverse(ut.begin(), ut.end());
conc(ans, ut);
ut=calc(c, 1);
reverse(ut.begin(), ut.end());
conc(ans, ut);
kor=calc(d, c);
reverse(kor.begin(), kor.end());
for (auto p:sz[d]) {
bool jo=0;
if (p.first==c) {
kor.push_back(p.second);
jo=1;
break;
}
assert(jo);
}
if (i==1) reverse(kor.begin(), kor.end());
conc(ans, kor);
reverse(ut.begin(), ut.end());
conc(ans, ut);
}
}
void egy_kor() {
//assert(!kesz);
kesz=1;
int pos=jobb[ut2.back()];
assert(korben[pos]);
// alaput, alapkor, ut2, pos
conc(ans, alaput);
conc(ans, alapkor);
conc(ans, calc(kezd, 1));
conc(ans, ut2);
int si=alapkor.size(), kezd=-1;
for (int i=0; i<si; i++) {
if (jobb[alapkor[i]]==pos) {
kezd=i;
}
}
//assert(kezd!=-1);
for (int i=0; i<si; i++) {
int id=(kezd-i+si)%si;
ans.push_back(alapkor[id]);
}
reverse(ut2.begin(), ut2.end());
conc(ans, ut2);
reverse(ut2.begin(), ut2.end());
}
void dfs(int a) {
if (test) cout << "dfs " << a << "\n";
v[a]=true;
fel2[a][0]=fel[a];
for (int i=1; i<k; i++) {
fel2[a][i]=fel2[fel2[a][i-1]][i-1];
}
for (auto p:sz[a]) {
int x=p.first, y=p.second;
if (test) cout << "fontos " << x << " " << y << "\n";
if (!v[x]) {
szint[x]=szint[a]+1;
fel[x]=a, felel[x]=y;
dfs(x);
} else {
int cs=lca(a, x);
if (cs!=x) continue;
if (kezd==0) {
kezd=x, veg=a, specid=y;
} else {
int s=lca(kezd, x), t=lca(veg, a);
if (s==t) {
ket_kor(kezd, veg, x, a);
} else {
//assert(s==kezd || s==x);
if (s==kezd) kezd=x, veg=a, specid=y;
}
}
}
}
}
void dfs2(int a, bool b) {
v2[a][b]=1, uton[a]=1;
if (korben[a] && b && !kesz) {
egy_kor();
}
for (auto p:sz[a]) {
int x=p.first, y=p.second;
if (uton[x]) continue;
int su=alaput.size(), su2=ut2.size();
if (su==su2 && b==0 && y==alapkor[0]) continue;
bool kov=b;
if (su<=su2 || y!=alaput[su2]) kov=1;
if (!v2[x][kov]) {
ut2.push_back(y);
dfs2(x, kov);
assert(ut2.back()==y);
ut2.pop_back();
}
}
}
variant<bool, vector<int>> find_journey(
//bool find_journey(
int N, int M, vector<int> U, vector<int> V) {
n=N, m=M;
for (int i=0; i<m; i++) {
int a=U[i], b=V[i];
sz[a+1].push_back({b+1, i});
bal[i]=a+1, jobb[i]=b+1;
}
szint[1]=1;
dfs(1);
if (test) cout << "vege " << kezd << " " << veg << "\n";
if (kezd==0) {
return false;
}
alaput=calc(kezd, 1);
reverse(alaput.begin(), alaput.end());
alapkor=calc(veg, kezd);
for (auto x:alapkor) {
korben[bal[x]]=1, korben[jobb[x]]=1;
}
reverse(alapkor.begin(), alapkor.end());
alapkor.push_back(specid);
//assert(alapkor.size()>0);
if (!kesz) {
dfs2(1, 0);
}
if (!kesz) {
return false;
} else {
ans=valt(ans);
//assert(ans.size()>0);
return ans;
//return true;
}
/*if (N > 2) {
return vector<int>({0, 1, 2, 4, 0, 3, 2, 1, 4, 3});
}
return false;*/
}
/*
int main() {
int nn, mm;
vector<int> aa, bb;
cin >> nn >> mm;
for (int i=0; i<mm; i++) {
int x, y;
cin >> x >> y;
aa.push_back(x), bb.push_back(y);
}
bool ans=find_journey(nn, mm, aa, bb);
cout << "sikerult: " << ans << "\n";
return 0;
}
*/
/*
2 3
0 1
1 0
1 0
*/
