#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,m;
vector<ii> al[200005];
ii edges[200005];
bool down[200005];
bool vis[200005];
bool onstk[200005];
int in[200005];
ii mx[200005];
int pp[200005];
int CTIME=1;
void dfs(int i){
vis[i]=true;
onstk[i]=true;
in[i]=CTIME++;
mx[i]=ii(-1,-1);
for (auto [it,id]:al[i]){
if (!vis[it]){
pp[it]=id;
dfs(it);
down[id]=true;
}
if (onstk[it]){
mx[i]=max(mx[i],{in[it],id});
}
else{
mx[i]=max(mx[i],mx[it]);
down[id]=true;
}
}
onstk[i]=false;
}
;
bool get(int i,vector<int> &v){
vis[i]=true;
onstk[i]=true;
for (auto [it,id]:al[i]){
if (!vis[it]){
if (get(it,v)){
v.pub(id);
return true;
}
}
if (onstk[it]){
v.pub(id);
return true;
}
}
onstk[i]=false;
return false;
}
variant<bool, vector<signed>> find_journey(
signed N, signed M, vector<signed> U, vector<signed> V) {
n=N,m=M;
rep(x,0,m){
al[U[x]].pub({V[x],x});
edges[x]={U[x],V[x]};
}
dfs(0);
//rep(x,0,n) cout<<in[x]<<" "; cout<<endl;
//rep(x,0,n) cout<<mx[x]<<" "; cout<<endl;
//rep(x,0,n) cout<<pp[x]<<" "; cout<<endl;
rep(x,0,n) if (vis[x]){
vector<ii> v;
for (auto [it,id]:al[x]) if (down[id] && mx[it].fi>=in[x]) v.pub({it,id});
if (sz(v)>=2){
vector<int> head;
int curr=x;
while (curr){
head.pub(pp[curr]);
curr=edges[pp[curr]].fi;
}
vector<signed> ans;
rep(x,sz(head),0) ans.pub(head[x]);
while (sz(v)>2) v.pob();
vector<int> tail[2],cyc[2];
rep(y,0,2){
memset(vis,false,sizeof(vis));
memset(onstk,false,sizeof(onstk));
onstk[x]=true;
for (auto it:head) vis[edges[it].fi]=true;
vis[x]=true;
vector<int> idx;
get(v[y].fi,idx);
idx.pub(v[y].se);
reverse(all(idx));
vector<int> idx1,idx2;
bool f=true;
for (auto it:idx){
if (edges[it].fi==edges[idx.back()].se) f=false;
if (f) tail[y].pub(it);
else cyc[y].pub(it);
}
//cout<<"debug: "<<v[y].fi<<endl;
//for (auto it:tail[y]) cout<<it<<" "; cout<<endl;
//for (auto it:cyc[y]) cout<<it<<" "; cout<<endl;
}
set<int> s;
rep(x,0,2) for (auto it:cyc[x]) s.insert(it);
if (sz(s)==sz(cyc[0])+sz(cyc[1])){
rep(x,0,4){
rep(y,0,sz(tail[x%2])) ans.pub(tail[x%2][y]);
if (x/2==0){
rep(y,0,sz(cyc[x%2])) ans.pub(cyc[x%2][y]);
}
else{
rep(y,sz(cyc[x%2]),0) ans.pub(cyc[x%2][y]);
}
rep(y,sz(tail[x%2]),0) ans.pub(tail[x%2][y]);
}
}
else{
s.clear();
for (auto it:cyc[0]) s.insert(it);
vector<int> tail2[2];
rep(x,0,2){
vector<int> temp;
for (auto it:tail[x]) temp.pub(it);
for (auto it:cyc[x]) temp.pub(it);
for (auto it:temp){
tail2[x].pub(it);
if (s.count(it)) break;
}
}
//cout<<"testing: "<<endl;
//for (auto it:tail2[0]) cout<<it<<" "; cout<<endl;
//for (auto it:tail2[1]) cout<<it<<" "; cout<<endl;
//for (auto it:cyc[0]) cout<<it<<" "; cout<<endl;
rep(x,0,sz(tail2[0])-1) ans.pub(tail2[0][x]);
rep(i,0,sz(cyc[0])) if (cyc[0][i]==tail2[0].back()){
rep(x,i,sz(cyc[0])) ans.pub(cyc[0][x]);
rep(x,0,i) ans.pub(cyc[0][x]);
}
rep(x,sz(tail2[0])-1,0) ans.pub(tail2[0][x]);
rep(x,0,sz(tail2[1])-1) ans.pub(tail2[1][x]);
rep(i,0,sz(cyc[0])) if (cyc[0][i]==tail2[1].back()){
rep(x,i,0) ans.pub(cyc[0][x]);
rep(x,sz(cyc[0]),i) ans.pub(cyc[0][x]);
}
rep(x,sz(tail2[1])-1,0) ans.pub(tail2[1][x]);
}
rep(x,0,sz(head)) ans.pub(head[x]);
return ans;
}
}
return false;
}
