#include "conveyor.h"

#include <vector>
#include<bits/stdc++.h>
# define rep(i, j, k) for (int i = j; i <= k; ++i)
using namespace std;

int n, hd[100005], to[200005], nxt[200005], id[200005], etimer;
int sz[100005], d[100005], p[100005], nt[100005], ppp[100005], son[100005], ly[100005], lbian[100005], maxx;
int ans[100005];
int stk[100005], r;
vector < int > qu[33], ute[33];
void addedge(int u, int v, int ix){to[++etimer] = v, nxt[etimer] = hd[u], hd[u] = etimer; id[etimer] = ix;}
void dfs(int u, int fa)
{
	p[u] = fa, d[u] = d[fa] + 1; sz[u] = 1; son[u] = 0;
	for (int i = hd[u]; i; i = nxt[i]) if (to[i] != fa) {nt[to[i]] = abs(id[i]), ppp[to[i]] = (id[i] < 0); dfs(to[i], u); sz[u] += sz[to[i]]; if (sz[to[i]] > sz[son[u]]) son[u] = to[i];}
}
void dfs_solve(int u, int lye)
{
	ly[u] = lye; maxx = max(maxx, lye);
	if (son[u]) dfs_solve(son[u], lye); else stk[++r] = u;
	for (int i = hd[u]; i; i = nxt[i]) if (to[i] != p[u] && to[i] != son[u]) dfs_solve(to[i], lye + 1);
}
void Solve(int N, std::vector<int> A, std::vector<int> B)
{
	std::vector<int> x(N - 1, 0), y(N, 0), za, zb, a(N - 1, 0);
	rep(i, 1, 30) qu[i] = x, ute[i] = y;
	n = N;
	rep(i, 0, n - 2) addedge(A[i] + 1, B[i] + 1, i + 1), addedge(B[i] + 1, A[i] + 1, -i - 1);
	dfs(1, 0);
	int rt = 1;
	rep(i, 2, n) if (sz[i] >= (n + 1) / 2 && sz[i] < sz[rt]) rt = i;// cerr << rt << endl;
	nt[rt] = 0; dfs(rt, 0);
	dfs_solve(rt, 1);
//	rep(i, 1, n) cerr << i << ' ' << son[i] << '\n';
	for (int i = maxx; i; --i)
	{
		rep(j, 1, r) if (ly[stk[j]] == i)
		{
			int u = stk[j];
			do
			{//cerr << u << endl;
				if (u != rt) qu[2 * i][nt[u] - 1] = 1;
				u = p[u];
			} while (ly[u] == ly[stk[j]]);
		}
		else if (ly[stk[j]] > i)
		{
			int u = stk[j];
			do
			{
				if (u != rt) qu[2 * i - 1][nt[u] - 1] = qu[2 * i][nt[u] - 1] = (ans[nt[u]] ^ ppp[u] ^ 1);
				u = p[u];
			} while (ly[u] == ly[stk[j]]);
		}
		rep(j, 0, n - 1) ute[2 * i - 1][j] = ute[2 * i][j] = 1;
	//	rep(j, 0, n - 2) cerr << qu[2 * i - 1][j] << ' '; cerr << '\n';
	//	rep(j, 0, n - 2) cerr << qu[2 * i][j] << ' '; cerr << '\n';
		za = Query(qu[2 * i - 1], ute[2 * i - 1]), zb = Query(qu[2 * i], ute[2 * i]);
		rep(j, 1, r) if (ly[stk[j]] == i)
		{
			int pos = (za[nt[stk[j]] - 1] == 1), u = stk[j];
			do
			{
				if (u != rt) ans[nt[u]] = (pos ^ ppp[u] ^ 1);
				u = p[u];
				if (u > 0) if (za[u - 1] || zb[u - 1]) pos = !pos;
			} while (ly[u] == ly[stk[j]]);
		}
	}
	rep(i, 0, n - 2) a[i] = ans[i + 1];//, cerr << a[i] << '\n';
	Answer(a);
}