#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e3+5;
int ans, vs[nx];
vector<pair<int, int>> d[nx];
vector<int> l, res;
pair<int, int> pa[nx], pa2[nx];
void dfs(int u)
{
vs[u]=1;
l.push_back(u);
for (auto [v, idx]:d[u]) if (!vs[v]) pa[v]={u, idx}, dfs(v);
}
void dfs2(int u, int rt)
{
vs[u]=1;
for (auto [v, idx]:d[u])
{
if (!ans&&v==rt)
{
vector<int> tmp, path;
int cur=rt;
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());
cur=u;
path.push_back(idx);
while (cur!=rt) path.push_back(pa2[cur].second), cur=pa[cur].first;
reverse(path.begin(), path.end());
for (auto x:path) res.push_back(x);
for (auto x:path) res.push_back(x+1);
reverse(path.begin(), path.end());
for (auto x:path) res.push_back(x);
for (auto x:path) res.push_back(x+1);
for (auto x:tmp) res.push_back(x);
ans=1;
}
if (vs[v]) continue;
else pa2[v]={u, idx}, dfs2(v, rt);
}
}
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)
{
bool f=0;
for (auto x:d[U[i]]) if (x.first==V[i]) f=1;
if (!f) d[U[i]].push_back({V[i], i});
}
dfs(0);
for (auto x:l)
{
if (!ans)
{
for (int i=0; i<N; i++) vs[i]=0;
dfs2(x, x);
}
}
if (ans) return res;
return false;
}
/*
5 10
0 1
0 1
1 2
1 2
2 3
2 3
3 4
3 4
4 2
4 2
*/
