#include "islands.h"
#include <bits/stdc++.h>
#include <variant>
#include <vector>
using namespace std;
using pii = pair<int, int>;
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
vector<vector<pii>> edges(N);
vector<int> deg(N, 0);
deg[0]++;
for (int i=0; i<M; i+=2)
{
int u = U[i];
int v = V[i];
edges[u].push_back({v, i});
edges[v].push_back({u, i+1});
deg[u]++;
deg[v]++;
}
vector<int> parent(N, -2);
vector<int> parent_canoe(N, -1);
queue<int> visitlist;
parent[0] = -1;
visitlist.push(0);
while (!visitlist.empty())
{
int k = visitlist.front();
visitlist.pop();
if (deg[k] >= 3)
{
int curr = k;
vector<int> return_home;
while (curr!=0)
{
return_home.push_back(parent_canoe[curr]);
curr = parent[curr];
}
int ban = parent_canoe[k];
vector<int> cycled;
for (pii choice: edges[k])
{
int y = choice.second;
if ((y!=ban) and ((y^1)!=ban))
cycled.push_back(y);
}
vector<int> journey;
int ss = return_home.size();
for (int i=ss-1; i>=0; i--)
journey.push_back(return_home[i]);
journey.push_back(cycled[0]);
journey.push_back(cycled[0]^1);
journey.push_back(cycled[1]);
journey.push_back(cycled[1]^1);
journey.push_back(cycled[0]^1);
journey.push_back(cycled[0]);
journey.push_back(cycled[1]^1);
journey.push_back(cycled[1]);
for (int i=0; i<ss; i++)
journey.push_back(return_home[i]);
return journey;
}
for (pii edge: edges[k])
{
int neigh = edge.first;
int canoe = edge.second;
if (parent[neigh] == -2)
{
parent[neigh] = k;
parent_canoe[neigh] = canoe;
visitlist.push(neigh);
}
}
}
return false;
}
