#include "islands.h"
#include <bits/stdc++.h>
#include <variant>
#include <vector>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf ((id<<1))
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 2e5+10;
typedef pair<int,int> pii;
int n, m;
int u[MAXN], v[MAXN];
vector<int> ANS;
vector<pii> adj[MAXN];
bool vis[MAXN];
vector<int> stac, cyc;
map<pii,int> ma, ma2;
vector<int> go;
void dfs(int nw, int pa){
vis[nw] = 1;
stac.pb(nw);
for(auto [nx, ed] : adj[nw]){
if(abs(ed-pa)==1 && u[ed]==v[pa] && u[pa]==v[ed]) continue;
if(!cyc.empty()) return;
if(vis[nx]){
while(stac.back() != nx){
cyc.pb(stac.back()); stac.pop_back();
}
cyc.pb(nx);
int ba = stac.back(); stac.pop_back();
while(!stac.empty()){
go.pb(ma[pii(stac.back(), ba)]);
ba = stac.back(); stac.pop_back();
}
return;
} else dfs(nx, ed);
}
}
void sol(int nw, int pa){
// cout << nw << " nw\n";
stac.pb(nw);
vector<int> vec;
for(auto [nx, ed] : adj[nw]){
if(abs(ed-pa)==1 && u[ed]==v[pa] && u[pa]==v[ed]) continue;
vec.pb(nx);
}
if(vec.size() >= 2){
for(int i=0; i+1<stac.size(); i++)
ANS.pb(ma[ pii(stac[i], stac[i+1]) ]);
int x = vec[0], y = vec[1];
ANS.pb(ma[pii(nw,x)]);
ANS.pb(ma[pii(x,nw)]);
ANS.pb(ma[pii(nw,y)]);
ANS.pb(ma[pii(y,nw)]);
ANS.pb(ma[pii(x,nw)]);
ANS.pb(ma[pii(nw,x)]);
ANS.pb(ma[pii(y,nw)]);
ANS.pb(ma[pii(nw,y)]);
for(int i=stac.size()-1; i>=1; i--)
ANS.pb(ma[ pii(stac[i-1], stac[i]) ]);
return;
}
for(auto [nx, ed] : adj[nw]){
if(ANS.size()) return;
if(abs(ed-pa)==1 && u[ed]==v[pa] && u[pa]==v[ed]) continue;
sol(nx, ed);
}
stac.pop_back();
}
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++){
u[i] = U[i]+1, v[i] = V[i]+1;
ma[pii(u[i], v[i])] = i;
adj[u[i]].pb({v[i], i});
}
for(int i=0; i<m; i++){
if(ma[pii(u[i], v[i])] == i) continue;
ma2[pii(u[i], v[i])] = i;
}
dfs(1, -1);
// for(auto in : cyc){
// cout << in << " in\n";
// }
if(!cyc.empty()){
reverse(cyc.begin(), cyc.end());
for(int i=go.size()-1; i>=0; i--) ANS.pb(go[i]);
cyc.pb(cyc[0]);
if(cyc.size() == 3){
for(int i=0; i+1<cyc.size(); i++){ // ac
int nx = cyc[i+1];
ANS.pb(ma[pii(cyc[i], nx)]);
}
for(int i=cyc.size()-1; i>=1; i--){ // fd
int nx = cyc[i-1];
ANS.pb(ma2[pii(cyc[i], nx)]);
}
for(int i=cyc.size()-1; i>=1; i--){ // fd
int nx = cyc[i-1];
ANS.pb(ma[pii(nx, cyc[i])]);
}
for(int i=0; i+1<cyc.size(); i++){ // ac
int nx = cyc[i+1];
ANS.pb(ma2[pii(nx, cyc[i])]);
}
} else {
for(int i=0; i+1<cyc.size(); i++){ // ac
int nx = cyc[i+1];
ANS.pb(ma[pii(cyc[i], nx)]);
}
for(int i=cyc.size()-1; i>=1; i--){ // fd
int nx = cyc[i-1];
ANS.pb(ma[pii(cyc[i], nx)]);
}
for(int i=cyc.size()-1; i>=1; i--){ // fd
int nx = cyc[i-1];
ANS.pb(ma[pii(nx, cyc[i])]);
}
for(int i=0; i+1<cyc.size(); i++){ // ac
int nx = cyc[i+1];
ANS.pb(ma[pii(nx, cyc[i])]);
}
}
for(int i=0; i<go.size(); i++) ANS.pb(go[i]);
return ANS;
}
if(adj[1].size() >= 2){
int x = adj[1][0].fi, y = adj[1][1].fi;
ANS.pb(ma[pii(1,x)]);
ANS.pb(ma[pii(x,1)]);
ANS.pb(ma[pii(1,y)]);
ANS.pb(ma[pii(y,1)]);
ANS.pb(ma[pii(x,1)]);
ANS.pb(ma[pii(1,x)]);
ANS.pb(ma[pii(y,1)]);
ANS.pb(ma[pii(1,y)]);
return ANS;
}
stac.clear();
sol(1,-1);
if(ANS.size()) return ANS;
return false;
}
