#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 cyc,int now){
vector<int> v;
v.push_back(cyc);
while(now != to[cyc]){
int eid = up[now];
v.push_back(eid);
now = to[eid^1];
}
reverse(v.begin(),v.end());
vector<int> rt;
while(now != 0){
int eid = up[now];
rt.push_back(eid);
now = to[eid^1];
}
reverse(rt.begin(),rt.end());
/*
cerr<<"ANS: "<<endl;
for(auto &i:rt)cerr<<to[i]<<' ';cerr<<endl;
for(auto &i:v)cerr<<to[i]<<' ';cerr<<endl;
*/
for(auto it = rt.begin();it != rt.end();it++)ansv.push_back(*it);
for(auto it = v.begin();it != v.end();it++)ansv.push_back(*it);
for(auto it = v.rbegin();it != v.rend();it++)ansv.push_back((*it)^1);
for(auto it = v.rbegin();it != v.rend();it++)ansv.push_back(*it);
for(auto it = v.begin();it != v.end();it++)ansv.push_back((*it)^1);
for(auto it = rt.rbegin();it != rt.rend();it++)ansv.push_back(*it);
return;
}
bitset<mxn> vis;
void dfs(int now){
if(!ansv.empty())return;
vis[now] = true;
//cerr<<now<<endl;
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]){
getans(eid,now);
return;
}
else{
up[nxt] = eid;
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;
}
