#include <bits/stdc++.h>
#include "conveyor.h"
#define N 100011
using namespace std;
struct edge{int v,w,next;edge(){}edge(int _v,int _w,int _next){v=_v;w=_w;next=_next;}}e[N*2];int head[N],sz;
void init(){memset(head,-1,sizeof(head));sz=-1;}void insert(int u,int v,int w){e[++sz]=edge(v,w,head[u]);head[u]=sz;}
int n,dep[N],w[N],sum,buc[3];
void dfs(int u,int f)
{
	dep[u]=dep[f]+1;
	for(int i=head[u];~i;i=e[i].next)if(e[i].v^f)dfs(e[i].v,u);
}
void Solve(int _n,vector<int> A,vector<int> B)
{
	init();
	n=_n;sum=n;
	for(int i=0;i<n-1;++i)insert(A[i],B[i],-1),insert(B[i],A[i],-1),++w[A[i]],++w[B[i]];
	dfs(0,0);
	while(sum)
	{
		int x=0;
		if(buc[1]>buc[x])x=1;if(buc[2]>buc[x])x=2;
		vector<int> X(n-1,0),Y(n,0);
		for(int i=0;i<n;++i)if(dep[i]%3==x&&w[i])
		{
			for(int j=head[i];~j;j=e[j].next)if(~e[j].w)X[j/2]=!e[j].w;
			Y[i]=1;
		}
		vector<int> res=Query(X,Y);
		for(int i=0;i<n;++i)if(dep[i]%3==x&&w[i])
		{
			if(!res[i])
			{
				bool flg=0;
				for(int j=head[i];~j;j=e[j].next)if(!~e[j].w&&res[e[j].v]&&dep[e[j].v]>dep[i]){--w[i],--w[e[j].v],e[j].w=0,e[j^1].w=1;flg=1;break;}
				if(!flg)
				{
					for(int j=head[i];~j;j=e[j].next)if(!~e[j].w&&dep[e[j].v]<dep[i])--w[i],--w[e[j].v],e[j].w=0,e[j^1].w=1;
				}
			}
			else
			{
				for(int j=head[i];~j;j=e[j].next)if(!~e[j].w)--w[i],--w[e[j].v],e[j].w=1,e[j^1].w=0;
			}
		}
		sum=0;for(int i=0;i<n;++i)buc[dep[i]%3]+=!!w[i],sum+=!!w[i];
	}
	vector<int> ans(n-1,0);
	for(int i=0;i<n-1;++i)
	{
		for(int j=head[A[i]];~j;j=e[j].next)if(e[j].v==B[i])ans[i]=e[j].w;
	}
	Answer(ans);
}