#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;
const int MAXN = 100100*1;
const ll MOD = 998244353;
const ll INF = 2e9;
queue<int> q;
set<pi> adj[MAXN], adjt[MAXN];
int chk[MAXN]; bool flip[MAXN*2];
void clean() {
while(q.size()) {
int here = q.front(); q.pop();
for(auto [there, x] : adj[here]) {
adjt[there].erase(pi(here, x));
} for(auto [there, x] : adjt[here]) {
adj[there].erase(pi(here, x));
if(adj[there].size() == 0) q.push(there);
}
adj[here].clear(); adjt[here].clear();
}
}
vector<int> tmp, res;
vector<pi> pathA, cycleA, pathB, cycleB;
vector<int> A, B;
bool flag;
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
for(int i=0; i<M; i++) {
adj[U[i]].insert(pi(V[i], i));
adjt[V[i]].insert(pi(U[i], i));
}
for(int i=0; i<N; i++) {
if(adj[i].empty()) q.push(i);
} clean();
// if 0 erased then return false
if(adj[0].empty()) return false;
int here = 0;
while(true) {
if(adj[here].empty()) return false;
if(adj[here].size() == 1) {
auto [there, x] = *adj[here].begin();
q.push(here); clean();
tmp.push_back(x); here = there; continue;
}
// first cycle
chk[here] = 1;
int there = adj[here].begin()->ff, x = adj[here].begin()->ss;
pathA.push_back(pi(here, x));
while(true) {
if(chk[there]) {
//for(auto [there,x]:pathA)cout<<x<<bl;cout<<endl;
while(true) {
cycleA.push_back(*pathA.rbegin());
pathA.pop_back();
if(cycleA.rbegin()->ff == there) break;
}
break;
}
chk[there] = 1;
pathA.push_back(pi(there, 0));
x = adj[there].begin()->ss, there = adj[there].begin()->ff;
pathA.rbegin()->ss = x;
} reverse(all(cycleA));
//for(auto [there,x]:cycleA) cout<<x<<bl;cout<<endl;
// for(auto [there,x] : pathA) A.push_back(x);
// for(auto [there,x] : cycleA) A.push_back(x);
// reverse(all(pathA));
// for(auto [there,x] : pathA) A.push_back(x);
// second cycle
memset(chk, 0, sizeof chk);
for(auto [there,x] : cycleA) chk[there] = -1;
chk[here] = 1;
there = adj[here].rbegin()->ff, x = adj[here].rbegin()->ss;
pathB.push_back(pi(here, x));
while(true) {
if(chk[there] == 1) {
while(true) {
cycleB.push_back(*pathB.rbegin());
pathB.pop_back();
if(cycleB.rbegin()->ff == there) break;
} reverse(all(cycleB));
break;
} else if(chk[there] == -1) {
int j=0; flag = 1;
while(cycleA[j].ff!=there) j++;
int sz=cycleA.size();
for(int k=0; k<sz; k++) {
j=(j-1+sz)%sz;
cycleB.push_back(cycleA[j]);
}
break;
}
chk[there] = 1;
pathB.push_back(pi(there, 0));
x = adj[there].begin()->ss, there = adj[there].begin()->ff;
pathB.rbegin()->ss = x;
}
// for(auto [there,x] : pathB) B.push_back(x);
// for(auto [there,x] : cycleB) B.push_back(x);
// reverse(all(pathB));
// for(auto [there,x] : pathB) B.push_back(x);
break;
}
for(int x:tmp) res.push_back(x); reverse(all(tmp));
int cnt = (flag ? 1 : 2);
while(cnt--) {
for(auto [there,x]:pathA) res.push_back(x); reverse(all(pathA));
for(auto [there,x]:cycleA) res.push_back(x); reverse(all(cycleA));
for(auto [there,x]:pathA) res.push_back(x);
for(auto [there,x]:pathB) res.push_back(x); reverse(all(pathB));
for(auto [there,x]:cycleB) res.push_back(x); reverse(all(cycleB));
for(auto [there,x]:pathB) res.push_back(x);
}
for(int x:tmp) res.push_back(x);
cnt = 0, here = 0;
for(int x:res) {
assert(here == U[x]);
here = V[x];
swap(U[x], V[x]);
flip[x] ^= 1;
if(flip[x]) cnt++;
else cnt--;
}
assert(cnt==0); assert(here==0);
//assert(res.size() <= 2000000);
return res;
}
