#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];
vector<int> A[N];
bool vis[N];
bool anc[N];
int cnt[N];
int kooft[N];
int par[N];
int marg[N];
bool dfs1(int v, int p, int h)
{
par[v] = p;
vis[v] = 1;
anc[v] = 1;
height[v] = h;
mnup[v] = N;
int cnt = 0;
for (int u : A[v]) {
if (anc[u]) {
mnup[v] = min(mnup[v], height[u]);
kooft[u]--;
marg[u]++;
}
if (vis[u])
continue;
auto tmp = dfs1(u, v, h+1);
cnt += !!marg[v] || tmp;
marg[v] = 0;
mnup[v] = min(mnup[v], mnup[u]);
}
if (cnt >= 2)
throw 1;
anc[v] = 0;
return cnt;
}
void make_count()
{
vector<int> vec = {0};
cnt[0] = 1;
while (vec.size()) {
int v = vec.back();
vec.pop_back();
vis[v] = 1;
for (int u : A[v]) {
if (!vis[u]) {
cnt[u] += cnt[v];
cnt[u] = min(cnt[u], 2);
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 (cnt[i] >= 2 && mnup[i] <= height[i])
return true;
}
return false;
}
