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

#define pii pair<int,int>
#define fs first
#define sc second

namespace ANYA{

	const int mxn = 505;
	const int W = 9;
	vector<pii> tree[mxn];
	int par[mxn];
	int head[mxn];
	int ptr;
	int N;
	bitset<mxn> isp;
	int dep[mxn];
	int cnt[W];
	vector<pii> edges;

	void dfs(int now){
		cnt[dep[now]%W]++;
		for(auto [nxt,w]:tree[now]){
			if(nxt == par[now])continue;
			dep[nxt] = dep[now]+w;
			par[nxt] = now;
			dfs(nxt);
		}
		return;
	}

	void InitAnya(int NN , int A[] , int B[]) {
		cerr<<"INIT ANYA IN!"<<endl;
		N = NN;
		for(int i = 0;i+1<N;i++){
			int a = A[i],b = B[i];
			tree[a].push_back(pii(b,1));
			tree[b].push_back(pii(a,1));
			edges.push_back(pii(a,b));
		}
		dfs(0);
		auto d = min_element(cnt,cnt+W)-cnt;
		for(int i = 0;i<N;i++){
			if(dep[i]%W == d){
				isp[i] = true;
				head[i] = ptr;
				ptr += W;
			}
			else{
				head[i] = ptr++;
			}
		}
		for(auto &[a,b]:edges){
			if(dep[a]>dep[b])swap(a,b);
		}
		cerr<<"INIT ANYA OUT!"<<endl;
		return;
	}

	void writeint(int h,int num,int wid){
		for(int i = 0;i<wid;i++){
			if(num&(1<<i))Save(h+i,1);
			else Save(h+i,0);
		}
		return;
	}

	void Anya(int C[]) {
		for(auto &i:tree)i.clear();
		for(int i = 0;i<edges.size();i++){
			auto &[a,b] = edges[i];
			tree[a].push_back(pii(b,C[i]));
		}
		dfs(0);
		for(int i = 0;i<edges.size();i++){
			auto &[a,b] = edges[i];
			if(isp[b])writeint(head[b],dep[b],W);
			else writeint(head[b],C[i],1);
		}
	}
}

void InitAnya(int NN , int A[] , int B[]) {
	ANYA::InitAnya(NN,A,B);
	return;
}
void Anya(int C[]){
	ANYA::Anya(C);
	return;
}

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

#define pii pair<int,int>
#define fs first
#define sc second

namespace BORIS{

	const int mxn = 505;
	const int W = 9;
	bitset<mxn> isp;
	int dep[mxn],cnt[W],par[mxn],head[mxn];
	vector<pii> tree[mxn];
	int ptr = 0;
	int N;

	void dfs(int now){
		cnt[dep[now]%W]++;
		for(auto [nxt,w]:tree[now]){
			if(nxt == par[now])continue;
			par[nxt] = now;
			dep[nxt] = dep[now]+1;
			dfs(nxt);
		}
		return;
	}

	void InitBoris(int NN , int A[] , int B[]) {
		N = NN;
		for(int i = 0;i+1<N;i++){
			int a = A[i],b = B[i];
			tree[a].push_back(pii(b,1));
			tree[b].push_back(pii(a,1));
		}
		dfs(0);
		int d = min_element(cnt,cnt+W)-cnt;
		for(int i = 0;i<N;i++){
			if(dep[i]%W == d){
				isp[i] = true;
				head[i] = ptr;
				ptr += W;
			}
			else{
				head[i] = ptr++;
			}
		}
		return;
	}

	int readint(int h,int wid){
		int re = 0;
		for(int i = 0;i<wid;i++){
			if(Ask(h+i))re |= 1<<i;
		}
		return re;
	}

	int Boris(int city) {
		int now = city;
		int ans = 0;
		while(now&&!isp[now]){
			ans += readint(head[now],1);
			now = par[now];
		}
		if(now)ans += readint(head[now],W);
		return ans;
	}
}

void InitBoris(int N , int A[] , int B[]) {
	BORIS::InitBoris(N,A,B);
}
int Boris(int city){
	return BORIS::Boris(city);
}