#include "islands.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
vector<int>V[LIM], S[LIM];
stack<int>Q;
int odw[LIM], kol[LIM], ile[LIM], akt;
void DFS(int x) {
odw[x]=1;
for(auto i : V[x]) if(!odw[i]) DFS(i);
Q.push(x);
}
void DFS2(int x) {
kol[x]=akt;
for(auto i : S[x]) if(!kol[i]) DFS2(i);
}
int DFS3(int x) {
odw[x]=1;
if(x && ile[kol[x]]>=2) return x;
int ok=-1;
for(auto i : V[x]) if(!odw[i] && DFS3(i)!=-1) {
if(!x) return i;
ok=i;
}
return ok;
}
int cykl(int n) {
rep(i, n) odw[i]=kol[i]=ile[i+1]=0;
rep(i, n) if(!odw[i]) DFS(i);
akt=0;
while(!Q.empty()) {
int p=Q.top(); Q.pop();
if(kol[p]) continue;
++akt;
DFS2(p);
}
rep(i, n) ++ile[kol[i]];
rep(i, n) odw[i]=0;
return DFS3(0);
}
variant<bool,vector<int>>find_journey(int n, int m, vector<int>X, vector<int>D) {
multiset<pair<int,int>>A;
rep(i, m) A.insert({X[i], D[i]});
for(auto i : A) {
V[i.st].pb(i.nd);
S[i.nd].pb(i.st);
}
int x=cykl(n);
if(x==-1) return false;
A.erase(A.find({0, x}));
rep(i, n) {
V[i].clear();
S[i].clear();
}
for(auto i : A) {
V[i.st].pb(i.nd);
S[i.nd].pb(i.st);
}
x=cykl(n);
if(x==-1) return false;
return true;
}
