#include "islands.h"
#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++){
edges[U[i]].insert({V[i],i});
}
// if(edges[0].size() < 2) return false;
vector<int> ans;
vector<bool> vis(N,false);
int root = 0;
vector<int> to_root;
while(edges[root].size() <= 1){
if(edges[root].size() == 0) return false;
auto [nxt,id] = *edges[root].begin();
to_root.push_back(id);
vis[root] = true;
edges[root].erase({nxt,id});
edges[nxt].erase({root,co(id)});
root = nxt;
}
// cout << "!" << root << endl;
function<void(int)> dfs = [&](int cur){
// cout << "?" << cur << endl;
vis[cur] = true;
if(cur == root){
vis[edges[cur].begin()->first] = true;
}
for(auto [nxt,id]:edges[cur]){
if(vis[nxt]) continue;
ans.push_back(id);
dfs(nxt);
ans.push_back(co(id));
}
if(cur == root){
auto [nxt,id] = *edges[cur].begin();
ans.push_back(id);
dfs(nxt);
ans.push_back(co(id));
}
};
dfs(root);
// for(int i = 0;i < N;i++) cout << vis[i] << " ";cout << endl;
// for(int i = 0;i < N;i++) if(!vis[i]) return false;
int csz = ans.size();
for(int i = 0;i < csz;i++) ans.push_back(co(ans[i]));
vector<int> ret = to_root;
for(auto &i:ans) ret.push_back(i);
for(int i = to_root.size()-1;i >= 0;i--) ret.push_back(to_root[i]);
return ret;
// return ans;
}
