#include "islands.h"
#include <variant>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;
variant<bool, vector<int>> find_journey(int n, int m, vector<int> U, vector<int> V)
{
vector<set<pair<int, int> > > g(n), gr(n);
for (int i = 0; i < m; i++)
{
g[U[i]].insert({ V[i], i });
gr[V[i]].insert({ U[i], i });
}
queue<int> q;
for (int i = 0; i < n; i++)
{
if (g[i].empty()) q.push(i);
}
int vr = 0;
vector<int> path, ans;
while (true)
{
while (!q.empty())
{
int u = q.front();
q.pop();
for (pair<int, int> v : gr[u])
{
g[v.first].erase({ u, v.second });
if (g[v.first].empty()) q.push(v.first);
}
gr[u].clear();
}
if (g[vr].empty()) return false;
if (g[vr].size() == 1)
{
int i = g[vr].begin()->second;
g[vr].clear();
gr[V[i]].erase({ U[i], i });
path.push_back(i);
ans.push_back(i);
q.push(vr);
vr = V[i];
}
else break;
}
for (int i = 0; i < n; i++)
{
if (i == vr) g[i].erase(next(g[i].begin(), 2), g[i].end());
else if (g[i].size()) g[i].erase(next(g[i].begin()), g[i].end());
}
vector<int> rev(m, 0);
int cnt = 0, lst = -1;
do
{
int i = g[vr].begin()->second;
g[vr].erase(g[vr].begin());
if (lst != -1) g[U[lst]].insert({ V[lst],lst });
lst = i;
ans.push_back(i);
vr = V[i];
swap(U[i], V[i]);
if (rev[i]) cnt--;
else cnt++;
rev[i] ^= 1;
} while (cnt);
reverse(path.begin(), path.end());
for (int i : path) ans.push_back(i);
return ans;
}
