#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int cur_scc;
vector<int> tp, scc_num, sz_scc, adj_from_0;
vector<bool> vis;
vector<vector<int> > adj, adj_t, adj_scc_t, init;
void dfs(int u) {
if (vis[u]) {
return;
}
vis[u] = 1;
for (auto v : adj_t[u]) {
dfs(v);
}
tp.pb(u);
}
void collect(int u) {
if (vis[u]) {
return;
}
vis[u] = 1;
scc_num[u] = cur_scc;
for (auto v : adj[u]) {
collect(v);
}
}
vector<int> dp(int u) {
vector<int> cur = init[u];
if ((int)cur.size() > 1) {
return cur;
}
for (auto v : adj_scc_t[u]) {
auto tmp = dp(v);
for (int i : tmp) {
bool in = 0;
for (int j : cur) {
if (i == j) {
in = 1;
break;
}
}
if (!in) {
cur.pb(i);
if ((int)cur.size() > 1) {
return cur;
}
}
}
}
return cur;
}
namespace ufds {
vector<int> lnk, sz, num_edges;
void init(int n) {
lnk.resize(n);
iota(lnk.begin(), lnk.end(), 0);
sz.resize(n);
fill(sz.begin(), sz.end(), 1);
num_edges.resize(n);
fill(num_edges.begin(), num_edges.end(), 0);
}
int find(int x) {
if (x == lnk[x]) {
return x;
}
return lnk[x] = find(lnk[x]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) {
return;
}
if (sz[b] > sz[a]) {
swap(a, b);
}
sz[a] += sz[b];
num_edges[a] += num_edges[b];
lnk[b] = a;
}
};
variant<bool, vector<int> > find_journey(int N, int M, vector<int> U, vector<int> V) {
ufds::init(N);
for (int i = 0; i < M; i++) {
if (i % 2 == 0) {
ufds::unite(U[i], V[i]);
ufds::num_edges[ufds::find(U[i])]++;
}
}
if (ufds::num_edges[ufds::find(0)] == ufds::sz[ufds::find(0)] - 1) {
return false;
} else {
int cnt = 0;
for (int i = 0; i < M; i++) {
if (U[i] == 0) {
cnt++;
}
}
return cnt > 1;
}
vis.resize(N);
scc_num.resize(N);
adj.resize(N);
adj_t.resize(N);
adj_scc_t.resize(N);
for (int i = 0; i < M; i++) {
adj[U[i]].pb(V[i]);
adj_t[V[i]].pb(U[i]);
}
for (int i = 0; i < N; i++) {
dfs(i);
}
reverse(tp.begin(), tp.end());
fill(vis.begin(), vis.end(), 0);
for (int i : tp) {
if (!vis[i]) {
collect(i);
cur_scc++;
}
}
sz_scc.resize(cur_scc);
init.resize(cur_scc);
for (int i = 0; i < N; i++) {
sz_scc[scc_num[i]]++;
}
for (int i = 0; i < M; i++) {
if (U[i] == 0 && (int)init[scc_num[V[i]]].size() < 2) {
init[scc_num[V[i]]].pb(i);
}
if (scc_num[U[i]] != scc_num[V[i]]) {
adj_scc_t[scc_num[V[i]]].pb(scc_num[U[i]]);
}
}
for (int i = 0; i < cur_scc; i++) {
auto vec = dp(i);
if (sz_scc[i] > 1 && (int)vec.size() > 1) {
return true;
}
}
return false;
}
