#include "islands.h"
#include<bits/stdc++.h>
#include <variant>
#include <vector>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50;
vector<int>E[N];
int U[2*N],V[2*N];
bool was[N];int par[N];
//vector<int>ans;bool imares;
int nekicvor=-1;
void DFS(int u){
was[u]=true;
if(E[u].size()>=3||(u==0&&E[u].size()>=2)) {nekicvor=u;return;}
for(auto i:E[u]){
if(!was[V[i]]) par[V[i]]=u,DFS(V[i]);
}
/*vector<int>nesto;
for(auto i:E[u]){
if(!was[i]) nesto.pb(i);
}
if(nesto.size()>=2){
int ind[4];
ind[0]=nesto[0];
if(ind[0]%2==0) ind[1]=ind[0]+1;
else ind[1]=ind[0]-1;
ind[2]=nesto[1];
if(ind[2]%2==0) ind[3]=ind[2]+1;
else ind[3]=ind[2]-1;
ans.pb(ind[0]),ans.pb(ind[1]);
ans.pb(ind[2]),ans.pb(ind[3]);
ans.pb(ind[1]),ans.pb(ind[0]);
ans.pb(ind[3]),ans.pb(ind[2]);
imares=true;
return;
}
bool bul=false;
for(auto i:E[u]){
if(!was[i]){
was[i]=true;
int j=i;
if(j%2==0) j++;
else j--;
was[j]=true;
ans.pb(i);
DFS(V[i]);
ans.pb(j);
bul=true;
break;
}
}
if(!bul) ans.pop_back();*/
}
std::variant<bool, std::vector<int>> find_journey(int n, int m, std::vector<int> U1, std::vector<int> V1) {
for(int i=0;i<m;i++) U[i]=U1[i],V[i]=V1[i];
bool subtask3=true;if(m%2==1) subtask3=false;
for(int i=0;i<m;i++) if(m%2==0&&i%2==0&&(U[i]!=V[i+1]||V[i]!=U[i+1])) subtask3=false;
if(n==2){
int deg[n+10]={0};
vector<int>nesto[n+10];
for(int i=0;i<m;i++){
deg[U[i]]++;
nesto[U[i]].pb(i);
}
if(deg[0]<=1||deg[1]<=0) return false;
return (vector<int>){nesto[0][0],nesto[1][0],nesto[0][1],nesto[0][0],nesto[1][0],nesto[0][1]};
}
if(subtask3){
map<pair<int,int>,int>mapa;
for(int i=0;i<m;i++){
E[U[i]].pb(i);
mapa[{U[i],V[i]}]=i;
}
DFS(0);
if(nekicvor==-1) return false;
vector<int>res,temp;
int u=nekicvor;
//printf("%i\n",nekicvor);
while(u!=0) temp.pb(u),u=par[u];
temp.pb(0);
//for(auto i:temp) printf("%i ",i);printf("\n");
for(int i=temp.size()-1;i>0;i--) res.pb(mapa[{temp[i],temp[i-1]}]);
u=nekicvor;
int ct=0,ind[4];
for(auto i:E[u]){
if(ct>1) break;
if(V[i]==par[u]) continue;
ind[2*ct]=i;
if(i%2==0) ind[2*ct+1]=i+1;
else ind[2*ct+1]=i-1;
ct++;
}
res.pb(ind[0]),res.pb(ind[1]);
res.pb(ind[2]),res.pb(ind[3]);
res.pb(ind[1]),res.pb(ind[0]);
res.pb(ind[3]),res.pb(ind[2]);
for(int i=1;i<temp.size();i++) res.pb(mapa[{temp[i],temp[i-1]}]);
return res;
}
else{
int ind[10];
for(int i=0;i<m;i++){
if(U[i]==0&&V[i]==1) ind[0]=i;
if(U[i]==1&&V[i]==0) ind[1]=i;
if(U[i]==0&&V[i]==2) ind[2]=i;
if(U[i]==2&&V[i]==0) ind[3]=i;
}
if(n==2) return false;
return (vector<int>){ind[0],ind[1],ind[2],ind[3],ind[1],ind[0],ind[3],ind[2]};
}
}
