#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[2005];
queue<int>qu;
vector<int> solve(int curr)
{
vector<int>vec;
vector<int>cop;
int curr2=curr;
while(curr2!=0)
{
vec.push_back(par[curr2].second);
cop.push_back(par[curr2].second);
curr2=par[curr2].first;
}
reverse(vec.begin(),vec.end());
int a=-1,b=-1;
for(auto k:adj[curr])
{
if((k.second^1)!=par[curr].second)
{
if(a==-1)
{
a=k.second;
}
else if(b==-1)
{
b=k.second;
}
}
}
vec.push_back(a);
vec.push_back(a^1);
vec.push_back(b);
vec.push_back(b^1);
vec.push_back(a^1);
vec.push_back(a);
vec.push_back(b^1);
vec.push_back(b);
for(auto x:cop)
{
vec.push_back(x);
}
return vec;
}
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++)
{
adj[U[i]].push_back({V[i],i});
}
if(adj[0].size()==2)
{
par[0].second=1e9;
vec=solve(0);
return vec;
}
for(int i=0;i<=n;i++)
{
par[i]={-1,-1};
}
qu.push(0);
while(qu.size())
{
auto curr=qu.front();
qu.pop();
for(auto k:adj[curr])
{
if(par[k.first]==make_pair(-1,-1))
{
par[k.first].first=curr;
par[k.first].second=k.second;
qu.push(k.first);
}
}
}
for(int i=0;i<N;i++)
{
if(adj[i].size()>=3 && par[i].first!=-1)
{
vec=solve(i);
return vec;
}
}
return false;
}
