#include "islands.h"
#include <variant>
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <map>
using namespace std;
int n,m;
vector<int>u,v;
variant<bool,vector<int>>sub1(){
vector<int>c1,c2;
for(int i=0;i<m;i++){
if(u[i]==0) c1.push_back(i);
else c2.push_back(i);
}
if(c1.size()<2 || c2.size()<1) return false;
return vector<int>({c1[0],c2[0],c1[1],c1[0],c2[0],c1[1]});
}
vector<int>sub2(){
vector<vector<int>>a(3,vector<int>(3));
for(int i=0;i<m;i++){
if(u[i]<3 && v[i]<3) a[u[i]][v[i]]=i;
}
return vector<int>({a[0][1],a[1][0],a[0][2],a[2][1],a[0][1],a[1][0],a[2][1],a[0][2]});
}
#define ff first
#define ss second
vector<vector<pair<int,int>>>adj;
vector<int>vis;
variant<bool,vector<int>>dfs(int x,int c){
vis[x]=true;
pair<int,int>y={-1,-1},z={-1,-1};
for(auto j:adj[x]){
// cout<<j.ss<<' ';
if(j.ss==(c^1)) continue;
if(y.ff==-1) y=j;
else z=j;
}
if(z.ff!=-1) return vector<int>({y.ss,y.ss^1,z.ss,z.ss^1,y.ss^1,y.ss,z.ss^1,z.ss});
for(auto [f,cc]:adj[x]){
if(vis[f]) continue;
variant<bool,vector<int>>res=dfs(f,cc);
if(res.index()==0) continue;
vector<int>sm=get<vector<int>>(res);
vector<int>asn={cc};
for(int h:sm) asn.push_back(h);
asn.push_back(cc);
return asn;
}
return false;
}
variant<bool,vector<int>>sub3(){
adj.resize(n);
for(int i=0;i<m;i++){
adj[u[i]].push_back({v[i],i});
}
vis.assign(n,0);
return dfs(0,-1);
}
vector<vector<int>>g;
vector<map<int,vector<int>>>mp;
vector<int>cycle,cf;
bool found;
int k;
void dfs1(int x,int p){
cf[x]=p;
vis[x]=1;
for(int z:g[x]){
if(vis[z]==2 || found) continue;
if(vis[z]==1){
while(x!=z) cycle.push_back(x),x=cf[x];
cycle.push_back(z);
found=true;
return;
}
dfs1(z,x);
}
vis[x]=2;
}
vector<int>ans,ans1;
bool dfs2(int x){
if(x==k) return true;
vis[x]=true;
for(int z:g[x]){
if(vis[z]) continue;
if(dfs2(z)){
ans1.push_back(mp[x][z][0]);
return true;
}
}
return false;
}
variant<bool,vector<int>>sub4(){
mp.resize(n);
g.resize(n);
for(int i=0;i<m;i++){
g[u[i]].push_back(v[i]);
mp[u[i]][v[i]].push_back(i);
}
cf.resize(n);
vis.assign(n,0);
found=false;
dfs1(0,0);
if(cycle.size()==0) return false;
reverse(cycle.begin(),cycle.end());
k=cycle[0];
vis.assign(n,false);
dfs2(0);
reverse(ans1.begin(),ans1.end());
for(int x:ans1) ans.push_back(x);
reverse(ans1.begin(),ans1.end());
if(cycle.size()==2){
int y=cycle[1];
ans.push_back(mp[k][y][0]);
ans.push_back(mp[y][k][0]);
ans.push_back(mp[k][y][1]);
ans.push_back(mp[k][y][0]);
ans.push_back(mp[y][k][0]);
ans.push_back(mp[k][y][1]);
}
else{
cycle.push_back(k);
ans.push_back(mp[k][cycle[1]][0]);
for(int i=cycle.size()-1;i>1;i--) ans.push_back(mp[cycle[i]][cycle[i-1]][0]);
ans.push_back(mp[k][cycle[1]][0]);
for(int i=2;i<cycle.size();i++) ans.push_back(mp[cycle[i]][cycle[i-1]][0]);
}
for(int x:ans1) ans.push_back(x);
return ans;
}
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
tie(n,m,u,v)=tie(N,M,U,V);
if(n==2) return sub1();
if(m==n*(n-1)) return sub2();
if(u[0]!=u[1]) return sub3();
return sub4();
}
