#include "conveyor.h"
#include <bits/stdc++.h>
using namespace std;

void Solve1(int N, vector<int> A, vector<int> B) {
	vector<vector<pair<int,int>>> adj(N);
	for(int i=0;i<N-1;i++){
		adj[A[i]].emplace_back(B[i],i);
		adj[B[i]].emplace_back(A[i],i);
	}
	vector<pair<int,int>> p(N);
	function<void(int,int)> dfs = [&](int x,int par){
		for(auto[v,i]:adj[x]){
			if(v==par)p[x]={v,i};
			else dfs(v,x);
		}
	};
	dfs(0,0);
	vector<int> ans(N-1);
	vector<bool> vis(N);
	vis[0]=true;
	for(int moves=0;moves<N-1;moves++){
		for(int v=0;v<N;v++){
			if(vis[v])continue;
			vector<int> directions(N-1),products(N);
			products[v]=1;
			for(auto[child,idx]:adj[v]){
				if(child==p[v].first)continue;
				if(!vis[child])continue;
				if(A[idx]==v and ans[idx]==0)directions[idx]=1;
				if(B[idx]==v and ans[idx]==1)directions[idx]=1;
			}
			auto t = Query(directions,products);
			if(t[v]){
				vis[v]=true;
				int idx = p[v].second;
				if(A[idx]==v)ans[idx]=1;
			} else if(t[p[v].first]){
				vis[v]=true;
				int idx = p[v].second;
				if(B[idx]==v)ans[idx]=1;
			} else {
				for(int impacted=0;impacted<N;impacted++){
					if(t[impacted]==0)continue;
					int idx = p[impacted].second;
					vis[impacted]=true;
					if(A[idx]==impacted)ans[idx]=1;
				}
			}
		}
	}
	Answer(ans);
}


void Solve(int N, vector<int> A, vector<int> B) {
	if(N<=30){
		Solve1(N,A,B);
		return;
	}
	vector<vector<pair<int,int>>> adj(N);
	for(int i=0;i<N-1;i++){
		adj[A[i]].emplace_back(B[i],i);
		adj[B[i]].emplace_back(A[i],i);
	}
	vector<pair<int,int>> p(N);
	vector<int> depth(N);
	vector<pair<int,int>> nodes = {{0,0},{0,1},{0,2}};
	function<void(int,int,int)> dfs = [&](int x,int par,int dep){
		depth[x] = dep;
		nodes[dep%3].first++;
		for(auto[v,i]:adj[x]){
			if(v==par)p[x]={v,i};
			else dfs(v,x,dep+1);
		}
	};
	dfs(0,0,0);
	vector<int> ans(N-1);
	vector<bool> vis(N);
	vis[0]=true;
	nodes[0].first--;
	for(int moves=0;moves<30;moves++){
		int offset = max_element(nodes.begin(),nodes.end())->second;
		vector<int> buffer;
		for(int i=0;i<N;i++)if(!vis[i] and depth[i]%3==offset)buffer.emplace_back(i);
		vector<int> directions(N-1),products(N);
		for(int&v:buffer){
			products[v]=1;
			for(auto[child,idx]:adj[v]){
				if(child==p[v].first)continue;
				if(!vis[child])continue;
				if(A[idx]==v and ans[idx]==0)directions[idx]=1;
				if(B[idx]==v and ans[idx]==1)directions[idx]=1;
			}
		}
		auto t = Query(directions,products);
		for(int&v:buffer){
			bool done = false;
			if(t[v]){
				vis[v]=true;
				nodes[depth[v]%3].first--;
				int idx = p[v].second;
				if(A[idx]==v)ans[idx]=1;
				done = true;
			} 
			if(!done){
				for(auto[impacted,i]:adj[v]){
					if(impacted==p[v].first)continue;
					if(t[impacted]==0)continue;
					int idx = p[impacted].second;
					vis[impacted]=true;
					nodes[depth[impacted]%3].first--;
					if(A[idx]==impacted)ans[idx]=1;
					done=true;
				}
			} 
			if(!done){
				vis[v]=true;
				int idx = p[v].second;
				nodes[depth[v]%3].first--;
				if(B[idx]==v)ans[idx]=1;
			} 
		}
	}
	Answer(ans);
}