#include "islands.h"
#include <cassert>
#include <cstdio>
#include <variant>
#include <vector>
#include <variant>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<pair<int,int>>adj[2005];
pair<int,int>par[1005];
int onstack[1005];
int fre[1005];
int inf=1e9;
vector<int>solution;
void sol(int bottom,int top,int edge)
{
vector<int>vec,vec2,cop2;
vector<int>cop;
int curr2=top;
while(curr2!=0)
{
vec.push_back(par[curr2].second);
cop.push_back(par[curr2].second);
curr2=par[curr2].first;
}
reverse(vec.begin(),vec.end());
curr2=bottom;
vec2.push_back(edge);
cop2.push_back(edge);
while(curr2!=top)
{
vec2.push_back(par[curr2].second);
cop2.push_back(par[curr2].second);
curr2=par[curr2].first;
}
reverse(vec2.begin(),vec2.end());
for(auto x:vec2)
{
vec.push_back(x);
}
for(auto x:vec2)
{
vec.push_back(x^1);
}
for(auto x:cop2)
{
vec.push_back(x);
}
for(auto x:cop2)
{
vec.push_back(x^1);
}
for(auto x:cop)
{
vec.push_back(x);
}
solution=vec;
}
void dfs(int curr)
{
for(auto k:adj[curr])
{
if(solution.size())
{
return;
}
if(fre[k.first]==0)
{
par[k.first]=make_pair(curr,k.second);
fre[k.first]=1;
onstack[k.first]=1;
dfs(k.first);
}
else if(onstack[k.first]==1)
{
sol(curr,k.first,k.second);
}
}
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V)
{
int n=N;
vector<int>vec;
for(int i=0; i<M; i+=2)
{
adj[U[i]].push_back({V[i],i});
}
fre[0]=1;
onstack[0]=1;
dfs(0);
if(solution.size())
{
return solution;
}
return false;
}
