#include "islands.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
vector<int> join(vector<int> v, vector<int> o, bool rev = false) {
if(rev) reverse(all(o));
v.insert(v.end(), all(o));
return v;
}
const int MAXN = 100'000;
const int MAXM = 200'000;
vector<pii> adj[MAXN + 10];
vector<pii> rev[MAXN + 10]; // {node, edge id}
int scc[MAXN + 10];
pii path_to_0[MAXN + 10]; // how can node 0 reach this node? {node, edge id}
int vcnt[MAXN + 10]; // count of nodes
int ecnt[MAXN + 10]; // count of internal edges
int fi[MAXN + 10]; // first person on path to node 0
vector<int> stk;
void dfs1(int n) {
scc[n] = -1;
for(auto &e:rev[n]) if(scc[e.F] == 0) {
dfs1(e.F);
}
stk.eb(n);
}
void dfs2(int n, int id) {
scc[n] = id;
vcnt[id]++;
for(auto &e:adj[n]) {
if(scc[e.F] == -1) dfs2(e.F, id);
if(scc[e.F] == scc[n]) {
ecnt[id]++;
}
}
}
void dfs_node0(int n) {
// cerr << "owo? " << n << " " << scc[n] << " " << fi[scc[n]] << "\n";
if(fi[scc[n]] < 0) fi[scc[n]] = n;
for(auto &e:adj[n]) if(path_to_0[e.F].F == -1) {
path_to_0[e.F] = pii(n, e.S);
dfs_node0(e.F);
}
}
pii par[MAXN + 10]; // {node, edge id}
int dep[MAXN + 10];
pii back_edge;
void dfs8(int n, int sccid, const set<int> &ban) {
for(auto &i:adj[n]) if(scc[i.F] == sccid && !ban.count(i.S)) {
if(dep[i.F] == 1) {
back_edge = pii(n, i.S);
} else if(dep[i.F] != 0) {
;
} else {
par[i.F] = pii(n, i.S);
dep[i.F] = dep[n] + 1;
dfs8(i.F, sccid, ban);
}
}
}
vector<int> find_cycle(int s, int sccid, vector<int> vban) {
set<int> ban;
for(auto &i:vban) ban.insert(i);
fill(par, par + MAXN + 10, pii(-1, -1));
memset(dep, 0, sizeof(dep));
par[s] = pii(-8, -8);
dep[s] = 1;
back_edge = pii(-8, -8);
dfs8(s, sccid, ban);
// For(i, 0, 1) cerr << par[i].F << " \n"[i == 1];
// For(i, 0, 1) cerr << par[i].F << " \n"[i == 1];
// For(i, 0, 1) cerr << dep[i] << " \n"[i == 1];
assert(back_edge.F != -8);
vector<int> cyc;
cyc.eb(back_edge.S);
int cur = back_edge.F;
while(cur != s) {
cyc.eb(par[cur].S);
cur = par[cur].F;
}
reverse(all(cyc));
return cyc;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
// if (N == 4) {
// return vector<int>({0, 1, 2, 4, 0, 3, 2, 1, 4, 3});
// }
// return false;
For(i, 0, M - 1) {
int x = U[i], y = V[i];
adj[x].eb(y, i);
rev[y].eb(x, i);
}
memset(scc, 0, sizeof(scc));
For(i, 0, N - 1) if(scc[i] == 0) dfs1(i);
int sccid = 0;
while(sz(stk)) {
sccid++;
dfs2(stk.back(), sccid);
while(sz(stk) && scc[stk.back()] != -1) stk.pop_back();
}
fill(fi, fi + MAXN + 10, -1);
fill(path_to_0, path_to_0 + MAXN + 10, pii(-1, -1));
path_to_0[0] = pii(-8, -8);
dfs_node0(0);
int good_id = -1;
For(i, 1, sccid) if(fi[i] != -1 && ecnt[i] > vcnt[i]) {
good_id = i; break;
}
// For(i, 0, N - 1) cerr << scc[i] << " \n"[i == N - 1];
// For(i, 1, sccid) cerr << fi[i] << " \n"[i == sccid];
// For(i, 0, N - 1) cerr << path_to_0[i].F << " \n"[i == N - 1];
if(good_id < 0) return false;
vector<int> cy1 = find_cycle(fi[good_id], good_id, {});
vector<int> cy2 = find_cycle(fi[good_id], good_id, cy1);
// for(auto &i:cy1) cerr << i << " ";
// cerr << "\n";
// for(auto &i:cy2) cerr << i << " ";
// cerr << "\n";
vector<int> chain;
{
int cur = fi[good_id];
while(cur != 0) {
chain.eb(path_to_0[cur].S);
cur = path_to_0[cur].F;
}
reverse(all(chain));
}
vector<int> ans;
ans = join(ans, chain);
ans = join(ans, cy1);
ans = join(ans, cy2);
ans = join(ans, cy1, true);
ans = join(ans, cy2, true);
ans = join(ans, chain, true);
return ans;
}
/*
4 5
0 1
1 2
2 3
0 3
3 1
1
10
0 1 2 4 0 3 2 1 4 3
2 3
0 1
1 0
1 0
0
0
*/
