#include "islands.h"
#include <bits/stdc++.h>
#include <variant>
#define ll long long
#define sz(s) (int)s.size()
#define pb push_back
#define in insert
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define F first
#define S second
#define all(v) v.begin(),v.end()
using namespace std;
const int MAX=2e5+10;
vector<pii> g[MAX];
int use[MAX];
int pr[MAX];
int d[MAX];
int cycle;
void dfs(int v,int p=-1){
pr[v]=p;
use[v]=1;
for(auto to:g[v]){
if(to.F==p)continue;
if(use[to.F]){
cycle=to.S;
}
else{
d[to.F]=d[v]+1;
dfs(to.F,to.S);
}
}
use[v]=1;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U,vector<int> V){
cycle=-1;
map<pii,int> mp;
for(int i=0;i<M;i++){
g[U[i]].pb({V[i],i});
mp[{U[i],V[i]}]=i;
}
dfs(0);
if(cycle==-1)return false;
vector<int> a,b;
int X=U[cycle],Y=V[cycle];
while(X!=Y){
if(d[X]>d[Y]){
a.pb(pr[X]);
X=U[pr[X]];
}
else{
b.pb(pr[Y]);
Y=U[pr[Y]];
}
}
reverse(all(b));
b.pb(cycle);
for(int x:a)b.pb(x);
vector<int> c;
while(X!=0){
c.pb(pr[X]);
X=U[pr[X]];
}
vector<int> ans;
reverse(all(c));
for(int x:c)ans.pb(x);
for(int x:b)ans.pb(x);
reverse(all(b));
for(int x:b){
ans.pb(mp[{V[x],U[x]}]);
}
for(int x:b)ans.pb(x);
reverse(all(b));
for(int x:b){
ans.pb(mp[{V[x],U[x]}]);
}
reverse(all(c));
for(int x:c)ans.pb(x);
return ans;
}
