#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5;
vector<pii> edges[MAXN];
vector<pii> redges[MAXN];
bool dead[MAXN];
int outdeg[MAXN];
pii edge_list[MAXN];
int n, m;
vector<int> path;
bool vis[MAXN];
bool fin[MAXN];
void prune(int i) {
dead[i] = 1;
for (pii e: redges[i]) {
if (dead[e.first]) continue;
outdeg[e.first]--;
if (outdeg[e.first] == 0) prune(e.first);
}
}
pii nxt[MAXN];
pii prv[MAXN];
pii prv2[MAXN];
int pinch[MAXN];
void make_path(int cur, vector<int> &cpath, bool spec = 0) {
if (spec) {
make_path(prv2[cur].first, cpath);
cpath.push_back(prv2[cur].second);
return;
}
if (cur == 0) return;
make_path(prv[cur].first, cpath);
cpath.push_back(prv[cur].second);
}
set<int> cyc_less;
// set<int> all_prev;
int pinch_f;
bool dfs(int cur) {
vis[cur] = 1;
if (pinch[cur] == -1) cyc_less.insert(cur);
// all_prev.insert(cur);
for (pii e: edges[cur]) {
if (dead[e.first]) continue;
if (pinch[e.first] != -1) {
// int abssfae = 0;
// while (nxt[pinch[e.first]].first == -1) abssfae++;
if (!fin[nxt[pinch[e.first]].first]) continue;
// make_path(cur, path);
// path.push_back(e.second);
// pinch_f = pinch[e.first];
return 1;
}
if (fin[e.first]) continue;
if (vis[e.first]) {
for (int v: cyc_less) {
pinch[v] = e.first;
}
cyc_less.clear();
int abssfae = 0;
while (pinch[cur] == -1) abssfae++;
prv2[pinch[cur]] = e;
nxt[cur] = e;
continue;
}
prv[e.first] = pii(cur, e.second);
if (dfs(e.first)) return 1;
}
if (cyc_less.find(cur) != cyc_less.end()) cyc_less.erase(cur);
// all_prev.erase(cur);
fin[cur] = 1;
return 0;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
n = N;
m = M;
for (int i = 0; i < m; i++) {
edges[U[i]].push_back(pii(V[i], i));
redges[V[i]].push_back(pii(U[i], i));
edge_list[i] = pii(U[i], V[i]);
outdeg[U[i]]++;
}
for (int i = 0; i < n; i++) {
if (!dead[i] && outdeg[i] == 0) prune(i);
}
if (dead[0]) return false;
fill(pinch, pinch+n, -1);
if (!dfs(0)) return false;
return vector<int>({});
}
