#include "islands.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
const int MAXN = 1e5+5;
int st, deg[MAXN], vis[MAXN], len[6];
pii nxt[MAXN];
bool stop;
vector <int> in[MAXN], ans;
vector <pii> out[MAXN];
void del(int x) {
deg[x]--;
for (int y : in[x]) {
deg[y]--;
if (!deg[y]) {
del(y);
}
}
}
pii find(int x) {
for (pii y : out[x]) {
if (deg[y.fi] > 0) {
return y;
}
}
return {-1,-1};
}
void goback(int x) {
vector <int> r;
int y = x;
do {
r.push_back(nxt[y].se);
y = nxt[y].fi;
}
while (y != x);
reverse(r.begin(),r.end());
for (int a : r) {
ans.push_back(a);
}
}
void resail(int x) {
vis[x] += 2;
if (vis[x] == 3) {
goback(x);
stop = 1;
vis[x] = 0;
return;
}
if (vis[x] == 4) {
len[4] = ans.size();
return;
}
int z = ans.size();
ans.push_back(nxt[x].se);
resail(nxt[x].fi);
if (vis[x] == 4) {
vis[x] = 0;
len[3] = z;
}
if (vis[nxt[x].fi] == 0) {
vis[x] = 0;
ans.push_back(nxt[x].se);
}
}
void sail(int x) {
vis[x]++;
if (vis[x] == 2) {
len[2] = ans.size();
return;
}
int z = ans.size();
ans.push_back(nxt[x].se);
sail(nxt[x].fi);
if (vis[x] == 2) {
vis[x] = 3;
len[1] = z;
}
if (vis[nxt[x].fi] == 3 || vis[nxt[x].fi] == 0) {
if (vis[nxt[x].fi] == 3) {
vis[nxt[x].fi] = 1;
}
vis[x] = 0;
ans.push_back(nxt[x].se);
}
}
variant<bool,vector<int>> find_journey(int N,int M,vector<int>U,vector<int>V) {
for (int i=0;i<M;i++) {
deg[U[i]]++;
in[V[i]].push_back(U[i]);
out[U[i]].push_back({V[i],i});
}
for (int i=0;i<N;i++) {
if (!deg[i]) {
del(i);
}
}
while (deg[st] < 2) {
if (deg[st] < 1) {
return false;
}
pii x = find(st);
del(st);
st = x.fi;
ans.push_back(x.se);
}
len[0] = ans.size();
for (int i=0;i<N;i++) {
if (deg[i] > 0) {
nxt[i] = find(i);
}
}
for (pii y : out[st]) {
if (deg[y.fi] > 0) {
nxt[N] = y;
}
}
sail(st);
if (vis[st] == 3) {
vis[st] = 1;
}
ans.push_back(nxt[N].se);
resail(nxt[N].fi);
ans.push_back(nxt[N].se);
len[5] = ans.size();
if (!stop) {
for (int i=len[0];i<len[1];i++) {
ans.push_back(ans[i]);
}
for (int i=len[2]-1;i>=len[1];i--) {
ans.push_back(ans[i]);
}
for (int i=len[2];i<len[3];i++) {
ans.push_back(ans[i]);
}
for (int i=len[4]-1;i>=len[3];i--) {
ans.push_back(ans[i]);
}
for (int i=len[4];i<len[5];i++) {
ans.push_back(ans[i]);
}
}
for (int i=len[0]-1;i>=0;i--) {
ans.push_back(ans[i]);
}
return ans;
}
