#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj, v;
vector<int> pai, marc, rep;
int find( int a ){ return (( a == rep[a] ) ? a : rep[a] = find(rep[a])); }
void join( int a, int b ){
rep[find(a)] = find(b);
}
bool dfs( int cur ){
marc[cur] = 1;
for( int viz : adj[cur] ){
if( marc[viz] == 0 ){
pai[viz] = cur;
if( dfs( viz ) ) return true;
}
else if( marc[viz] == 1 ) v[viz].push_back(cur);
else if( rep[viz] != viz ) return true;
}
for( int x : v[cur] ){
while( find(x) != 0 ){
join( x, pai[x] );
x = find(x);
}
}
marc[cur] = 2;
return false;
}
variant<bool, vector<int>> find_journey( int n, int m, vector<int> a, vector<int> b ){
adj.resize(n);
v.resize(n);
marc.resize(n);
pai.resize(n);
rep.resize(n);
iota( rep.begin(), rep.end(), 0 );
for( int i = 0; i < m; i++ ) adj[a[i]].push_back(b[i]);
return dfs(0);
}
