#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 set_ind(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;
set_ind(x.st);
max_ind[v] = max(max_ind[v],max_ind[x.st]); //to powinno byc pozniej!
}
for(auto x:g[v]){
if(drzewowa[x.nd]) continue;
if(h[x.st] < h[v]){
//cerr << "wsteczna\n";
max_ind[v] = max(max_ind[v],h[x.st]);
}
else{
//cerr << "set_min\n";
min_ind[x.st] = min(min_ind[x.st],h[v]);
}
}
}
bool check_ans(int v){
//cerr << "v: " << v << " min_ind: " << min_ind[v] << '\n';
bool ans = 0;
int ile_c = 0;
for(auto x:g[v]){
if(drzewowa[x.nd]){
min_ind[x.st] = min(min_ind[x.st],min_ind[v]);
if(max_ind[x.st] >= h[v]) ile_c++;
ans |= check_ans(x.st);
}
//krawedz wsteczna, warunek czy dwie sciezki na jeden cykl!
if(h[x.st] < h[v] && min_ind[v] <= h[x.st]) ans = 1;
}
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;
}
set_h(0); //cerr << "set_h\n";
set_ind(0); //cerr << "set_cykl\n";
//bool ans = 0;
bool ans = check_ans(0); //cerr << "ans: " << ans << '\n';
//if(!ans) return false;
vi vec; rep(i,0,n-1) vec.pb(i); //cokolwiek
return vec;
}
