#include <iostream>
#include <vector>
#include "conveyor.h"
using namespace std;

// #include <cstdio>
// #include <cstdlib>
// #include <random>
// #include <utility>
// #include <vector>

// namespace {

// const int INVALID_X_LENGTH = 1;
// const int INVALID_X_RANGE = 2;
// const int INVALID_Y_LENGTH = 3;
// const int INVALID_Y_RANGE = 4;
// const int QUERY_LIMIT_EXCEEDED = 5;
// const int INVALID_A_LENGTH = 6;
// const int INVALID_A_RANGE = 7;
// const int WRONG_A = 8;
// const int ANSWER_TWICE = 9;
// const int NO_ANSWER = 10;

// const int QUERY_LIMIT = 30;

// int N;
// std::vector<int> A, B, C;

// int query_count = 0;
// bool answered = false;

// void WrongAnswer(int code) {
//   printf("Wrong Answer [%d]\n", code);
//   exit(0);
// }

// std::mt19937 rng(0);

// int random_select(const std::vector<int> &v) {
//   return v[std::uniform_int_distribution<int>(0, v.size() - 1)(rng)];
// }

// } // namespace

// std::vector<int> Query(std::vector<int> x, std::vector<int> y) {
//   // cout << "querying: ";
//   // for(auto val : y) cout << val << " "; cout << endl;
//   if (int(x.size()) != N - 1) {
//     WrongAnswer(INVALID_X_LENGTH);
//   }
//   for (int i = 0; i < N - 1; i++) {
//     if (x[i] != 0 && x[i] != 1) {
//       WrongAnswer(INVALID_X_RANGE);
//     }
//   }
//   if (int(y.size()) != N) {
//     WrongAnswer(INVALID_Y_LENGTH);
//   }
//   for (int i = 0; i < N; i++) {
//     if (y[i] != 0 && y[i] != 1) {
//       WrongAnswer(INVALID_Y_RANGE);
//     }
//   }
//   query_count++;
//   if (query_count > QUERY_LIMIT) {
//     WrongAnswer(QUERY_LIMIT_EXCEEDED);
//   }
//   std::vector<int> z(N, 0);
//   std::vector<std::vector<int>> t(N);
//   for (int i = 0; i < N - 1; i++) {
//     int a = A[i], b = B[i];
//     if (x[i] ^ C[i]) {
//       std::swap(a, b);
//     }
//     t[a].push_back(b);
//   }
//   for (int i = 0; i < N; i++) {
//     if (y[i]) {
//       if (t[i].empty()) {
//         // cout << "stayed at node " << i << endl;
//         z[i] = 1;
//       } else {
//         int nxt = random_select(t[i]);
//         // cout << i << " to " << nxt << endl;
//         z[nxt] = 1;
//       }
//     }
//   }
//   return z;
// }

// void Answer(std::vector<int> a) {
//   if (answered) {
//     WrongAnswer(ANSWER_TWICE);
//   }
//   answered = true;
//   if (int(a.size()) != N - 1) {
//     WrongAnswer(INVALID_A_LENGTH);
//   }
//   for (int i = 0; i < N - 1; i++) {
//     if (a[i] != 0 && a[i] != 1) {
//       WrongAnswer(INVALID_A_RANGE);
//     }
//   }
//   if (a != C) {
//     WrongAnswer(WRONG_A);
//   }
// }

#define pii pair<int, int>
#define ff first
#define ss second

const int MAXN = 1e5 + 5;

int n;
vector<pii> adj[MAXN];
bool vis[MAXN];
int dep[MAXN], idx[MAXN], par[MAXN];
pii edges[MAXN];
vector<int> ans;
vector<int> which;
int d;

void dfs(int u, int p) {
  par[u] = p;
    for(auto [v, i] : adj[u]) {
        if(v == p) continue;
        idx[v] = i; dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}

void magic() {
    which.clear();
    for(int i = 0; i < n; ++i) vis[i] = true;

    for(int i = 0; i < n - 1; ++i) {
        if(ans[i] == -1) vis[edges[i].ff] = vis[edges[i].ss] = false;
    }

    int freq[] = {0, 0, 0};

    for(int i = 0; i < n; ++i) {
        if(vis[i]) continue;
        ++freq[dep[i] % 3];
    }

    int mx = max(freq[0], max(freq[1], freq[2]));
    if(freq[0] == mx) d = 0;
    else if(freq[1] == mx) d = 1;
    else d = 2;

    if(mx == 0) return;

    // cout << "max missing of depth " << cnt << endl;

    vector<int> belt(n - 1, 0), tables(n, 0);

    for(int i = 0; i < n; ++i) {
        if(dep[i] % 3 == d) tables[i] = 1;
    }

    // cout << "tables: ";
    // for(auto table : tables) cout << table << " "; cout << endl;

    for(int i = 0; i < n - 1; ++i) {
        if(ans[i] == -1) continue;

        if(dep[edges[i].ff] % 3 == d) belt[i] = 1 - ans[i];
        else belt[i] = ans[i];
    }

    which = Query(belt, tables);
}

void Solve(int _n, vector<int> a, vector<int> b) {
	  n = _n;

    ans.resize(n - 1);
    for(int i = 0; i < n - 1; ++i) {
        edges[i] = {a[i], b[i]};
        adj[a[i]].push_back({b[i], i});
        adj[b[i]].push_back({a[i], i});
        ans[i] = idx[i] = -1;
    }

    dfs(0, -1);

    while(true) {
        magic();

        if(which.empty()) {
            Answer(ans); return;
        }

        for(int u = 0; u < n; ++u) {
            if(dep[u] % 3 != d) continue;

            bool up = true;
            for(auto [v, i] : adj[u]) {
                if(v == par[u]) continue;
                if(which[v]) {
                    // cout << "found" << endl;
                    up = false;
                    if(edges[i].ff == u) ans[i] = 0;
                    else ans[i] = 1;
                }
            }

            if(which[u]) {  // all point inwards
                // cout << "all inwards" << endl;
                up = false;
                for(auto [v, i] : adj[u]) {
                    if(v == par[u]) continue;
                    if(ans[i] == -1) {
                        if(edges[i].ff == u) ans[i] = 1;
                        else ans[i] = 0;
                    }
                }

                if(idx[u] != -1) {
                    if(ans[idx[u]] == -1) {
                        // cout << "updated up" << endl;
                        if(edges[idx[u]].ff == u) ans[idx[u]] = 1;
                        else ans[idx[u]] = 0;
                    }
                }
            }

            if(up) {
                // cout << "went up" << endl;
                if(edges[idx[u]].ff == u) ans[idx[u]] = 0;
                else ans[idx[u]] = 1;
            }
        }

        // cout << "ans: ";
        // for(auto val : ans) cout << val << " ";
        // cout << endl;
    }
}

// int main() {
//   if (scanf("%d", &N) != 1) {
//     fprintf(stderr, "Error while reading input.\n");
//     exit(1);
//   }
//   A.resize(N - 1);
//   B.resize(N - 1);
//   C.resize(N - 1);
//   for (int i = 0; i < N - 1; i++) {
//     if (scanf("%d", &A[i]) != 1) {
//       fprintf(stderr, "Error while reading input.\n");
//       exit(1);
//     }
//   }
//   for (int i = 0; i < N - 1; i++) {
//     if (scanf("%d", &B[i]) != 1) {
//       fprintf(stderr, "Error while reading input.\n");
//       exit(1);
//     }
//   }
//   for (int i = 0; i < N - 1; i++) {
//     if (scanf("%d", &C[i]) != 1) {
//       fprintf(stderr, "Error while reading input.\n");
//       exit(1);
//     }
//   }
//   Solve(N, A, B);
//   if (!answered) {
//     WrongAnswer(NO_ANSWER);
//   }
//   printf("Accepted: %d\n", query_count);
//   return 0;
// }