#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int n, m, from[MAXN], to[MAXN];
vector<int> ans, adj[MAXN];
bool 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;
}
inline void seven(int a, int b) {
ans.push_back(a);
ans.push_back(a ^ 1);
ans.push_back(b);
ans.push_back(b ^ 1);
ans.push_back(a ^ 1);
ans.push_back(a);
ans.push_back(b ^ 1);
ans.push_back(b);
}
void dfs(int v) {
vector<int> poss;
for (int ind : adj[v])
if (!vis[ind])
poss.push_back(ind);
if (poss.empty()) return;
if (int(poss.size()) == 1) {
int ind = find_edge(poss[0], v);
vis[ind] = true;
st.push(ind ^ 1);
ans.push_back(ind);
dfs(f(ind, v));
} else {
flag = true;
seven(find_edge(poss[0], v), find_edge(poss[1], v));
}
}
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];
adj[from[i]].push_back(i), adj[to[i]].push_back(i);
}
dfs(0);
if (!flag) return false;
while (!st.empty()) ans.push_back(st.top()), st.pop();
return ans;
}
