// Source: https://usaco.guide/general/io

#include "conveyor.h"

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <bitset>

// #define int long long
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()

using namespace std;

const int inf = (int) 1e9;

vector<vector<pair<int, int>>> adj;

vector<int> idx, parent, edge_idx;

void dfs(int c, int p, int e) {
	parent[c] = p;
	edge_idx[c] = e;

	for (auto n : adj[c]) {
		if (n.first != p) {
			idx[n.first] = (idx[c] + 1) % 3;
			dfs(n.first, c, n.second);
		}
	}
}

pair<int, int> combine(const pair<int, int> &a, const pair<int, int> b) {
	if (b.first > a.first) {
		return b;
	}

	return a;
}

void Solve(int N, vector<int> arr, vector<int> brr) {
	adj.resize(N); idx.resize(N); parent.resize(N); edge_idx.resize(N);

	for (int i = 0; i < N - 1; i++) {
		adj[arr[i]].push_back({brr[i], i});
		adj[brr[i]].push_back({arr[i], i});
	}

	for (int i = 0; i < N; i++) {
		// start from leaf
		if (sz(adj[i]) == 1) {
			dfs(i, -1, -1); break;
		}
	}

	vector<int> ans(N - 1, inf); // inf means don't know

	while (true) {
		vector<int> ct(3, 0);

		pair<int, int> best = {0, 0};

		for (int i = 0; i < N; i++) {
			int tmp = 0;

			for (auto n : adj[i]) {
				tmp |= (ans[n.second] == inf);
			}

			if (tmp) {
				if (ct[idx[i]] == inf) {
					ct[idx[i]] = 0;
				} else if (ct[idx[i]] == 0) {
					ct[idx[i]]++;
				}
			}

			best = combine(best, make_pair(ct[idx[i]], idx[i]));
		}

		// query
		vector<int> xrr(N - 1, 0), yrr(N, 0);

		for (int i = 0; i < N; i++) {
			if (idx[i] == best.second) {
				yrr[i] = 1;
			}
		}

    	for (int i = 0; i < N; i++) {
      		if (yrr[i]) {
        		for (auto n : adj[i]) {
          			if (ans[n.second] == 0 && arr[n.second] == i) {
						xrr[n.second] = 1;
					}

          			if (ans[n.second] == 1 && brr[n.second] == i) {
						xrr[n.second] = 1;
					}
        		}
      		}
    	}

		vector<int> query = Query(xrr, yrr);

		for (int i = 0; i < N; i++) {
			if (!yrr[i]) {
				continue;
			}

			if (query[i]) {
				for (auto n : adj[i]) {
					if (xrr[n.second]) { // reversed
						if (n.first == brr[n.second]) {
							// a -> b reversed (b -> a) doesn't work
							ans[n.second] = 0;
						} else {
							// b -> a reversed (a -> b) doesn't work
							ans[n.second] = 1;
						}
					} else {
						// not reversed
						if (n.first == brr[n.second]) {
							// a -> b normal doesn't work
							ans[n.second] = 1;
						} else {
							// b -> a normal doesn't work
							ans[n.second] = 0;
						}
					}
				}
			} else {
				for (auto n : adj[i]) {
					if (query[n.first]) {
						if (xrr[n.second]) { // reversed
							if (n.first == brr[n.second]) {
								// a -> b reversed (b -> a) works
								ans[n.second] = 1;
							} else {
								// b -> a reversed (a -> b) works
								ans[n.second] = 0;
							}
						} else { // not reversed
							if (n.first == brr[n.second]) {
								// a -> b normal works
								ans[n.second] = 0;
							} else {
								// b -> a normal works
								ans[n.second] = 1;
							}
						}
					}
				}
			}
		}

		bool good = true;

		for (int i = 0; i < N - 1; i++) {
			if (ans[i] == inf) {
				good = false; break;
			}
		}

		if (good) {
			break;
		}
	}

	Answer(ans);
}