#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>adj[100100];
vector<int>RES;
bitset<100100>vis,ons;
vector<int>stk;
void MKCYC(vector<int>v){
for(auto i:v)
RES.push_back(i);
for(auto i:v)
RES.push_back(i^1);
reverse(v.begin(),v.end());
for(auto i:v)
RES.push_back(i);
for(auto i:v)
RES.push_back(i^1);
}
int dfs(int n){
vis[n]=1;
ons[n]=1;
stk.push_back(n);
for(auto[go,ind]:adj[n]){
if(ons[go]){
vector<int>v{ind};
while(stk.back()!=go)
stk.pop_back(),
v.push_back(RES.back()),
RES.pop_back();
reverse(v.begin(),v.end());
vector<int>stilon=RES;
MKCYC(v);
reverse(stilon.begin(),stilon.end());
for(auto i:stilon)
RES.push_back(i);
return 1;
}
if(vis[go])continue;
RES.push_back(ind);
if(dfs(go)) {
return 1;
}
RES.pop_back();
}
ons[n]=0;
stk.pop_back();
return 0;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
for(int i=0;i<M;i+=2)
adj[U[i]].push_back({V[i],i});
if(dfs(0))
return RES;
return false;
}
