#include "islands.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
auto co = [](int id){
if(id%2 == 0) return id+1;
else return id-1;
};
vector<set<pair<int,int>>> edges(N);// nxt,id
for(int i = 0;i < M;i+=2){
edges[U[i]].insert({V[i],i});
}
vector<bool> vis(N,false);
set<int> anc;
vector<pair<int,int>> nxt_edges(N);// nxt,id
vector<int> ans;
function<void(int)> dfs = [&](int cur){
vis[cur] = true;
anc.insert(cur);
for(auto [nxt,id]:edges[cur]){
if(anc.count(nxt)) {
// find the answer
vector<int> before_loop;
int croot = 0;
while(croot != nxt){
before_loop.push_back(nxt_edges[croot].second);
croot = nxt_edges[croot].first;
}
vector<int> in_loop;
do{
in_loop.push_back(nxt_edges[croot].second);
croot = nxt_edges[croot].first;
}while(croot != nxt);
for(auto &i:before_loop) ans.push_back(i);
for(auto &i:in_loop) ans.push_back(i);
for(auto &i:in_loop) ans.push_back(co(i));
reverse(before_loop.begin(),before_loop.end());
reverse(in_loop.begin(),in_loop.end());
for(auto &i:in_loop) ans.push_back(i);
for(auto &i:in_loop) ans.push_back(co(i));
for(auto &i:before_loop) ans.push_back(i);
return;
}
if(vis[nxt]) continue;
nxt_edges[cur] = {nxt,id};
dfs(nxt);
if(!ans.empty()) return;
}
anc.erase(cur);
};
dfs(0);
if(ans.empty()) return false;
return ans;
}
