#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]});
}
vector<vector<int>>adj;
vector<int>vis,cf,cycle;
bool found;
void dfs(int x,int p){
if(found) return;
vis[x]=1;
cf[x]=p;
for(int z:adj[x]){
if(z==p || vis[z]==2 || found) continue;
if(z==0){
while(x!=0){
cycle.push_back(x);
x=cf[x];
}
cycle.push_back(0);
found=true;
return;
}
if(vis[z]==1) continue;
dfs(z,x);
}
vis[x]=2;
}
variant<bool,vector<int>>sub3(){
adj.resize(n);
for(int i=0;i<m;i++){
adj[u[i]].push_back(v[i]);
}
vis.assign(n,0);
found=false;
cf.resize(n);
dfs(0,0);
vector<int>ans;
vector<map<int,int>>b(n);
for(int i=0;i<m;i++) b[u[i]][v[i]]=i;
if(cycle.size()<3){
if(adj[0].size()<2) return false;
return vector<int>({b[0][adj[0][0]],b[adj[0][0]][0],b[0][adj[0][1]],b[adj[0][1]][0],b[adj[0][0]][0],b[0][adj[0][0]],b[adj[0][1]][0],b[0][adj[0][1]]});
}
reverse(cycle.begin(),cycle.end());
cycle.push_back(0);
ans.emplace_back(b[0][cycle[1]]);
ans.emplace_back(b[cycle[1]][0]);
for(int i=cycle.size()-1;i>1;i--) ans.push_back(b[cycle[i]][cycle[i-1]]);
ans.emplace_back(b[0][cycle[1]]);
ans.emplace_back(b[cycle[1]][0]);
for(int i=2;i<cycle.size();i++) ans.push_back(b[cycle[i]][cycle[i-1]]);
// for(int x:cycle) cout<<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();
return sub3();
}
/*
4 8
0 1
1 0
1 2
2 1
2 3
3 2
0 3
3 0
*/
