#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);
	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 offset=0;offset<3;offset++){
		for(int moves=0;moves<2;moves++){
			vector<int> buffer;
			for(int i=offset;i<N;i+=3)if(!vis[i])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){
				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 {
					int impacted = v+1;
					if(t[impacted]==0)continue;
					int idx = p[impacted].second;
					vis[impacted]=true;
					if(A[idx]==impacted)ans[idx]=1;
				}
			}
		}
	}
	Answer(ans);
}