#include "islands.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define delv(V,x) (V).erase(find(allv(V),(x)))
using namespace std;
const int MAXN = 100'055;
const int MAXM = 200'055;
vector<int> G[MAXN];
int oc[MAXN];
bitset<MAXM> dead;
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
for(int i = M; i--;) {
G[V[i]].eb(i);
oc[U[i]]++;
}
{
vector<int> V;
for(int i = N; i--;) if(!oc[i]) V.eb(i);
while(!V.empty()) {
int i = V.back();
V.pop_back();
for(int e : G[i]) {
dead[e] = true;
int v = U[e];
if(!--oc[v]) V.eb(v);
}
}
}
for(int i = N; i--;) G[i].clear();
for(int i = M; i--;) if(!dead[i]) G[U[i]].eb(i);
vector<int> PV;
int S = 0;
while(1 == sz(G[S])) {
int e = G[S][0];
PV.eb(e);
G[S].clear();
S = V[e];
}
if(!S && !PV.empty()) return false;
for(int i = N; i--;) {
if(i == S) G[i].resize(2);
else if(!G[i].empty()) G[i].resize(1);
}
for(int i = M; i--;) U[i] ^= V[i];
vector<int> CV;
{
int pve = -1, v = S, cnt = 0;
while(cnt < 4) {
for(int e : G[v]) if(e != pve) {
CV.eb(e);
pve = e;
delv(G[v], e);
v = U[e] ^ v;
G[v].eb(e);
break;
}
if(v == S) cnt++;
}
}
vector<int> r = PV;
r.insert(r.end(), allv(CV));
reverse(allv(PV));
r.insert(r.end(), allv(PV));
return r;
}
