#include "islands.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < ll(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= ll(l); --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];
int height[N];
vector<int> ans;
void answer(int v, int u, int e)
{
ans.push_back(e);
int cnt = height[u] - height[v] + 1;
int pre = ans.size() - cnt;
Loop (i,pre,pre+cnt)
ans.push_back(ans[i]^1);
Loop (i,pre,pre+cnt)
ans.push_back(ans[i]^0);
Loop (i,pre,pre+cnt)
ans.push_back(ans[i]^1);
LoopR (i,0,pre)
ans.push_back(ans[i]);
}
bool dfs(int v, int h)
{
height[v] = h;
vis[v] = 1;
anc[v] = 1;
for (auto [u, e] : A[v]) {
if (anc[u]) {
answer(u, v, e);
return 1;
}
if (vis[u])
continue;
ans.push_back(e);
if (dfs(u, h+1))
return 1;
ans.pop_back();
}
anc[v] = 0;
return 0;
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V) {
for (int i = 0; i < M; i += 2)
A[U[i]].push_back({V[i], i});
if (!dfs(0, 0))
return false;
return ans;
}
