#include "islands.h"
#include<bits/stdc++.h>
#include <variant>
#include <vector>
#define arestas aresta
using namespace std;
const int N = 1010;
set <int> g[N];
int mark[N], pai[N];
vector <int> ans;
vector <int> aresta[N][N];
bool dfs(int v, int p){
mark[v] = 1;
pai[v] = p;
for(auto x : g[v]){
if(x != p and mark[x]){
vector <int> ciclo;
int xx = v;
while(xx != x){
ciclo.push_back(xx);
xx = pai[xx];
}
ciclo.push_back(x);
vector <int> path;
xx = x;
while(xx != 0){
path.push_back(xx);
xx = pai[xx];
}
path.push_back(0);
reverse(path.begin(), path.end());
//exit(0);
for(int i = 0;i+1 < path.size();i++){
ans.push_back(arestas[path[i]][path[i+1]][0]);
}
reverse(ciclo.begin(), ciclo.end());
int t = ciclo.size();
for(int i = 0;i < ciclo.size();i++){
ans.push_back(arestas[ciclo[i]][ciclo[(i+1)%t]][0]);
}
for(int i = 0;i < ciclo.size();i++){
ans.push_back(arestas[ciclo[i]][ciclo[(i+1)%t]][1]);
}
for(int i = ciclo.size()-1;i > 0;i--){
i++;
ans.push_back(arestas[ciclo[((i-1)%t+t)%t]][ciclo[i%t]][0]);
i--;
}
for(int i = ciclo.size()-1;i > 0;i--){
i++;
ans.push_back(arestas[ciclo[((i-1)%t+t)%t]][ciclo[i%t]][1]);
i--;
}
t = path.size();
for(int i = t-2;i > 0;i--){
ans.push_back(arestas[path[i]][path[i+1]][0]);
}
//exit(0);
return true;
}
else if(x == p) continue;
if(dfs(x, v)) return true;
}
return false;
}
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
int n = N;
for(int i = 0;i < M;i++){
g[U[i]].insert(V[i]);
aresta[U[i]][V[i]].push_back(i);
}
if(dfs(0, 0)) return ans;
return false;
}
