#include <bits/stdc++.h>
#include "conveyor.h"
void Solve(int n, std::vector<int> A, std::vector<int> B) {
std::vector<std::vector<std::pair<int, int>>> gr(n);
for (int i = 0; i < n - 1; i++) {
gr[A[i]].push_back({B[i], 2 * i});
gr[B[i]].push_back({A[i], 2 * i + 1});
}
std::vector<int> prv(n), depth(n);
auto dfs = [&](auto dfs, int v, int f) -> void {
prv[v] = f;
for (auto [t, id] : gr[v]) {
if (t != f) {
depth[t] = depth[v] + 1;
dfs(dfs, t, v);
}
}
};
dfs(dfs, 0, -1);
std::vector<int> ans(n - 1, -1);
while (std::count(ans.begin(), ans.end(), -1)) {
std::vector<int> cnt(n);
for (int i = 0; i < n - 1; i++) {
if (ans[i] == -1) {
cnt[A[i]]++, cnt[B[i]]++;
}
}
std::array<int, 3> shit;
shit.fill(0);
for (int i = 0; i < n; i++) {
shit[depth[i] % 3] += cnt[i] > 0;
}
int mx_id = std::max_element(shit.begin(), shit.end()) - shit.begin();
std::vector<int> put(n);
for (int i = 0; i < n; i++) {
put[i] = depth[i] % 3 == mx_id;
}
std::vector<int> rev(n - 1);
for (int i = 0; i < n - 1; i++) {
if (ans[i] != -1 && (put[A[i]] || put[B[i]])) {
rev[i] = ans[i] ^ put[A[i]] ^ 0;
}
}
auto res = Query(rev, put);
for (int i = 0; i < n; i++) {
if (put[i]) {
int xr = 0;
if (res[i]) {
for (auto [t, id] : gr[i]) {
if (ans[id / 2] == -1)
ans[id / 2] = id % 2 ^ 1 ^ xr;
}
continue;
}
bool suc = false;
for (auto [t, id] : gr[i]) {
if (t != prv[i] && res[t]) {
ans[id / 2] = id % 2 ^ xr;
suc = true;
break;
}
}
if (suc) {
continue;
}
for (auto [t, id] : gr[i]) {
if (res[t]) {
ans[id / 2] = id % 2 ^ xr;
suc = true;
break;
}
}
}
}
}
Answer(ans);
}