#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
#define sz(x) int(x.size())
const int mx = 100'000;
vpii edge[mx];
vpii revedge[mx];
int N, M;
queue<int> tbv;
int src = 0;
vi pushed(mx, 0);
vi killed(mx, 0);
vi outdeg(mx, 0);
vi incedge(mx, -1);
void addvec(vi& a, vi& b)
{
for(int u : b)
a.push_back(u);
}
void rev(vi& a)
{
reverse(a.begin(), a.end());
}
void addrev(vi& a, vi& b)
{
rev(b);
addvec(a, b);
rev(b);
}
vi nodevis(mx, 0);
vi cyclic(mx, 0);
bool samecycle = 0;
vi lst1, nodelst1, cyc1, nodecyc1;
int bannededge;
void dfs1(int u)
{
for(pii vp : edge[u])
{
int v = vp.first;
if(killed[v])
continue;
if(nodevis[v] == 0)
{
lst1.push_back(vp.second);
nodelst1.push_back(vp.first);
if(u == src)
bannededge = vp.second;
nodevis[v] = 1;
dfs1(v);
}
else if(nodevis[v] == 1)
{
// samecycle = 1;
nodecyc1.push_back(v);
cyclic[v] = 1;
cyc1.push_back(vp.second);
while(1)
{
if(nodelst1.back() == v)
break;
nodecyc1.push_back(nodelst1.back());
cyclic[nodelst1.back()] = 1;
cyc1.push_back(lst1.back());
nodelst1.pop_back();
lst1.pop_back();
}
rev(nodecyc1);
rev(cyc1);
}
return;
}
}
vi lst2, cyc2, nodelst2, nodecyc2;
void dfs2(int u)
{
for(pii vp : edge[u])
{
if(vp.second == bannededge)
continue;
int v = vp.first;
if(killed[v])
continue;
if(nodevis[v] == 0)
{
lst2.push_back(vp.second);
nodelst2.push_back(vp.first);
if(u == src)
bannededge = vp.second;
nodevis[v] = 2;
dfs2(v);
}
else if(nodevis[v] == 2)
{
nodecyc2.push_back(v);
cyc2.push_back(vp.second);
while(1)
{
if(nodelst2.back() == v)
break;
nodecyc2.push_back(nodelst2.back());
cyc2.push_back(lst2.back());
nodelst2.pop_back();
lst2.pop_back();
}
rev(nodecyc2);
rev(cyc2);
}
else if(nodevis[v] == 1 && !cyclic[v])
{
samecycle = 1;
nodecyc2 = nodecyc1;
cyc2 = cyc1;
// cerr << "no"
int id = 0;
while(nodelst1[id] != v)
id++;
nodelst2.push_back(v);
lst2.push_back(vp.second);
for(id++; id < sz(nodelst1); id++)
{
nodelst2.push_back(nodelst1[id]);
lst2.push_back(lst1[id-1]);
}
}
else if(nodevis[v] == 1 && cyclic[v])
{
samecycle = 1;
lst2.push_back(vp.second);
int z = 0;
while(nodecyc1[z] != v)
z++;
for(int f = z+1; f < sz(cyc1); f++)
{
cyc2.push_back(cyc1[f]);
nodecyc2.push_back(nodecyc1[f]);
}
for(int f = 0; f <= z; f++)
{
cyc2.push_back(cyc1[f]);
nodecyc2.push_back(nodecyc1[f]);
}
}
return;
}
}
variant<bool, vi> find_journey(int N_, int M_, vi U, vi V)
{
N = N_;
M = M_;
for(int j = 0; j < M; j++)
{
edge[U[j]].push_back({V[j], j});
revedge[V[j]].push_back({U[j], j});
outdeg[U[j]]++;
}
for(int i = 0; i < N; i++)
{
if(outdeg[i] == 0)
{
pushed[i] = 1;
tbv.push(i);
}
}
if(pushed[src])
{
return false;
}
vi originlist;
while(1)
{
if(!tbv.empty())
{
int u = tbv.front();
tbv.pop();
killed[u] = 1;
for(pii vp : revedge[u])
{
int v = vp.first;
outdeg[v]--;
if(outdeg[v] == 0)
{
pushed[v] = 1;
if(v == src)
{
// gettime();
return false;
}
tbv.push(v);
}
}
}
else if(outdeg[src] == 1)
{
int newsrc;
for(pii vp : edge[src])
{
if(!pushed[vp.first])
{
newsrc = vp.first;
incedge[newsrc] = vp.second;
originlist.push_back(vp.second);
break;
}
}
pushed[src] = 1;
killed[src] = 1;
for(pii vp : revedge[src])
{
int v = vp.first;
if(vp.second == incedge[src])
continue;
outdeg[v]--;
if(outdeg[v] == 0)
{
pushed[v] = 1;
if(pushed[newsrc])
return false;
tbv.push(v);
}
}
src = newsrc;
}
else
{
break;
}
}
nodevis[src] = 1;
nodelst1.push_back(src);
dfs1(src);
nodelst2.push_back(src);
dfs2(src);
vi res;
if(!samecycle)
{
addvec(res, originlist);
addvec(res, lst1);
addvec(res, cyc1);
addrev(res, lst1);
addvec(res, lst2);
addvec(res, cyc2);
addrev(res, lst2);
addvec(res, lst1);
addrev(res, cyc1);
addrev(res, lst1);
addvec(res, lst2);
addrev(res, cyc2);
addrev(res, lst2);
addrev(res, originlist);
}
else
{
addvec(res, originlist);
addvec(res, lst1);
addvec(res, cyc1);
addrev(res, lst1);
addvec(res, lst2);
addrev(res, cyc2);
addrev(res, lst2);
addrev(res, originlist);
}
return res;
}
