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