#include "tree.h"
#include<bits/stdc++.h>
using namespace std;
const int MX = 1005;
vector<int > c[MX];int dep[MX];
vector<int > g[MX];int fa[MX][11];
void init(int x,int f){
	fa[x][0] = f;
	for(int i = 1;i <= 10;i++)fa[x][i] = fa[fa[x][i - 1]][i - 1];
}
int lca(int x,int y){
	if(dep[x] < dep[y])swap(x,y);
	for(int i = 10;i >= 0;i--)if(dep[fa[x][i]] >= dep[y])x = fa[x][i];
	if(x == y)return x;
	for(int i = 10;i >= 0;i--)if(fa[x][i] != fa[y][i])x = fa[x][i],y = fa[y][i];
	return fa[x][0];
}
int dist(int x,int y){
	int lc = lca(x,y);
	return dep[x] + dep[y] - 2 * dep[lc];
}
void solve(vector<int > A,vector<int > B){
	/*
	cerr << "solve : \n";
	cerr << "A = ";
	for(auto it : A)cerr << it << ' ';
	cerr << '\n';
	cerr << "B = ";
	for(auto it : B)cerr << it << ' ';
	cerr << '\n';
	*/
	if(A.size() == 1){
		for(auto it : B){answer(it,A[0]);init(it,A[0]);}
		return;
	}
	if(B.size() == 0)return;
	int p = A.size() / 2;vector<int > LA,RA,LB,RB;
	for(int i = 0;i < p;i++)LA.push_back(A[i]);
	for(int i = p;i < A.size();i++)RA.push_back(A[i]);
	set<int > s;
	for(auto it : LA){
		int sum = 0;
		for(auto jt : LA)sum += dist(it,jt);
		s.insert(sum);
	}
	int num = LA.size();
	for(auto it : B){
		int cur = ask(it,LA);
		if(s.find(cur - num) != s.end())LB.push_back(it);
		else RB.push_back(it);
	}
	solve(LA,LB);solve(RA,RB);
}
void solver(int n,int A,int B){
	vector<int > tmp;tmp.push_back(1);
	int mx = 0;c[0].push_back(1);
	for(int i = 2;i <= n;i++){
		dep[i] = ask(i,tmp);
		c[dep[i]].push_back(i);
		mx = max(mx,dep[i]);
	}
	init(1,1);
	for(int i = 0;i < mx;i++){
		/*
		cerr << "solve Layer : \n";
		for(auto it : c[i])cerr << it << ' ';
		cerr << '\n';
		for(auto it : c[i + 1])cerr << it << ' ';
		cerr << '\n';
		*/
		solve(c[i],c[i + 1]);
	}
}