#include "islands.h"
#include <variant>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 4e5+10;
int head[mxn],nid[mxn],to[mxn];
int ecnt = 0;
int up[mxn];
void add_edge(int a,int b){
nid[ecnt] = head[a];
head[a] = ecnt;
to[ecnt] = b;
ecnt++;
return;
}
vector<int> ansv;
void getans(int a,int b,int now){
vector<int> rt;
while(now != 0){
int eid = up[now];
rt.push_back(eid);
now = to[eid^1];
}
reverse(rt.begin(),rt.end());
for(auto it = rt.begin();it != rt.end();it++)ansv.push_back(*it);
vector<int> tv = {a,a^1,b,b^1,a^1,a,b^1,b};
for(auto &i:tv)ansv.push_back(i);
for(auto it = rt.rbegin();it != rt.rend();it++)ansv.push_back(*it);
/*
cerr<<"ANS: "<<endl;
for(auto &i:rt)cerr<<to[i]<<' ';cerr<<endl;
for(auto &i:v)cerr<<to[i]<<' ';cerr<<endl;
*/
return;
}
bitset<mxn> vis;
void dfs(int now){
if(!ansv.empty())return;
vis[now] = true;
//cerr<<now<<endl;
vector<int> cnt;
for(int eid = head[now];eid != -1;eid = nid[eid]){
if(!ansv.empty())return;
int nxt = to[eid];
//cerr<<now<<' '<<nxt<<":"<<eid<<endl;
if((eid^1) == up[now])continue;
cnt.push_back(eid);
}
if(cnt.size()>=2){
getans(cnt[0],cnt[1],now);
return;
}
for(int eid = head[now];eid != -1;eid = nid[eid]){
if(!ansv.empty())return;
int nxt = to[eid];
//cerr<<now<<' '<<nxt<<":"<<eid<<endl;
if((eid^1) == up[now])continue;
if(!vis[nxt])dfs(nxt);
}
return;
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
memset(head,-1,sizeof(head));
for(int i = 0;i<M;i++){
int a = U[i],b = V[i];
add_edge(a,b);
}
memset(up,-1,sizeof(up));
dfs(0);
if(!ansv.empty())return ansv;
else return false;
}
