#include "islands.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
using namespace std;
namespace
{
int K;
vector<int> order, cc, vis, topo, dp;
vector<vector<int>> scc;
vector<pii> E[100000], R[100000];
void dfs(int u)
{
vis[u] = 1;
for (auto [v, i] : E[u])
if (!vis[v])
dfs(v);
order.emplace_back(u);
}
void dfscc(int u, int r)
{
vis[u] = 1;
cc[u] = r;
scc[r].emplace_back(u);
for (auto [v, i] : R[u])
if (!vis[v])
dfscc(v, r);
}
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V)
{
for (int i = 0; i < M; i++)
{
E[U[i]].emplace_back(pii(V[i], i));
R[V[i]].emplace_back(pii(U[i], i));
}
if(E[0].size() >= 2)
return true;
return false;
vis.resize(N, 0);
cc = vis;
for (int i = 0; i < N; i++)
if (!vis[i])
dfs(i);
for (int i = 0; i < N; i++)
vis[i] = 0;
reverse(order.begin(), order.end());
for (int i : order)
if (!vis[i])
{
topo.emplace_back(i);
scc.emplace_back(vector<int>());
dfscc(i, K++);
}
dp.resize(K, 0);
for (int i = K - 1; i >= 0; i--)
{
if (scc[i].size() > 1)
dp[i] = 1;
for (auto j : scc[i])
for (auto [k, _] : E[j])
dp[i] |= dp[cc[k]];
}
int cnt = 0;
for (auto [i, _] : E[0])
if (dp[cc[i]])
cnt++;
if (cnt >= 2)
return true;
return false;
}
