#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<pair<int,int>>G[LIM];
vector<int>V[LIM], S[LIM];
int deg[LIM], odw[LIM], kraw[2*LIM], n, m, akt;
map<pair<int,int>,int>mp;
bool DFS(int x) {
if(odw[x]) return true;
odw[x]=1;
for(auto i : G[x]) {
if(odw[i.st]) {
kraw[i.nd]=1;
return true;
}
if(DFS(i.st)) {
kraw[i.nd]=1;
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, m) mp[{_u[i], _v[i]}]=i;
vector<int>K;
rep(i, (int)P.size()-1) K.pb(mp[{P[i], P[i+1]}]);
if(P.size()) K.pb(mp[{P.back(), akt}]);
vector<int>ans;
for(auto i : K) ans.pb(i);
rep(i, m) if(!odw[_u[i]] && !odw[_v[i]]) G[_u[i]].pb({_v[i], i});
rep(i, n) odw[i]=0;
DFS(akt);
DFS(G[akt][1].st);
kraw[G[akt][1].nd]=1;
rep(i, n) V[i].clear();
rep(i, m) if(kraw[i]) {
V[_u[i]].pb(i);
V[_v[i]].pb(i);
}
int p=akt, ile=0, lst=-1;
while(ile<12) {
for(auto i : V[p]) if(_u[i]==p && lst!=i) {
p=_v[i];
swap(_u[i], _v[i]);
if(p==akt) ++ile;
lst=i;
ans.pb(i);
break;
}
}
reverse(all(K));
for(auto i : K) ans.pb(i);
return ans;
}
