#include "islands.h"
#include <variant>
#include <vector>
#include <algorithm>
#include <assert.h>
//#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef pair<int,int> pii;
struct date
{
int nod,a,b;
};
vector<date> muchii[100005];
vector<int> c[1005][1005];
bool useedge[300005],usenod[300005];
int n,m;
bool good=0;
int who;
vector<int> edges,v;
vector<int> nodes,w;
vector<date> ee[100005];
void dfs(int nod)
{
if(good)
return;
if(muchii[nod].size()>=3)
{
who=nod;
good=1;
return;
}
usenod[nod]=1;
for(date i:muchii[nod])
{
if(good)
return;
if(!usenod[i.nod])
{
edges.push_back(i.a);
dfs(i.nod);
if(good)
return;
}
}
}
vector<int> sol;
void build(int x,int y,int z)
{
assert(x>=0&&y>=0&&z>=0);
int A=c[x][y][0];
int B=c[y][x][0];
int C=c[x][z][0];
int D=c[z][x][0];
if(y==z)
{
C=c[x][z][1];
D=c[z][x][1];
}
vector<int> aux={A,B,C,D,B,A,D,C};
for(int i:aux)
sol.push_back(i);
}
bool use[200005];
bool inst[200005];
vector<int> ciclu;
vector<int> lant;
int from[200005];
void calc(int nod)
{
if(good)
return;
use[nod]=1;
inst[nod]=1;
for(date i:ee[nod])
{
if(good)
return;
if(use[i.nod])
{
if(inst[i.nod])
{
if(good==0)
{
good=1;
int x=nod;
while(true)
{
ciclu.push_back(x);
if(x==i.nod)
break;
else
x=from[x];
}
while(true)
{
lant.push_back(x);
if(x==0)
break;
else
x=from[x];
}
}
return;
}
}
else
{
from[i.nod]=nod;
calc(i.nod);
}
}
inst[nod]=0;
}
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V)
{
n=N;
m=M;
for(int i=0;i<m;i++)
{
int a=U[i];
int b=V[i];
c[a][b].push_back(i);
}
if(n==2)
{
if(c[0][1].size()>=2&&c[1][0].size()>=1)
{
int A=c[1][0][0];
int B=c[0][1][0];
int C=c[0][1][1];
sol={B,A,C,B,A,C};
return sol;
}
return false;
}
for(int a=0;a<n;a++)
for(int b=0;b<n;b++)
if(a!=b)
{
for(int i=0;i<c[a][b].size()&&i<c[b][a].size();i++)
{
int x=c[a][b][i];
int y=c[b][a][i];
muchii[a].push_back({b,x,y});
}
}
if(muchii[0].size()>=2)
{
int x=0;
int y=muchii[0][0].nod;
int z=muchii[0][1].nod;
build(x,y,z);
return sol;
}
dfs(0);
if(good)
{
for(int i:edges)
sol.push_back(i);
int x=who;
int y=-1;
int z=-1;
for(date i:muchii[who])
if(!usenod[i.nod])
{
if(y==-1)
y=i.nod;
else
z=i.nod;
}
build(x,y,z);
reverse(edges.begin(),edges.end());
for(int i:edges)
sol.push_back(i);
return sol;
}
for(int a=0;a<n;a++)
for(int b=0;b<n;b++)
{
if(c[a][b].size()>=2)
{
int x=c[a][b][0];
int y=c[a][b][1];
ee[a].push_back({b,x,y});
}
}
good=0;
calc(0);
if(good)
{
sol.clear();
reverse(ciclu.begin(),ciclu.end());
assert(ciclu.size()>=2);
for(int i=1;i<lant.size();i++)
sol.push_back(c[lant[i-1]][lant[i]][0]);
int lg=ciclu.size();
for(int i=0;i<ciclu.size();i++)
{
int x=ciclu[i];
int y=ciclu[(i+1)%lg];
sol.push_back(c[x][y][0]);
}
for(int i=0;i<ciclu.size();i++)
{
int x=ciclu[i];
int y=ciclu[(i+1)%lg];
sol.push_back(c[x][y][1]);
}
for(int i=0;;i=(i-1+lg)%lg)
{
int x=ciclu[i];
int y=ciclu[(i-1+lg)%lg];
sol.push_back(c[y][x][0]);
if(i==1)
break;
}
for(int i=0;;i=(i-1+lg)%lg)
{
int x=ciclu[i];
int y=ciclu[(i-1+lg)%lg];
sol.push_back(c[y][x][1]);
if(i==1)
break;
}
reverse(lant.begin(),lant.end());
for(int i=1;i<lant.size();i++)
sol.push_back(c[lant[i]][lant[i-1]][0]);
return sol;
}
return false;
}
