#include <bits/stdc++.h>
#include "islands.h"
using namespace std;
typedef pair <vector <int>, vector <int>> pvv;
void output(const vector <int> &v) {
for (auto it : v)
printf("%d ", it);
puts("");
}
void output(const pvv &p) {
output(p.first);
output(p.second);
}
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 !curr && !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 <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 remove = [&](int x) {
for (auto it : in[x]) {
out[u[it]].erase(it);
refresh(u[it]);
}
for (auto it : out[x])
in[v[it]].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 = v[edge];
sofar.push_back(edge);
}
else {
assert(out[curr].size() >= 2);
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 = v[e]; !bio[x]; x = v[e]) {
path.push_back(e = *out[x].begin());
bio[x] = true;
}
int last = -1;
for (int i = 0; i < path.size(); i++) {
if (y == x)
last = i;
y = v[path[i]];
}
vector <int> tail, cycle;
for (int i = 0; i < path.size(); i++)
if (i < last)
tail.push_back(path[i]);
else
cycle.push_back(path[i]);
return pvv(tail, cycle);
};
auto it = out[curr].begin();
pvv cyc1 = find_cycle(curr, *it++, true);
pvv cyc2 = find_cycle(curr, *it++, false);
//output(cyc1);
//output(cyc2);
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;
}
}
}
