#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));
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
{
tour.push_back(g[x].begin()->second);
tour.push_back(g[x].begin()->second + 1);
tour.push_back((++g[x].begin())->second);
tour.push_back((++g[x].begin())->second + 1);
tour.push_back(g[x].begin()->second + 1);
tour.push_back(g[x].begin()->second);
tour.push_back((++g[x].begin())->second + 1);
tour.push_back((++g[x].begin())->second);
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;
}
}
