#include "islands.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
int out_deg[100001];
vi in_graph[100001];
bool del[100001];
vector<pii> out_graph[100001];
queue<int> events;
vi ans;
int beg_path_siz = 0;
bool odw[100001];
bool in_cycle[200001];
pii edge[200001];
void del_vert(int x)
{
del[x] = 1;
forall(it,in_graph[x])
{
out_deg[it]--;
if(out_deg[it] == 0) events.push(it);
}
}
int new_beg(int v)
{
int v2 = -1;
forall(it,out_graph[v])
{
if(del[it.ff]) continue;
v2 = it.ff;
beg_path_siz++;
ans.pb(it.ss);
}
del_vert(v);
return v2;
}
pair<vi,vi> find_cycle(int v, int beg, int beg_edge, int n)
{
vi ans2 = {beg_edge};
rep(i,n) odw[i] = 0;
odw[beg] = 1;
while(odw[v] == 0)
{
ans2.pb(out_graph[v][0].ss);
odw[v] = 1;
v = out_graph[v][0].ff;
}
vi cycle = {ans2.back()};
vi path = {};
for(int i = siz(ans2)-2; i >= 0; i--)
{
cycle.pb(ans2[i]);
if(edge[ans2[i]].ff == v)
{
for(int j = 0; j < i; j++) path.pb(ans2[j]);
break;
}
}
reverse(all(cycle));
return {path,cycle};
}
variant<bool,vi> find_journey(int n, int m, vi u, vi v)
//vi find_journey(int n, int m, vi u, vi v)
{
rep(i,m)
{
edge[i] = {u[i],v[i]};
out_graph[u[i]].pb({v[i],i});
}
rep(i,m)
{
out_deg[u[i]]++;
in_graph[v[i]].pb(u[i]);
}
rep(i,n)
{
if(out_deg[i] == 0) events.push(i);
}
int cur_beg = 0;
while(out_deg[cur_beg] <= 1)
{
int nb = new_beg(cur_beg);
if(nb == -1) return (bool)0;
cur_beg = nb;
}
while(!events.empty())
{
int x = events.front();
events.pop();
if(del[x]) continue;
del_vert(x);
while(out_deg[cur_beg] <= 1)
{
int nb = new_beg(cur_beg);
if(nb == -1) return (bool)0;
cur_beg = nb;
}
}
rep(i,n) out_graph[i] = {};
rep(i,m)
{
if(del[u[i]] || del[v[i]]) continue;
out_graph[u[i]].pb({v[i],i});
}
pair<vi,vi> cycle1 = find_cycle(out_graph[cur_beg][0].ff,cur_beg,out_graph[cur_beg][0].ss,n);
pair<vi,vi> cycle2 = find_cycle(out_graph[cur_beg][1].ff,cur_beg,out_graph[cur_beg][1].ss,n);
forall(it,cycle1.ss) in_cycle[it] = 1;
bool is_case = 0;
forall(it,cycle2.ss) if(in_cycle[it]) is_case = 1;
if(is_case)
{
forall(it,cycle1.ff) ans.pb(it);
forall(it,cycle1.ss) ans.pb(it);
reverse(all(cycle1.ff));
forall(it,cycle1.ff) ans.pb(it);
vi path = cycle2.ff;
if(siz(cycle2.ff) == 0)
{
rep(i,siz(cycle2.ss))
{
if(in_cycle[cycle2.ss[i]]) break;
path.pb(cycle2.ss[i]);
}
}
forall(it,path) ans.pb(it);
int beg_edge;
rep(i,siz(cycle1.ss))
{
int it = cycle1.ss[i];
if(edge[it].ff == edge[path.back()].ss)
{
beg_edge = i;
}
}
int cnt = siz(cycle1.ss);
vi new_cycle;
while(cnt--)
{
new_cycle.pb(cycle1.ss[beg_edge]);
beg_edge++;
beg_edge %= siz(cycle1.ss);
}
reverse(all(new_cycle));
forall(it,new_cycle) ans.pb(it);
reverse(all(path));
forall(it,path) ans.pb(it);
}
else
{
forall(it,cycle1.ff) ans.pb(it);
forall(it,cycle1.ss) ans.pb(it);
reverse(all(cycle1.ff));
forall(it,cycle1.ff) ans.pb(it);
reverse(all(cycle1.ff));
forall(it,cycle2.ff) ans.pb(it);
forall(it,cycle2.ss) ans.pb(it);
reverse(all(cycle2.ff));
forall(it,cycle2.ff) ans.pb(it);
reverse(all(cycle2.ff));
forall(it,cycle1.ff) ans.pb(it);
reverse(all(cycle1.ss));
forall(it,cycle1.ss) ans.pb(it);
reverse(all(cycle1.ff));
forall(it,cycle1.ff) ans.pb(it);
reverse(all(cycle1.ff));
forall(it,cycle2.ff) ans.pb(it);
reverse(all(cycle2.ss));
forall(it,cycle2.ss) ans.pb(it);
reverse(all(cycle2.ff));
forall(it,cycle2.ff) ans.pb(it);
reverse(all(cycle2.ff));
}
for(int i = beg_path_siz-1; i >= 0; i--)
{
ans.pb(ans[i]);
}
return ans;
}
