#include "islands.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;
const int N = 100'010;
int height[N], mnup[N], mxup[N];
vector<int> A[N];
bool vis[N];
bool anc[N];
int mncnt[N];
int kooft[N];
int par[N];
int marg[N];
int mark[N];
int mark2[N];
bool dfs1(int v, int p, int h)
{
par[v] = p;
vis[v] = 1;
anc[v] = 1;
height[v] = h;
mnup[v] = N;
mxup[v] = 0;
int cnt = 0;
for (int u : A[v]) {
if (anc[u]) {
mnup[v] = min(mnup[v], height[u]);
mxup[v] = max(mxup[v], height[u]);
kooft[u]--;
marg[u]++;
mark2[v] = 1;
}
if (vis[u])
continue;
auto tmp = dfs1(u, v, h+1);
cnt += !!marg[v] || tmp;
mark[u] = !!marg[v];
marg[v] = 0;
mnup[v] = min(mnup[v], mnup[u]);
if (mxup[u] <= height[v])
mxup[v] = max(mxup[v], mxup[u]);
mark2[v] |= mark2[u];
}
if (cnt >= 2)
throw 1;
anc[v] = 0;
return cnt;
}
bool has_back(int v) { return mnup[v] <= height[v]; }
void make_count()
{
vector<int> vec = {0};
fill(mncnt, mncnt+N, N);
mncnt[0] = -1;
while (vec.size()) {
int v = vec.back();
vec.pop_back();
vis[v] = 1;
int x = has_back(v)? height[v]: mncnt[v];
for (int u : A[v]) {
if (!vis[u]) {
mncnt[u] = min(mncnt[u], x);
if (!--kooft[u])
vec.push_back(u);
}
}
}
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
Loop (i,0,M) {
A[U[i]].push_back(V[i]);
kooft[V[i]]++;
}
try {
dfs1(0, -1, 0);
} catch(int) {
return true;
}
Loop (i,0,N) {
if (vis[i])
continue;
for (int u : A[i])
kooft[u]--;
}
memset(vis, 0, sizeof(vis));
make_count();
Loop (i,0,N) {
if (has_back(i) && mncnt[i] <= mxup[i] && (mncnt[i] < height[i]-1 || mxup[i] == height[i]))
return true;
}
return false;
}
