#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX 201010
int deg[MAX];
vector<int> adj[MAX];
vector<int> radj[MAX];
int chk[MAX];
int vis[MAX];
vector<int> U, V;
int N, M;
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
int i;
::N = N;
::M = M;
::U = U;
::V = V;
for (i = 0; i < M; i++) deg[U[i]]++, adj[U[i]].push_back(i), radj[V[i]].push_back(U[i]);
queue<int> q;
for (i = 0; i < N; i++) if (!deg[i]) q.push(i);
int s = 0;
vector<int> st;
while (1) {
while (q.size()) {
int t = q.front();
chk[t] = 1;
q.pop();
for (auto v : radj[t]) if (!chk[v]) {
deg[v]--;
if (deg[v] == 0) q.push(v);
}
}
if (deg[s] <= 1) {
if (deg[s] == 0) return false;
for (auto n : adj[s]) {
if (!chk[V[n]]) {
for (auto v : radj[s]) if (!chk[v]) {
deg[v]--;
if (deg[v] == 0) q.push(v);
}
chk[s] = 1;
s = V[n];
st.push_back(n);
break;
}
}
if (deg[s] == 0) return false;
continue;
}
else break;
}
vector<int> ans = st;
int a, b;
a = b = -1;
for (auto n : adj[s]) if (!chk[V[n]]) b = a, a = n;
vector<int> p1, p2, cyc1, cyc2;
int v;
p1.push_back(a);
v = V[a];
vis[a] = 1;
while (1) {
int nn, x;
for (auto n : adj[v]) {
x = V[n];
if (chk[x]) continue;
nn = n;
break;
}
if (vis[nn]) {
while (p1.size()) {
cyc1.push_back(p1.back());
if (p1.back() == nn) {
p1.pop_back();
break;
}
p1.pop_back();
}
reverse(cyc1.begin(), cyc1.end());
break;
}
p1.push_back(nn);
vis[nn] = 1;
v = x;
}
end1:
memset(vis, 0, sizeof(vis));
p2.push_back(b);
v = V[b];
vis[b] = 1;
while (1) {
int nn, x;
for (auto n : adj[v]) {
x = V[n];
if (chk[x]) continue;
nn = n;
break;
}
if (vis[nn]) {
while (p2.size()) {
cyc2.push_back(p2.back());
if (p2.back() == nn) {
p2.pop_back();
break;
}
p2.pop_back();
}
reverse(cyc2.begin(), cyc2.end());
break;
}
p2.push_back(nn);
vis[nn] = 1;
v = x;
}
end2:
memset(vis, 0, sizeof(vis));
for (auto v : cyc1) vis[v] = 1;
int c = 0;
for (auto v : cyc2) if (vis[v]) c = 1;
for (auto v : p1) ans.push_back(v);
for (auto v : cyc1) ans.push_back(v);
reverse(p1.begin(), p1.end());
for (auto v : p1) ans.push_back(v);
reverse(p1.begin(), p1.end());
for (auto v : p2) ans.push_back(v);
if (c) reverse(cyc2.begin(), cyc2.end());
for (auto v : cyc2) ans.push_back(v);
if (c) reverse(cyc2.begin(), cyc2.end());
reverse(p2.begin(), p2.end());
for (auto v : p2) ans.push_back(v);
reverse(p2.begin(), p2.end());
if (c) {
reverse(st.begin(), st.end());
for (auto v : st) ans.push_back(v);
return ans;
}
for (auto v : p1) ans.push_back(v);
reverse(cyc1.begin(), cyc1.end());
for (auto v : cyc1) ans.push_back(v);
reverse(cyc1.begin(), cyc1.end());
reverse(p1.begin(), p1.end());
for (auto v : p1) ans.push_back(v);
reverse(p1.begin(), p1.end());
for (auto v : p2) ans.push_back(v);
reverse(cyc2.begin(), cyc2.end());
for (auto v : cyc2) ans.push_back(v);
reverse(cyc2.begin(), cyc2.end());
reverse(p2.begin(), p2.end());
for (auto v : p2) ans.push_back(v);
reverse(p2.begin(), p2.end());
reverse(st.begin(), st.end());
for (auto v : st) ans.push_back(v);
return ans;
}
