#include <bits/stdc++.h>
#include "conveyor.h"

using namespace std;

constexpr int N = 1e5 + 10;

int dep[N], deg[N];

vector<int> G[N], d[4];

void Solve(int n, vector<int> a, vector<int> b) {
    function<void(int, int)> dfs = [&](int u, int fa) {
        for (int i : G[u]) {
            int v = u ^ a[i] ^ b[i];
            if (v != fa) dep[v] = dep[u] + 1, dfs(v, u);
        }
    };
    
    vector<int> dir(n - 1, -1);
    for (int i = 0; i < n - 1; i++) {
        G[a[i]].emplace_back(i), G[b[i]].emplace_back(i);
        deg[a[i]]++, deg[b[i]]++;
    }
    dfs(0, -1);
    for (int i = 0; i < n; i++) d[dep[i] % 3].emplace_back(i);
    while (!d[0].empty()) {
        vector<int> V(n), E(n - 1);
        for (int u : d[0]) {
            V[u] = 1;
            for (int i : G[u]) {
                if ((u == a[i] && dir[i] == 0) || (u == b[i] && dir[i] == 1)) E[i] = 1;
            }
        }
        auto now = Query(E, V);
        for (int u : d[0]) {
            if (now[u]) {
                for (int i : G[u]) {
                    if (dir[i] == -1) {
                        dir[i] = u == b[i] ? 0 : 1;
                        deg[a[i]]--, deg[b[i]]--;
                    }
                }
            } else {
              for (int i : G[u]) {
                  if (dir[i] == -1 && now[u ^ a[i] ^ b[i]]) {
                      dir[i] = u == a[i] ? 0 : 1;
                      deg[a[i]]--, deg[b[i]]--;
                  }
              }
            }
        }
        for (int i = 0; i < 3; i++) {
            for (int j = d[i].size() - 1; j >= 0; j--) {
                if (!deg[d[i][j]]) d[i].erase(d[i].begin() + j);
            }
        }
        sort(d, d + 3, [&](vector<int> x, vector<int> y) {return x.size() > y.size();});
    }
    Answer(dir);
}