#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
#define all(x) (x).begin(),(x).end()
int n, m, from[MAXN], to[MAXN], level[MAXN];
vector<int> ans, adj[MAXN];
bool edge_vis[MAXN], flag = false;
stack<int> st;
inline int f(int ind, int v) {
return from[ind] ^ to[ind] ^ v;
}
inline int find_edge(int ind, int u) {
return from[ind] == u ? ind : ind + 1;
}
void dfs(int v) {
if (flag) return;
for (int ind : adj[v]) {
if (flag) return;
if (edge_vis[ind]) continue;
if (level[to[ind]]) {
flag = true;
int r = level[v] - level[to[ind]];
vector<int> cyc;
while (r--) cyc.push_back(st.top()), st.pop(), ans.pop_back();
reverse(all(cyc));
cyc.push_back(ind);
for (int e : cyc) ans.push_back(e);
for (int e : cyc) ans.push_back(e ^ 1);
reverse(all(cyc));
for (int e : cyc) ans.push_back(e);
for (int e : cyc) ans.push_back(e ^ 1);
flag = true;
return;
}
level[to[ind]] = level[v] + 1;
edge_vis[ind] = true;
st.push(ind);
ans.push_back(ind);
dfs(to[ind]);
if (flag) return;
ans.pop_back();
st.pop();
}
}
int cnt_[MAXN];
variant<bool, vector<int>> find_journey(int n_, int m_, vector<int> U_, vector<int> V_) {
n = n_;
m = m_;
for (int i = 0; i < m; i += 2) {
from[i] = U_[i], to[i] = V_[i];
from[i + 1] = from[i], to[i + 1] = to[i];
adj[from[i]].push_back(i);
}
level[0] = 1;
dfs(0);
if (!flag) return false;
while (!st.empty()) ans.push_back(st.top()), st.pop();
for (int e : ans)
cnt_[e]++;
for (int e : ans)
assert(cnt_[e] % 2 == 0);
assert(from[ans.front()] == 0);
assert(from[ans.back()] == 0);
return ans;
}
