#include <bits/stdc++.h>
#include <conveyor.h>
using namespace std;
vector<int> p[3];
vector<pii> g[maxn];
int deg[maxn], fa[maxn], cnt[3];
vector<int> ans;
void dfs(int u, int fu, int dep)
{
fa[u] = fu;
p[dep].emplace_back(u);
for (pii tmp : g[u])
{
int v = tmp.first;
if (v == fu) continue;
dfs(v, u, (dep + 1) % 3);
}
}
void Solve(int N, vector<int> A, vector<int> B)
{
for (int i = 0; i <= N - 2; i++)
{
A[i]++, B[i]++;
deg[A[i]]++, deg[B[i]]++;
g[A[i]].emplace_back(make_pair(B[i], i)), g[B[i]].emplace_back(make_pair(A[i], i));
}
ans.resize(N - 1);
for (int i = 0; i <= N - 2; i++) ans[i] = -1;
dfs(1, 0, 0);
while (1)
{
cnt[0] = cnt[1] = cnt[2] = 0;
for (int i = 0; i < 3; i++)
for (int u : p[i]) if (deg[u]) cnt[i]++;
int pos;
if (cnt[0] > cnt[1] && cnt[0] > cnt[2]) pos = 0;
else if (cnt[1] > cnt[2]) pos = 1;
else pos = 2;
if (!cnt[pos]) break;
vector<int> x, y, res;
x.resize(N - 1), y.resize(N);
for (int u : p[pos])
{
y[u - 1] = 1;
for (pii tmp : g[u])
{
int v = tmp.first, id = tmp.second;
if (ans[id] == -1) continue;
x[id] = (u == A[id]) ^ ans[id];
}
}
res = Query(x, y);
for (int u : p[pos])
{
if (res[u - 1])
{
for (pii tmp : g[u])
{
int v = tmp.first, id = tmp.second;
if (ans[id] != -1) continue;
ans[id] = (u == A[id]);
deg[u]--, deg[v]--;
}
}
else
{
bool Fl = false;
for (pii tmp : g[u])
{
int v = tmp.first, id = tmp.second;
if (v == fa[u]) continue;
if (res[v - 1])
{
Fl = true;
deg[u]--, deg[v]--;
ans[id] = (u != A[id]);
break;
}
}
if (!Fl)
{
for (pii tmp : g[u])
{
int v = tmp.first, id = tmp.second;
if (v == fa[u])
{
deg[u]--, deg[v]--;
ans[id] = (u != A[id]);
break;
}
}
}
}
}
}
Answer(ans);
}