#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
struct state {
int moves, cur, lst;
vi steps, config;
};
int n, m;
vector<vi> adj;
vi istate;
variant<bool, vi> find_journey(int N, int M, vi U, vi V) {
n = N; m = M; istate.assign(n, 0); adj.resize(n);
for (int i = 0; i < M; i++) {
adj[U[i]].push_back(i);
adj[V[i]].push_back(i);
}
queue<state> q;
q.push(state{1, 0, -1, vector<int>(1, 0), vector<int>(m, 0)});
int lim = 5*M, step = 0;
while (!q.empty() && step++ < lim) {
auto st = q.front(); q.pop();
if (st.cur == 0 && st.moves > 1 && *max_element(st.config.begin(), st.config.end()) == 0) {
return st.steps;
}
for (auto v : adj[st.cur]) {
if (v != st.lst && ((U[v] == st.cur && st.config[v] == 0) || (V[v] == st.cur && st.config[v] == 1))) {
auto ns = state{st.moves, st.cur, st.lst, st.steps, st.config};
ns.moves++; ns.cur = (U[v] == st.cur ? V[v] : U[v]);
ns.config[v] = 1-ns.config[v]; ns.steps.push_back(ns.cur); ns.lst = v;
q.push(ns);
}
}
}
return false;
}
