#include "islands.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#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], cykl1, cykl2;
int deg[LIM], odw[LIM], czy[LIM], n, m, akt;
bool DFS(int x) {
if(odw[x]) return false;
odw[x]=1;
for(auto i : V[x]) {
if(i==akt) {
cykl1.pb(x);
return true;
}
if(DFS(i)) {
cykl1.pb(x);
return true;
}
}
return false;
}
bool DFS2(int x) {
if(!odw[x]) return false;
odw[x]=1;
if(czy[x]) {
cykl2.pb(x);
return true;
}
for(auto i : V[x]) if(DFS(i)) {
cykl2.pb(x);
return true;
}
return false;
}
variant<bool,vector<int>>find_journey(int _n, int _m, vector<int>_u, vector<int>_v) {
n=_n; m=_m;
rep(i, m) {
V[_u[i]].pb(_v[i]);
S[_v[i]].pb(_u[i]);
}
rep(i, n) deg[i]=V[i].size();
queue<int>q;
rep(i, n) if(deg[i]==0) {
odw[i]=1;
q.push(i);
}
vector<int>P;
while(true) {
if(deg[akt]<1 || odw[akt]) return false;
if(deg[akt]==1) {
P.pb(akt);
odw[akt]=1;
int p=-1;
for(auto i : V[akt]) if(!odw[i]) p=i;
if(p==-1) return false;
for(auto i : S[akt]) {
--deg[i];
if(deg[i]<=0 && !odw[i]) {
odw[i]=1;
q.push(i);
}
}
akt=p;
continue;
}
if(q.empty()) break;
int p=q.front(); q.pop();
for(auto i : S[p]) {
--deg[i];
if(deg[i]<=0 && !odw[i]) {
odw[i]=1;
q.push(i);
}
}
}
rep(i, n) V[i].clear();
rep(i, m) if(!odw[_u[i]] && !odw[_v[i]]) V[_u[i]].pb(_v[i]);
rep(i, n) odw[i]=0;
DFS(akt);
reverse(all(cykl1));
rep(i, n) odw[i]=0;
for(auto i : cykl1) czy[i]=1;
DFS2(V[akt][1]);
return true;
}
