#include "islands.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
const int N = 100'010;
vector<pii> A[N];
bool vis[N];
bool anc[N];
vector<int> ans;
void answer(int v, int p)
{
vector<int> vec;
for (auto [u, e] : A[v]) {
if (u == p)
continue;
vec.push_back(e);
}
vector<int> tmp = ans;
ans.push_back(vec[0]^0);
ans.push_back(vec[0]^1);
ans.push_back(vec[1]^0);
ans.push_back(vec[1]^1);
ans.push_back(vec[0]^0);
ans.push_back(vec[0]^1);
ans.push_back(vec[1]^0);
ans.push_back(vec[1]^1);
reverse(tmp.begin(), tmp.end());
ans.insert(ans.end(), tmp.begin(), tmp.end());
}
bool dfs(int v, int p)
{
if (A[v].size() - (p != -1) >= 2) {
answer(v, p);
return 1;
}
for (auto [u, e] : A[v]) {
if (u == p)
continue;
ans.push_back(e);
if (dfs(u, v))
return 1;
ans.pop_back();
}
return 0;
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
Loop (i,0,M)
A[U[i]].push_back({V[i], i});
if (!dfs(0, -1))
return false;
return ans;
}
