#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
set<pair<int,int>>adj[100100];
vector<int>RES;
bitset<100100>vis;
int dfs(int n){
vis[n]=1;
if(adj[n].size()>=2){
auto[go,ind]=*adj[n].begin();
auto[go2,ind2]=*++adj[n].begin();
RES.push_back(ind);
RES.push_back(ind^1);
RES.push_back(ind2);
RES.push_back(ind2^1);
RES.push_back(ind^1);
RES.push_back(ind);
RES.push_back(ind2^1);
RES.push_back(ind2);
return 1;
}
for(auto[go,ind]:adj[n]){
if(vis[go])continue;
adj[go].erase({n,ind^1});
RES.push_back(ind);
if(dfs(go)) {
RES.push_back(ind);
return 1;
}
RES.pop_back();
}
return 0;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
if(N==2) {
vector<int>atob,btoa;
for(int i=0;i<M;i++)
(U[i]?btoa:atob).push_back(i);
if(atob.size()<2||btoa.empty())
return false;
vector<int>v;
v.push_back(atob[0]);
v.push_back(btoa[0]);
v.push_back(atob[1]);
v.push_back(atob[0]);
v.push_back(btoa[0]);
v.push_back(atob[1]);
return v;
} else {
for(int i=0;i<M;i++)
adj[U[i]].insert({V[i],i});
if(dfs(0))
return RES;
return false;
}
}
