#include <bits/stdc++.h>
using namespace std;
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
vector<vector<pair<int, int>>> adj(N);
for (int i = 0; i < M; ++i) {
if (i % 2 == 0) {
adj[U[i]].push_back({V[i], i}), adj[V[i]].push_back({U[i], i});
}
}
vector<int> vis_edge(M);
int good = 0;
vector<int> ans;
auto add = [&](int idx, int u, int v) {
return U[idx] == u ? idx : idx + 1;
};
auto dfs = [&](auto &&self, int u) {
vector<int> chs;
for (auto &[i, idx] : adj[u]) {
if (vis_edge[idx]) {
continue;
}
chs.push_back(idx);
}
if (chs.empty()) {
return;
}
if (chs.size() == 1) {
vis_edge[chs[0]] = true;
int v = U[chs[0]] + V[chs[0]] - u;
int idx = add(chs[0], u, v);
ans.push_back(idx);
self(self, v);
ans.push_back(idx);
return;
}
good = 1;
int v1 = U[chs[0]] + V[chs[0]] - u;
int v2 = U[chs[1]] + V[chs[1]] - u;
int a1 = add(chs[0], u, v1);
int a2 = add(chs[0], v1, u);
int a3 = add(chs[1], u, v2);
int a4 = add(chs[1], v2, u);
ans.push_back(a1);
ans.push_back(a2);
ans.push_back(a3);
ans.push_back(a4);
ans.push_back(a2);
ans.push_back(a1);
ans.push_back(a4);
ans.push_back(a3);
};
dfs(dfs, 0);
if (!good) {
return false;
}
return ans;
}
#ifdef MACOS_LOCAL
#include "grader.cpp"
#endif
