#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e3+5;
int ans, vs[nx], a, b, c,D;
pair<int, int> pa[nx];
vector<pair<int, int>> d[nx];
vector<int> res;
int adjust(int x)
{
int tmp=1-x%2;
return (x/2)*2+tmp;
}
void dfs(int u, int p)
{
if (ans) return;
vs[u]=1;
//cout<<"dfs "<<u<<' '<<p<<'\n';
if (!ans&&(int)d[u].size()-(u!=p)>=2)
{
vector<int> tmp;
int cur=u, cnt=0;
while (cur!=0) tmp.push_back(pa[cur].second), cur=pa[cur].first;
reverse(tmp.begin(), tmp.end());
for (auto x:tmp) res.push_back(x);
reverse(tmp.begin(), tmp.end());
//cout<<"size "<<d[u].size()<<'\n';
for (auto [x, idx]:d[u])
{
//cout<<"here "<<x<<' '<<idx<<'\n';
if (x!=p&&cnt==0)
{
a=idx;
b=adjust(a);
cnt++;
}
else if (x!=p&&cnt==1)
{
c=idx;
D=adjust(c);
cnt++;
}
}
//cout<<"debug "<<a<<' '<<b<<' '<<c<<' '<<D<<'\n';
res.push_back(a);
res.push_back(b);
res.push_back(c);
res.push_back(D);
res.push_back(a);
res.push_back(b);
res.push_back(c);
res.push_back(D);
for (auto x:tmp) res.push_back(x);
ans=1;
}
for (auto [v, idx]:d[u]) if (v!=p&&!vs[v]) pa[v]={u, idx}, dfs(v, u);
}
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
for (int i=0; i<M; i+=2) d[U[i]].push_back({V[i], i}), d[V[i]].push_back({U[i], i+1});
//for (int i=0; i<N;i ++) cout<<"sz "<<i<<' '<<d[i].size()<<'\n';
dfs(0, 0);
if (ans) return res;
return false;
}
/*
4 6
0 1
1 0
1 2
2 1
3 1
1 3
*/
