#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define irep(i,a,b) for(int i = a; i >= b; i--)
typedef long long ll;
typedef long double ld;
//typedef __int128 int128;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<ll,ll> pl;
const int max_n = 2e5+7;
const int INF = 1e9+7;
vector<pi> g[max_n];
bool drzewowa[max_n];
bool odw[max_n];
int h[max_n];
bool cykl[max_n]; //cykl nizej!
int min_ind[max_n]; //min h na ktorej sie rozdzielamy by dojsc do tego wierzcholka!
int max_ind[max_n]; //max h dla ktorej mamy krawedz wsteczną nad nami!
void set_h(int v){
//cerr << "\nset_h, v: " << v << " h: " << h[v] << '\n';
odw[v] = 1;
for(auto x:g[v]){
if(odw[x.st]) continue;
drzewowa[x.nd] = 1;
h[x.st] = h[v]+1;
set_h(x.st);
}
}
void ini(int v){
//cerr << "\nset_cykl od v: " << v << '\n';
for(auto x:g[v]){
//cerr << "x.st: " << x.st << " nd: " << x.nd << '\n';
if(!drzewowa[x.nd]) continue;
min_ind[x.st] = min(min_ind[x.st],min_ind[v]);
ini(x.st);
max_ind[v] = max(max_ind[v],max_ind[x.st]); //to powinno byc pozniej!
}
}
bool check_ans(int v){
//cerr << "v: " << v << " min_ind: " << min_ind[v] << '\n';
bool ans = 0;
int ile_c = 0;
if(max_ind[v] >= min_ind[v]) ans = 1; //imo check wystarczy!
for(auto x:g[v]){
if(!odw[x.st]) continue; //moze sie przyda!
if(drzewowa[x.nd]){
ans |= check_ans(x.st);
if(max_ind[x.st] >= h[v]) ile_c++;
}
}
//cout << "v: " << v << " ile_c: " << ile_c << '\n';
if(ile_c >= 2) ans = 1;
return ans;
}
variant<bool, vi> find_journey(int n, int m, vi U, vi V) {
rep(i,0,m-1) g[U[i]].pb({V[i],i});
rep(i,0,n-1){
min_ind[i] = INF; max_ind[i] = -1;
}
//stworzyc min i max
set_h(0); //cerr << "set_h\n";
rep(v,0,n-1){
//cerr << "\nv: " << v << '\n';
for(auto x:g[v]){
//cout << "x: " << x.st << ' ' << x.nd << '\n';
//cout << "drzewowa: " << drzewowa[x.nd] << " odw: " << odw[x.st] << '\n';
if(drzewowa[x.nd] || !odw[x.st]) continue;
//cout <<" ustawiamy\n";
if(h[x.st] < h[v]) max_ind[v] = max(max_ind[v],h[x.st]);
if(h[x.st] > h[v]) min_ind[x.st] = min(min_ind[x.st],h[v]);
}
}
ini(0); //cerr << "set_cykl\n";
//debug
//rep(v,0,n-1) cerr << "v: " << v << " min: " << min_ind[v] << " max: " << max_ind[v] << '\n';
//bool ans = 0;
bool ans = check_ans(0); //cerr << "ans: " << ans << '\n';
if(!ans) return false;
return true;
//vi vec; rep(i,0,n-1) vec.pb(i); //cokolwiek
//return vec;
}
