#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];
void nullazas() {
for (int i=1; i<=n; i++) {
szint[i]=0, fel[i]=0, felel[i]=0;
v[i]=0, v2[i][0]=0, v2[i][1]=0, korben[i]=0, uton[i]=0;
for (int j=0; j<k; j++) fel2[i][j]=0;
}
alaput.clear(), alapkor.clear(), ans.clear(), ut2.clear();
kezd=0, veg=0, specid=0;
}
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) {
if (test) cout << "ket kor\n" << "\n";
// 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());
bool jo=0;
for (auto p:sz[b]) {
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());
jo=0;
for (auto p:sz[d]) {
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() {
if (test) cout << "egy kor\n";
assert(!kesz);
kesz=1;
int pos=jobb[ut2.back()];
assert(korben[pos]);
// alaput, alapkor, ut2, pos
if (test) {
cout << "alaput: ";
for (auto x:alaput) cout << x << " ";
cout << "\n";
}
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();
}
}
uton[a]=0;
}
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;
}
for (int proba=0; proba<6; proba++) {
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) {
break;
}
nullazas();
for (int i=1; i<=n; i++) {
random_shuffle(sz[i].begin(), sz[i].end());
}
}
if (!kesz) {
return false;
} else {
ans=valt(ans);
assert(ans.size()>0);
return ans;
//return true;
}
}
/*
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 res=find_journey(nn, mm, aa, bb);
cout << "sikerult: " << res << "\n";
for (auto x:ans) {
cout << x << " ";
}
cout << "\n";
return 0;
}
*/
/*
7
9
0 1 1 2 2 3 3 4 4 5 5 6
4 2
1 5
6 1
*/
