#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>
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<'\n';
using namespace std;
vector<set<int>>adj;
vi from;
vector<bool>vis;
pii branch;
int st;
bool ok = 0;
vector<int>doob;
void dfs(int x, int fr){
if(ok)return;
vis[x] = 1;
int cnt = adj[x].size();
if(fr != -1)cnt--;
if(cnt >= 2){
st = x;
vi brr;
for(auto u : adj[x]){
if(u == fr)continue;
brr.pb(u);
if(brr.size() == 2)break;
}
branch = mp(brr[0], brr[1]);
ok = 1;
return;
}
for(auto u : adj[x]){
if(u == fr)continue;
if(ok)return;
else{
from[u] = x;
dfs(u, x);
}
}
}
void dfs2(int x){
if(ok)return;
vis[x] = 1;
if(doob[x] != -1){
st = x;
ok = 1;
return;
}
for(auto u : adj[x]){
if(vis[u])continue;
if(ok)return;
from[u] = x;
dfs2(u);
}
}
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);
doob.resize(n);
f0r(i, n)doob[i] = -1;
from[0] = -1;
map<pii, int>ma;
map<pii, vector<int>>dub;
for(int i = 0; i<m; i+=2){
adj[u[i]].insert(v[i]);
adj[v[i]].insert(u[i]);
ma[mp(u[i], v[i])] = i;
ma[mp(v[i], u[i])] = i + 1;
dub[mp(u[i], v[i])].pb(i);
dub[mp(v[i], u[i])].pb(i+1);
}
for(auto u : dub){
if(u.second.size() > 1){
doob[u.first.first] = u.first.second;
doob[u.first.second] = u.first.first;
}
}
dfs(0, -1);
if(ok){
vi chain;
chain.pb(st);
while(chain.back() != 0)chain.pb(from[chain.back()]);
reverse(chain.begin(), chain.end());
vi nums;
f0r(i, chain.size() - 1){
nums.pb(ma[mp(chain[i], chain[i + 1])]);
}
int a = ma[mp(st, branch.first)];
int b = ma[mp(branch.first, st)];
int c = ma[mp(st, branch.second)];
int d = ma[mp(branch.second, st)];
vi ans;
for(auto u : nums){
ans.pb(u);
}
ans.pb(a);
ans.pb(b);
ans.pb(c);
ans.pb(d);
ans.pb(b);
ans.pb(a);
ans.pb(d);
ans.pb(c);
for(int i = nums.size() - 1; i>=0; i--)ans.pb(nums[i]);
// cout<<st<<' '<<branch.first<<' '<<branch.second<<'\n';
return ans;
}
else{
f0r(i,n){
from[i] = 0;
vis[i] = 0;
}
from[0] = -1;
dfs2(0);
if(ok){
vi ans;
vi chain;
chain.pb(st);
while(chain.back() != 0)chain.pb(from[chain.back()]);
reverse(chain.begin(), chain.end());
vi nums;
f0r(i, chain.size() - 1){
nums.pb(ma[mp(chain[i], chain[i + 1])]);
}
for(auto u : nums){
ans.pb(u);
}
int a1 = dub[mp(st, doob[st])][0];
int b1 = dub[mp(st, doob[st])][1];
int c1 = dub[mp(doob[st], st)][0];
ans.pb(a1);
ans.pb(c1);
ans.pb(b1);
ans.pb(a1);
ans.pb(c1);
ans.pb(b1);
for(int i = nums.size() - 1; i>=0; i--)ans.pb(nums[i]);
return ans;
}
else return false;
}
}
