#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], T[MAXN];
int oc[MAXN];
bitset<MAXM> dead;
variant<bool, vector<int>> find_journey(int N, int M, vector<int> A, vector<int> B) {
for(int i = M; i--;) {
G[A[i]].eb(i);
T[B[i]].eb(i);
oc[A[i]]++;
}
vector<int> PV;
int S = 0;
vector<int> ZV;
for(int i = N; i--;) if(!oc[i]) ZV.eb(i);
while(1 == oc[S] || !ZV.empty()) {
if(1 == oc[S]) {
int e = *find_if(allv(G[S]), [&](int e){ return !dead[e]; });
PV.eb(e);
dead[e] = true;
oc[S] = 0;
ZV.eb(S);
S = B[e];
}
int i = ZV.back(); ZV.pop_back();
for(int e : T[i]) {
dead[e] = true;
int v = A[e];
if(!--oc[v]) ZV.eb(v);
}
}
for(int i = N; i--;) G[i].clear();
for(int i = M; i--;) if(!dead[i]) G[A[i]].eb(i);
if(G[S].empty()) return false;
for(int i = N; i--;)
G[i].resize(i == S ? 2 : 1);
for(int i = M; i--;) A[i] ^= B[i];
dead.reset();
vector<int> CV;
int pve = -1, v = S;
do {
for(int e : G[v]) if(e != pve) {
CV.eb(e);
pve = e;
dead[e] = !dead[e];
delv(G[v], e);
v ^= A[e];
G[v].eb(e);
break;
}
} while(v != S || dead.any());
vector<int> r = PV;
r.insert(r.end(), allv(CV));
reverse(allv(PV));
r.insert(r.end(), allv(PV));
return r;
}
