#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;
int en;
bool ok = 0;
vector<int>doob;
void dfs(int x, int fr){
if(ok)return;
vis[x] = 1;
for(auto u : adj[x]){
if(u == fr)continue;
if(ok)return;
else if(vis[u]){
ok = 1;
st = u;
en = x;
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]);
ma[mp(u[i], v[i])] = i;
}
for(auto u : ma){
if(ma.count(mp(u.first.second, u.first.first))){
doob[u.first.first] = u.first.second;
doob[u.first.second] = u.first.first;
dub[mp(u.first.first, u.first.second)].pb(ma[mp(u.first.first, u.first.second)]);
dub[mp(u.first.first, u.first.second)].pb(ma[mp(u.first.first, u.first.second)] + 1);
dub[mp(u.first.second, u.first.first)].pb(ma[mp(u.first.second, u.first.first)]);
dub[mp(u.first.second, u.first.first)].pb(ma[mp(u.first.second, u.first.first)] + 1);
}
}
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 sike;
sike.pb(en);
while(sike.back() != st)sike.pb(from[sike.back()]);
reverse(sike.begin(), sike.end());
sike.pb(sike[0]);
vi nums;
f0r(i, chain.size() - 1){
nums.pb(ma[mp(chain[i], chain[i + 1])]);
}
// vout(chain);
// vout(sike);
vi ans;
for(auto u : nums){
ans.pb(u);
}
f0r(i, sike.size() - 1){
ans.pb(ma[mp(sike[i], sike[i+1])]);
}
f0r(i, sike.size() - 1){
ans.pb(ma[mp(sike[i], sike[i+1])] + 1);
}
for(int i = sike.size() - 2; i>=0; i--){
ans.pb(ma[mp(sike[i], sike[i+1])]);
}
for(int i = sike.size() - 2; i>=0; i--){
ans.pb(ma[mp(sike[i], sike[i+1])] + 1);
}
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;
}
}
