#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> u,v;
vector<int> vis(1e5+3,0);
vector<int> par(1e5+3,-1);
vector<vector<int>> adj(1e5+3,vector<int>(0));
int cycpt=-1;
vector<int> cyc;
int color=1;
void dfs(int u) {
if (vis[u]==color) {cycpt=u; return;}
vis[u]=color;
for (auto v:adj[u]) {
dfs(v);
if (cycpt!=-1) {
cyc.push_back(u);
return;
}
++color;
}
}
variant<bool, std::vector<int>>
//vector<int>
find_journey(int N, int M, vector<int> U, vector<int> V) {
n=N,m=M,u=U,v=V;
if (n==2) {
vector<int> fv,sv;
for (int x=0; x<m; ++x) if (u[x]==0) fv.push_back(x); else sv.push_back(x);
int f=fv.size(), s=sv.size();
if (f>=2 && s) {
vector<int> r={fv[0],sv[0],fv[1],fv[0],sv[0],fv[1]};;
return r;
}
else return false;
}
vector<vector<int>>__p2(n,vector<int>(n,0));
int _p2=1;
for (int i=0; i<m; ++i) {
__p2[u[i]][v[i]]=1;
}
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
if (i==j) continue;
_p2&=__p2[i][j];
}
}
if (_p2) {
int a,b,c,d;
for (int i=0; i<m; ++i) {
if (u[i]==0 && v[i]==1) a=i;
if (u[i]==0 && v[i]==2) b=i;
if (u[i]==1 && v[i]==0) c=i;
if (u[i]==2 && v[i]==0) d=i;
}
vector<int> r = {a,c,b,d,c,a,d,b};
return r;
}
int _p3=1, _p4=1;
for (int i=0; i<m; i+=2) {
_p3&=((u[i]==v[i+1])&&(v[i]==u[i+1]));
_p4&=((u[i]==u[i+1])&&(v[i]==v[i+1]));
}
if (_p3) {
vector<int> deg(1e5+3,0);
for (int i=0; i<m; i+=2) {
deg[u[i]]++;
deg[v[i]]++;
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
int mx=0;
for (auto x:deg) mx=max(mx,x);
if (deg[0]>=2) {
int a=-1,b=-1,c=-1,d=-1;
int f=-1,s=-1;
for (auto x:adj[0]) {
if (f==-1) f=x;
else {s=x; break;}
}
for (int i=0; i<m; ++i) {
if (u[i]==0 && v[i]==f) a=i;
if (u[i]==0 && v[i]==s) b=i;
if (u[i]==f && v[i]==0) c=i;
if (u[i]==s && v[i]==0) d=i;
}
vector<int> r = {a,c,b,d,c,a,d,b};
return r;
}
if (mx<3) return false;
vis[0]=1;
queue<int> q; q.push(0);
while (!q.empty()) {
int x=q.front(); q.pop();
if (deg[x]>=3) {
vector<int> r;
int a=-1,b=-1,c=-1,d=-1;
vector<int> path;
int p=x;
while (p!=0) {
for (int i=0; i<m; ++i) {
if (u[i]==par[p] && v[i]==p) {
path.push_back(i);
break;
}
}
p=par[p];
}
for (int i=path.size()-1; i>=0; --i) r.push_back(path[i]);
int f=-1, s=-1;
for (auto y:adj[x]) {
if (y==par[x]) continue;
if (f==-1) f=y;
else {s=y; break;}
}
//cout<<f<<' '<<s<<'\n';
if (f!=s) for (int i=0; i<m; ++i) {
if (u[i]==x && v[i]==f) a=i;
if (u[i]==x && v[i]==s) b=i;
if (u[i]==f && v[i]==x) c=i;
if (u[i]==s && v[i]==x) d=i;
} else for (int i=0; i<m; ++i) {
if (u[i]==x && v[i]==f && a==-1) a=i;
if (u[i]==x && v[i]==s && a!=-1) b=i;
if (u[i]==f && v[i]==x && c==-1) c=i;
if (u[i]==s && v[i]==x && c!=-1) d=i;
}
vector<int> paiu={a,c,b,d,c,a,d,b};
for (auto x:paiu) r.push_back(x);
for (int i=0; i<path.size(); ++i) r.push_back(path[i]);
return r;
}
for (auto y:adj[x]) {
if (!vis[y]) {
q.push(y);
vis[y]=1;
par[y]=x;
}
}
}
return false;
}
if (_p4) {
for (int i=0; i<m; i+=2) {
adj[u[i]].push_back(v[i]);
}
dfs(0); //cout<<cycpt;
if (cycpt==-1) return false;
else return true;
return {};
}
}
