#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]){
// cout<<v<<" "<<pr[v]<<" "<<to.F<<" "<<to.S<<"\n";
if(pr[v]!=-1&&to.S==(pr[v]%2==0?pr[v]+1:pr[v]-1))continue;
if(use[to.F]){
cycle=to.S;
// return;
}
else{
d[to.F]=d[v]+1;
dfs(to.F,to.S);
}
}
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U,vector<int> V){
// return true;
cycle=-1;
for(int i=0;i<M;i++){
g[U[i]].pb({V[i],i});
}
if(N==2){
if(sz(g[0])>=2&&sz(g[1])>=1){
vector<int> vec={g[0][0].S,g[1][0].S,g[0][1].S,g[0][0].S,g[1][0].S,g[0][1].S};
return vec;
}return false;
}
dfs(0);
// cout<<cycle<<"\n";
if(cycle==-1)return false;
// return true;
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]%2==0?pr[Y]+1:pr[Y]-1));
Y=U[pr[Y]];
}
}
swap(a,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((x%2==0?x+1:x-1));
}
for(int x:b)ans.pb(x);
reverse(all(b));
for(int x:b){
ans.pb((x%2==0?x+1:x-1));
}
reverse(all(c));
for(int x:c)ans.pb(x);
return ans;
}
