#include "islands.h"
#include <iostream>
#include <variant>
#include <vector>
#include <map>
#define ll long long
using namespace std;
bool visited[100000];
bool B[100000], done[100000];
map <ll, ll> mp;
ll id[100000];
vector <array<ll, 2> > adj[100000];
vector <ll> X, C, F, G;
vector <int> ans;
ll k;
ll search(ll u) {
++mp[u];
visited[u] = k;
while (id[u] < adj[u].size()) {
ll v = adj[u][id[u]++][0];
if (done[v]) continue;
G.push_back(adj[u][id[u]-1][1]);
if (B[v]) return 1;
else if (visited[v] == k) {
return 2;
}
else if (!visited[v]) {
ll res = search(v);
if (res) return res;
}
G.pop_back();
}
return 0;
}
ll dfs(ll u) {
++mp[u];
visited[u] = 1;
while (id[u] < adj[u].size()) {
ll v = adj[u][id[u]++][0];
if (done[v]) continue;
F.push_back(adj[u][id[u]-1][1]);
if (visited[v] == 1) {
C.push_back(u);
B[u] = 1;
return v;
}
else if (visited[v] == 0) {
ll ret = dfs(v);
if (ret == -2) {
B[u] = 1;
X.push_back(u);
return -2;
}
else if (ret != -1) {
B[u] = 1;
if (ret != u) {
C.push_back(u);
return ret;
}
else {
X.push_back(u);
return -2;
}
}
}
F.pop_back();
}
return -1;
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
X.clear();
C.clear();
F.clear();
G.clear();
mp.clear();
ans.clear();
k = 2;
for (int i=0; i<N; ++i) visited[i] = B[i] = done[i] = id[i] = 0;
for (int i=0; i<M; ++i) {
adj[U[i]].push_back({V[i], i});
}
ll nx = 0;
while (dfs(nx) == -2) {
while (!X.empty()) {
auto u = X.back();
X.pop_back();
ll res = search(u);
if (res) {
for (auto v : F) ans.push_back(v);
bool ok = 0;
vector <int> tmp, cyc;
for (auto v : F) {
if (U[v] == V[F.back()]) ok = 1;
if (ok) cyc.push_back(v);
}
ok = 0;
for (auto v : F) {
if (U[v] == u) ok = 1;
if (U[v] == V[F.back()]) ok = 0;
if (ok) tmp.push_back(v);
}
for (int i = (ll)tmp.size()-1; i>=0; --i) {
ans.push_back(tmp[i]);
}
for (auto v : G) ans.push_back(v);
if (res == 1) {
ok = 0;
ll start = -1;
for (auto v : F) {
if (U[v] == V[G.back()]) ok = 1;
if (U[v] == V[F.back()]) {
if (ok) start = U[v];
break;
}
if (ok) ans.push_back(v);
}
if (start == -1) start = V[G.back()];
ok = 0;
for (int i=cyc.size()-1; i>=0; --i) {
if (V[cyc[i]] == start) ok = 1;
if (ok) ans.push_back(cyc[i]);
}
if (start != U[cyc[0]]) {
for (int i=cyc.size()-1; i>=0; --i) {
ans.push_back(cyc[i]);
if (U[cyc[i]] == start) break;
}
}
for (int i=G.size()-1; i>=0; --i) ans.push_back(G[i]);
ok = 0;
for (int i=F.size()-2; i>=0; --i) {
if (V[F[i]] == u) ok = 1;
if (ok) ans.push_back(F[i]);
}
}
else {
ok = 0;
for (int i=G.size()-2; i>=0; --i) {
if (V[G[i]] == V[G.back()]) ok = 1;
if (ok) ans.push_back(G[i]);
}
ok = 0;
for (auto v : F) {
if (U[v] == u) ok = 1;
if (U[v] == V[F.back()]) break;
if (ok) ans.push_back(v);
}
for (int i=F.size()-1; i>=0; --i) {
ans.push_back(F[i]);
if (U[F[i]] == u) break;
}
for (auto v : G) {
if (U[v] == V[G.back()]) break;
ans.push_back(v);
}
for (int i=G.size()-1; i>=0; --i) {
ans.push_back(G[i]);
if (U[G[i]] == u) break;
}
ok = 0;
for (int i=F.size()-2; i>=0; --i) {
if (V[F[i]] == u) ok = 1;
if (ok) ans.push_back(F[i]);
}
}
return ans;
}
B[u] = 0;
++k;
}
for (auto u : C) {
B[u] = 0;
--id[u];
mp.erase(u);
}
for (auto [x, y] : mp) {
done[x] = 1;
}
mp.clear();
nx = C.back();
C.clear();
G.clear();
while (!F.empty()) {
auto u = F.back();
if (V[u] != nx) F.pop_back();
else break;
}
}
return false;
}
