#include "islands.h"
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <variant>
#include <vector>
using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;
using ll = long long;
constexpr int inf = (1 << 30) - 1;
constexpr ll infll = (1ll << 62) - 1;
template <class F> struct make_fixed : private F {
explicit make_fixed(F&& f) : F(std::forward<F>(f)) {}
template <class... Args> decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
template <class T, class... Args> void DBG(const T& x, const Args&... args) {
std::cerr << x;
if constexpr (sizeof...(args)) {
std::cerr << ' ';
DBG(args...);
} else {
std::cerr << std::endl;
}
}
template <class T> void DBG(const vector<T>& v) {
std::cerr << '[';
bool f = false;
for (const T& x : v) {
if (f) std::cerr << ", ";
f = true;
std::cerr << x;
}
std::cerr << ']' << std::endl;
}
void append(vector<int>& a, vector<int> b) {
std::copy(b.begin(), b.end(), std::back_inserter(a));
}
vector<int> slice(const vector<int>& a, int l, int r) {
return vector<int>(a.begin() + l, a.begin() + r);
}
vector<int> rev(const vector<int>& a) {
return vector<int>(a.rbegin(), a.rend());
}
std::variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
const auto other = [&](int u, int e) { return U[e] ^ V[e] ^ u; };
vector<vector<int>> G(N), rG(N);
for (int i = 0; i < M; ++i) {
G[U[i]].push_back(i);
rG[V[i]].push_back(i);
}
vector<int> out(N);
vector<char> dead(N);
std::queue<int> que;
const auto clean = [&] {
while (!que.empty()) {
const int u = que.front();
que.pop();
dead[u] = true;
for (const int e : rG[u]) {
const int v = other(u, e);
if ((--out[v]) == 0) que.push(v);
}
}
};
for (int i = 0; i < N; ++i) {
out[i] = (int)G[i].size();
if (out[i] == 0) que.push(i);
}
clean();
vector<int> path;
for (int u = 0;;) {
if (dead[u]) return false;
vector<int> next;
for (const int e : G[u]) {
if (!dead[other(u, e)]) next.emplace_back(e);
}
if (next.size() >= 2) {
vector<int> state(N), depth(N);
vector<int> cycle1, cycle2;
int length = -1;
for (int v = u, e = next[0];;) {
state[v] = 1;
v = other(v, e);
cycle1.push_back(e);
if (state[v]) {
append(cycle1, rev(slice(cycle1, 0, depth[v])));
length = depth[v];
break;
} else {
depth[v] = depth[other(v, e)] + 1;
for (const int f : G[v]) {
if (!dead[other(v, f)]) e = f;
}
}
}
vector<int> cycle;
for (int v = u, e = next[1];;) {
state[v] = 2;
v = other(v, e);
cycle2.push_back(e);
if (state[v] == 1) {
append(cycle, cycle1);
append(cycle, cycle2);
if (depth[v] <= length) {
append(cycle, slice(cycle1, depth[v], length));
} else {
append(cycle, rev(slice(cycle1, length, depth[v])));
}
append(cycle, rev(slice(cycle1, depth[v], (int)cycle1.size() - length)));
append(cycle, rev(cycle2));
break;
} else if (state[v] == 2) {
append(cycle2, rev(slice(cycle2, 0, depth[v])));
append(cycle, cycle1);
append(cycle, cycle2);
append(cycle, rev(cycle1));
append(cycle, rev(cycle2));
break;
} else {
depth[v] = depth[other(v, e)] + 1;
for (const int f : G[v]) {
if (!dead[other(v, f)]) e = f;
}
}
}
vector<int> ret;
append(ret, path);
append(ret, cycle);
append(ret, rev(path));
return ret;
} else {
out[u] = 0;
que.push(u);
clean();
const int e = next[0];
path.push_back(e);
u = other(u, e);
}
}
}
