#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 1000;
vector<pair<int,int>> nei[M];
vector<int> ans;
int vis[M], par[M], id[M];
void dfs(int u)
{
vis[u]=1;
if (ans.size())
{
vis[u]=2;
return;
}
for (auto [i,x]:nei[u])
if (!vis[i])
par[i]=u,id[i]=x,dfs(i);
else if(vis[i]==1)
{
int v=u;
while (v)
ans.push_back(id[v]),v=par[v];
reverse(ans.begin(),ans.end());
ans.push_back(x);
int m=ans.size();
for (int o=0;o<m;o++)
{
if (ans[o]==id[i])
{
for (int j=o+1;j<m;j++)
ans.push_back(ans[j]+1);
for (int j=m-1;j>o;j--)
ans.push_back(ans[j]);
for (int j=m-1;j>o;j--)
ans.push_back(ans[j]+1);
for (int j=o;j>=0;j--)
ans.push_back(ans[j]);
break;
}
}
break;
}
vis[u]=2;
}
variant<bool, vector<int>> find_journey(int n, int m, vector<int> U, vector<int> V)
{
for (int i=0;i<m;i+=2)
nei[U[i]].push_back({V[i],i});
dfs(0);
if (ans.size()) return ans;
return false;
}
