#include <bits/stdc++.h>
#include "islands.h"
using namespace std;
constexpr size_t N_MAX = 100000;
set<pair<int, int>> g[N_MAX];
bitset<N_MAX> in_dfs;
int find_cycle(int u, vector<int> &cycle, vector<int> &path_to_cycle)
{
if (in_dfs[u])
return u;
in_dfs[u] = 1;
for (auto const &[v, i] : g[u])
{
int x = find_cycle(v, cycle, path_to_cycle);
if (x != -1)
{
cycle.push_back(i);
in_dfs[u] = 0;
return x == u ? -1 : x;
}
else if (!cycle.empty())
{
path_to_cycle.push_back(i);
in_dfs[u] = 0;
return -1;
}
}
in_dfs[u] = 0;
return -1;
}
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);
vector<int> cycle, path_to_cycle;
find_cycle(0, cycle, path_to_cycle);
if (cycle.empty())
return false;
reverse(cycle.begin(), cycle.end());
reverse(path_to_cycle.begin(), path_to_cycle.end());
vector<int> tour = path_to_cycle;
tour.insert(tour.end(), cycle.begin(), cycle.end());
for (size_t i = path_to_cycle.size(); i < path_to_cycle.size() + cycle.size(); ++i)
{
if (tour[i] + 1 < M && U[tour[i]] == U[tour[i] + 1] && V[tour[i]] == V[tour[i] + 1])
tour.push_back(tour[i] + 1);
else
tour.push_back(tour[i] - 1);
}
tour.resize(tour.size() * 2);
copy(tour.begin() + path_to_cycle.size(), tour.begin() + tour.size() / 2, tour.begin() + tour.size() / 2);
copy(path_to_cycle.begin(), path_to_cycle.end(), tour.end() - path_to_cycle.size());
reverse(tour.begin() + tour.size() / 2, tour.begin() + tour.size() / 2 + cycle.size());
reverse(tour.begin() + tour.size() / 2 + cycle.size(), tour.end() - path_to_cycle.size());
reverse(tour.end() - path_to_cycle.size(), tour.end());
return tour;
}
