#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;
const int MAXN = 100100*1;
const ll MOD = 998244353;
const ll INF = 2e9;
queue<int> q;
vector<pi> adj[MAXN], adjt[MAXN];
int ind[MAXN];
int chk[MAXN];
void clean() {
while(q.size()) {
int here = q.front(); q.pop();
for(auto [there, x] : adjt[here]) {
ind[there]--;
if(ind[there] == 0) q.push(there);
}
}
}
vector<int> tmp, res;
vector<pi> pathA, cycleA, pathB, cycleB;
bool flag;
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
for(int i=0; i<M; i++) {
adj[U[i]].push_back(pi(V[i], i));
adjt[V[i]].push_back(pi(U[i], i));
ind[V[i]]++;
}
for(int i=0; i<N; i++) {
if(adj[i].empty()) q.push(i);
} clean();
// if 0 erased then return false
if(adj[0].empty()) return false;
int here = 0;
while(true) {
if(adj[here].empty()) return false;
if(adj[here].size() == 1) {
auto [there, x] = adj[here][0];
q.push(here); clean();
tmp.push_back(x); here = there; continue;
}
// first cycle
chk[here] = 1;
int there = adj[here][0].ff, x = adj[here][0].ss;
pathA.push_back(pi(here, x));
while(true) {
if(chk[there]) {
while(true) {
cycleA.push_back(*pathA.rbegin());
pathA.pop_back();
if(cycleA.rbegin()->ff == there) break;
}
break;
}
chk[there] = 1;
pathA.push_back(pi(there, 0));
x = adj[there][0].ss, there = adj[there][0].ff;
pathA.rbegin()->ss = x;
} reverse(all(cycleA));
// second cycle
memset(chk, 0, sizeof chk);
for(auto [there,x] : cycleA) chk[there] = -1;
chk[here] = 1;
there = adj[here][1].ff, x = adj[here][1].ss;
pathB.push_back(pi(here, x));
while(true) {
if(chk[there] == 1) { // find new cycle
while(true) {
cycleB.push_back(*pathB.rbegin());
pathB.pop_back();
if(cycleB.rbegin()->ff == there) break;
} reverse(all(cycleB));
break;
} else if(chk[there] == -1) { // find first cycle
int j=0; flag = 1;
while(cycleA[j].ff!=there) j++;
int sz=cycleA.size();
for(int k=0; k<sz; k++) {
j=(j-1+sz)%sz;
cycleB.push_back(cycleA[j]);
}
break;
}
chk[there] = 1;
pathB.push_back(pi(there, 0));
x = adj[there][0].ss, there = adj[there][0].ff;
pathB.rbegin()->ss = x;
}
break;
}
for(int x:tmp) res.push_back(x); reverse(all(tmp));
int cnt = (flag ? 1 : 2);
while(cnt--) {
for(auto [there,x]:pathA) res.push_back(x); reverse(all(pathA));
for(auto [there,x]:cycleA) res.push_back(x); reverse(all(cycleA));
for(auto [there,x]:pathA) res.push_back(x); reverse(all(pathA));
for(auto [there,x]:pathB) res.push_back(x); reverse(all(pathB));
for(auto [there,x]:cycleB) res.push_back(x); reverse(all(cycleB));
for(auto [there,x]:pathB) res.push_back(x); reverse(all(pathB));
}
for(int x:tmp) res.push_back(x);
return res;
}
