#include <bits/stdc++.h>
#include "islands.h"
using namespace std;
constexpr size_t N_MAX = 100000;
set<pair<int, int>> g[N_MAX], rg[N_MAX];
void delete_node(int u)
{
for (auto const &[v, i] : rg[u])
g[v].erase(make_pair(u, i));
for (auto const &[v, i] : g[u])
rg[v].erase(make_pair(u, i));
g[u].clear();
rg[u].clear();
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V)
{
for (int i = 0; i < M; ++i)
g[U[i]].emplace(V[i], i), rg[V[i]].emplace(U[i], i);
int x = 0;
vector<int> tour;
while (g[x].size() == 1)
{
tour.push_back(g[x].begin()->second);
int y = x;
x = g[x].begin()->first;
delete_node(y);
}
if (g[x].empty())
{
return false;
}
else
{
int a = g[x].begin()->second,
b = g[g[x].begin()->first].lower_bound(make_pair(x, 0))->second,
c = (++g[x].begin())->second,
d = g[(++g[x].begin())->first].lower_bound(make_pair(x, 0))->second;
assert(U[a] == x && V[b] == x && U[c] == x && V[d] == x);
tour.insert(tour.end(), {a, b, c, d, b, a, d, c});
tour.resize(2 * tour.size() - 8);
copy(tour.begin(), tour.begin() + (tour.size() - 8) / 2, tour.begin() + (tour.size() + 8) / 2);
reverse(tour.begin() + (tour.size() + 8) / 2, tour.end());
return tour;
}
}
