#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);
map<pair<int, int>, int> pq;
for (int i = 0; i < m; i++) {
if (pq[{U[i], V[i]}] >= 2) continue;
pq[{U[i], V[i]}]++;
adj[U[i]].push_back(i);
adj[V[i]].push_back(i);
}
queue<state> q;
q.push(state{0, 0, -1, vector<int>(), vector<int>(m, 0)});
int lim = 1200*m, step = 0;
while (!q.empty() && step++ < lim) {
auto st = q.front(); q.pop();
if (st.cur == 0 && st.moves > 0 && *max_element(st.config.begin(), st.config.end()) == 0) {
return st.steps;
}
// for (auto &el : st.steps) cout << el << " "; cout << "\n";
for (auto v : adj[st.cur]) {
// cout << v << "\n";
if (v != st.lst && ((U[v] == st.cur) == (st.config[v] == 0))) {
auto ns = state{st.moves, st.cur, st.lst, vector<int>(), vector<int>()};
for (auto &el : st.steps) ns.steps.push_back(el);
for (auto &el : st.config) ns.config.push_back(el);
ns.moves++; ns.cur = (U[v] == st.cur ? V[v] : U[v]);
ns.config[v] = 1-ns.config[v]; ns.steps.push_back(v); ns.lst = v;
q.push(ns);
}
}
}
return false;
}
