#include <bits/stdc++.h>
#include "islands.h"
using namespace std;
typedef pair <vector <int>, vector <int>> pvv;
bool check(int M, vector <int> u, vector <int> v, vector <int> s) {
int curr = 0, prev = -1;
vector <int> occ(M);
for (auto it : s) {
if (it == prev)
return false;
if (u[it] != curr)
return false;
curr = v[it];
swap(u[it], v[it]);
occ[it] ^= 1;
prev = it;
}
return !count(occ.begin(), occ.end(), 1);
}
vector <int> min_rot(vector <int> v) {
rotate(v.begin(), min_element(v.begin(), v.end()), v.end());
return v;
}
variant <bool, vector <int>> find_journey(int N, int M, vector <int> u, vector <int> v) {
queue <int> sinks;
vector <unordered_set <int>> in(N), out(N);
for (int i = 0; i < M; i++) {
out[u[i]].insert(i);
in[v[i]].insert(i);
}
auto refresh = [&](int x) {
if (out[x].empty())
sinks.push(x);
};
for (int i = 0; i < N; i++)
refresh(i);
int curr = 0;
vector <int> sofar;
while (1) {
auto other = [&](int e, int x) {
return u[e] ^ v[e] ^ x;
};
auto remove = [&](int x) {
for (auto it : in[x]) {
int tmp = other(it, x);
out[tmp].erase(it);
refresh(tmp);
}
for (auto it : out[x])
in[other(it, x)].erase(it);
};
for (; !sinks.empty(); sinks.pop()) {
if (sinks.front() == curr)
return false;
remove(sinks.front());
}
if (out[curr].size() == 1) {
int edge = *out[curr].begin();
remove(curr);
curr = other(edge, curr);
sofar.push_back(edge);
}
else {
auto find_cycle = [&](int x, int e, bool b) {
int y = x;
vector <int> path = {e};
vector <bool> bio(N);
bio[x] = b;
for (x = other(e, x); !bio[x]; x = other(e, x)) {
path.push_back(e = *out[x].begin());
bio[x] = true;
}
bool flag = false;
vector <int> tail, cycle;
for (auto it : path) {
flag |= y == x;
if (flag)
cycle.push_back(it);
else
tail.push_back(it);
y = other(it, y);
}
return pvv(tail, cycle);
};
auto it = out[curr].begin();
pvv cyc1 = find_cycle(curr, *it++, true);
pvv cyc2 = find_cycle(curr, *it++, false);
vector <int> sol;
auto append = [&](vector <int> &v) {
sol.insert(sol.end(), v.begin(), v.end());
reverse(v.begin(), v.end());
};
append(sofar);
bool eq = min_rot(cyc1.second) == min_rot(cyc2.second);
for (int i = 0; i < 2; i++) {
auto traverse = [&](pvv &p1, pvv &p2) {
append(p1.first);
append(p1.second);
if (eq)
reverse(p2.second.begin(), p2.second.end());
append(p1.first);
};
traverse(cyc1, cyc2);
traverse(cyc2, cyc1);
}
append(sofar);
assert(check(M, u, v, sol));
return sol;
}
}
}
