#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];
vector<int>ans;bool imares;
void DFS(int u){
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;
}
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);
break;
}
}
}
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){
for(int i=0;i<m;i++) E[U[i]].pb(i);
DFS(0);
if(!imares) return false;
return ans;
}
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]};
}
}
