#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 gettime()
{
for(int j = 1; j <= 500'000; j++)
cerr << "hello world\n";
}
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;
vi nodelst1;
vi cyc1;
vi 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;
vi cyc2;
vi nodelst2;
vi nodecyc2;
void dfs2(int u)
{
// cerr << "dfs2 " << u << '\n';
for(pii vp : edge[u])
{
if(vp.second == bannededge)
continue;
int v = vp.first;
// cerr << u << " -> " << v << " via " << vp.second << '\n';
// cerr << cyclic[v] << ' ' << nodevis[v] << '\n';
if(killed[v])
continue;
// cerr << "#\n";
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)
{
// cerr << "??\n";
nodecyc2.push_back(v);
cyc2.push_back(vp.second);
// cerr << "v = " << v << '\n';
// cerr <
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);
// cerr << "reached end\n";
}
else if(nodevis[v] == 1 && !cyclic[v])
{
// cerr << "^^^\n";
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])
{
// cerr << "hello\n";
samecycle = 1;
lst2.push_back(vp.second);
int z = 0;
while(nodecyc1[z] != v)
z++;
// cerr << "v = " << v << '\n';
// cerr << "nodecyc1 = ";
// for(int y : nodecyc1)
// cerr << y << ' ';
// cerr << '\n';
// cerr << "cyc1 = ";
// for(int y : cyc1)
// cerr << y << ' ';
// cerr << '\n';
// cerr << "z = " << z << '\n';
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;
}
}
void testarray(vi U, vi V, vi res)
{
vi inv(M, 0);
int lst = -1;
int loc = 0;
string err;
for(int r : res)
{
if(U[r] != loc && V[r] != loc)
err = "Canoe doesn't travel to current source";
else if(U[r] != loc)
err = "Canoe not currently docked at source";
else if(lst == r)
err = "Canoe used consecutively";
cerr << "take " << r << " : " << U[r] << " -> " << V[r] << '\n';
if(!err.empty())
{
cerr << err << '\n';
while(1);
}
loc = V[r];
swap(U[r], V[r]);
inv[r] = !inv[r];
lst = r;
}
if(loc != 0)
err = "Didn't return to 0";
for(int j = 0; j < M; j++)
if(inv[j])
err = "Canoe not docked at initial location";
if(!err.empty())
{
cerr << err << '\n';
while(1);
}
}
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])
{
// gettime();
return false;
}
// cerr << "A\n";
vi originlist;
// cerr << sz(tbv) << " ! \n";
// cerr << "outdeg 1 = " << outdeg[1] << '\n';
while(1)
{
if(!tbv.empty())
{
int u = tbv.front();
tbv.pop();
killed[u] = 1;
for(pii vp : revedge[u])
{
int v = vp.first;
// cerr << "remove out edge from " << v << " to del node = " << u << ", edge ind = " << vp.second << '\n';
outdeg[v]--;
// cerr << "outdeg " << v << " = " << outdeg[v] << '\n';
if(outdeg[v] == 0)
{
pushed[v] = 1;
if(v == src)
{
// gettime();
return false;
}
tbv.push(v);
// cerr << "push " << v << " to killing queue\n";
}
}
}
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;
// cerr << "remove out edge from " << v << " to src = " << src << ", edge ind = " << vp.second << '\n';
outdeg[v]--;
// cerr << "outdeg " << v << " = " << outdeg[v] << '\n';
if(outdeg[v] == 0)
{
pushed[v] = 1;
if(pushed[newsrc])
return false;
tbv.push(v);
// cerr << "push " << v << " to killing queue\n";
}
}
// cerr << src << " -> " << newsrc << '\n';
src = newsrc;
}
else
{
break;
}
}
// cerr << "B\n";
// cerr << "src = " << src << '\n';
nodevis[src] = 1;
nodelst1.push_back(src);
dfs1(src);
// cerr << "nodelst1 = ";
// for(int p : nodelst1)
// cerr << p << ' ';
// cerr << '\n';
// cerr << "nodecyc1 = ";
// for(int p : nodecyc1)
// cerr << p << ' ';
// cerr << '\n';
// cerr << "lst1 = ";
// for(int p : lst1)
// cerr << p << ' ';
// cerr << '\n';
// cerr << "cyc1 = ";
// for(int p : cyc1)
// cerr << p << ' ';
// cerr << '\n';
// cerr << "C\n";
// cerr << "bannededge = " << bannededge << '\n';
nodelst2.push_back(src);
dfs2(src);
// cerr << "\n\n\n";
// cerr << "nodelst2 = ";
// for(int p : nodelst2)
// cerr << p << ' ';
// cerr << '\n';
// cerr << "nodecyc2 = ";
// for(int p : nodecyc2)
// cerr << p << ' ';
// cerr << '\n';
// cerr << "lst2 = ";
// for(int p : lst2)
// cerr << p << ' ';
// cerr << '\n';
// cerr << "cyc2 = ";
// for(int p : cyc2)
// cerr << p << ' ';
// cerr << '\n';
// cerr << "D\n";
vi res;
// if(!samecycle)
{
// cerr << "diff cycle\n";
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
// {
// // cerr << "samecycle\n";
// addvec(res, originlist);
// addvec(res, lst1);
// addvec(res, cyc1);
// addrev(res, lst1);
// addvec(res, lst2);
// addrev(res, cyc2);
// addrev(res, lst2);
// addrev(res, originlist);
// }
// cerr << "E\n";
// testarray(U, V, res);
return res;
}
