#include "islands.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define f0r(i,n) for(int i = 0; i< n; i++)
#define mp make_pair
#define pii pair<int,int>
using namespace std;
vector<vi>adj;
vi from;
vector<bool>vis;
vi cyc;
bool ok = 0;
void dfs(int x, int fr){
if(ok)return;
vis[x] = 1;
for(auto u : adj[x]){
if(u == fr)continue;
if(vis[u]){
cyc.pb(u); cyc.pb(x);
ok = 1;
return;
}
else{
from[u] = x;
dfs(u, x);
}
}
}
std::variant<bool, std::vector<int>> find_journey(
int n, int m, std::vector<int> u, std::vector<int> v) {
adj.resize(n);
from.resize(n);
vis.resize(n);
from[0] = -1;
map<pii, int>ma;
for(int i = 0; i<m; i+=2){
adj[u[i]].pb(v[i]);
adj[v[i]].pb(u[i]);
ma[mp(u[i], v[i])] = i;
ma[mp(v[i], u[i])] = i + 1;
}
dfs(0, -1);
if(cyc.empty())return false;
else{
while(cyc.back() != 0){
cyc.pb(from[cyc.back()]);
}
int st = 0;
f0r(i, cyc.size()){
if(cyc[i] == cyc.back()){
st = i;
break;
}
}
reverse(cyc.begin(), cyc.end());
vi ans;
f0r(i, st){
ans.pb(ma[mp(cyc[i], cyc[i+1])]);
}
FOR(i, st, cyc.size()){
ans.pb(ma[mp(cyc[i], cyc[i+1])]);
}
for(int i = cyc.size() - 1; i>st; i--){
ans.pb(ma[mp(cyc[i], cyc[i-1])]);
}
for(int i = cyc.size() - 1; i>st; i--){
ans.pb(ma[mp(cyc[i-1], cyc[i])]);
}
FOR(i, st, cyc.size()){
ans.pb(ma[mp(cyc[i+1], cyc[i])]);
}
for(int i = st - 1; i>=0; i--){
ans.pb(ma[mp(cyc[i+1], cyc[i])]);
}
return ans;
}
}
