#include "islands.h"
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
struct edge
{
int ver,num;
edge(){};
edge(int vi, int ni)
{
ver = vi;
num = ni;
}
};
const int MAXN = 2e5+5;
int n,m,u[MAXN],v[MAXN];
int idx,ans[MAXN];
vector<edge>g[MAXN],o[MAXN];///obraten
vector<int>v0[MAXN],v1[MAXN];
void solve1()
{
for(edge nb : g[0])
{
v0[nb.ver].push_back(nb.num);
}
for(edge nb : o[0])
{
v1[nb.ver].push_back(nb.num);
}
for(int i = 1; i < n; i++)
{
if((int)v0[i].size() >= 2 && (int)v1[i].size() >= 1)
{
int u1 = v0[i][0];
int u2 = v0[i][1];
int v = v1[i][0];
ans[idx] = u1;
ans[idx+1] = v;
ans[idx+2] = u2;
ans[idx+3] = u1;
ans[idx+4] = v;
ans[idx+5] = u2;
idx += 6;
break;
}
}
}
struct PAR
{
int p,num;
};
int used[MAXN];
PAR par[MAXN];
int cikul,num_e;
vector<int>sp,put;
void dfs(int beg)
{
used[beg] = 1;
for(edge nb : g[beg])
{
if(cikul != -1) break;
if(used[nb.ver] == 2) continue;
if(used[nb.ver] == 1)
{
if(nb.ver == 0) continue;
cikul = beg;
num_e = nb.num;
sp.push_back(num_e);
int kraj = v[num_e];
int x = cikul;
while(x != kraj)
{
sp.push_back(par[x].num);
x = par[x].p;
}
reverse(sp.begin(),sp.end());
///x = kraj;
while(x != 0)
{
put.push_back(par[x].num);
x = par[x].p;
}
reverse(put.begin(),put.end());
break;
}
else
{
par[nb.ver] = {beg,nb.num};
dfs(nb.ver);
}
}
used[beg] = 2;
}
vector<int> is_cycle()
{
for(int i = 0; i < n; i++) used[i] = 0;
for(int i = 0; i < n; i++) par[i] = {0,0};
cikul = -1;
par[0] = {0,-1};
dfs(0);
if(cikul == -1) return sp;
/*cout << "hello" << endl;
for(int h : put) cout << h << " " ;
cout << endl;
for(int h : sp) cout << h << " ";
cout << endl;*/
vector<int>ans;
for(int h : put) ans.push_back(h);
for(int h : sp) ans.push_back(h);
for(int i = (int)put.size() - 1; i >= 0; i--) ans.push_back(put[i]);
for(int h : put) ans.push_back(h);
for(int i = (int)sp.size() - 1; i >= 0; i--) ans.push_back(sp[i]);
for(int i = (int)put.size() - 1; i >= 0; i--) ans.push_back(put[i]);
return ans;
}
variant <bool, vector<int> > find_journey(int N, int M, vector<int> U, vector<int> V)
{
n = N;
m = M;
for(int i = 0; i < M; i++)
{
u[i] = U[i];
v[i] = V[i];
g[u[i]].push_back({v[i],i});
o[v[i]].push_back({u[i],i});
}
solve1();
if(idx != 0)
{
vector<int>res;
res.resize(idx);
for(int i = 0; i < idx; i++) res[i] = ans[i];
return res;
}
//cout << "tuka" << endl;
vector<int> res = is_cycle();
if((int)res.size()) return res;
return false;
}
