#include "Ali.h"
#include <bits/stdc++.h>
namespace {
std::vector<int> adjl[10005];
int p[10005][18];
int dep[10005];
void dfs1(int node, int pa){
p[node][0] = pa;
for (auto x : adjl[node]){
if (x==pa) continue;
dep[x] = dep[node]+1;
dfs1(x,node);
}
}
int lca(int a, int b){
if (dep[a]>dep[b]) std::swap(a,b);
int t = dep[b]-dep[a];
for (int x = 0; x<18; x++){
if (t&(1<<x)) b = p[b][x];
}
if (a==b) return a;
for (int x = 17; x>=0; x--){
if (p[a][x]!=p[b][x]){
a = p[a][x];
b = p[b][x];
}
}
return p[a][0];
}
int n;
int getdist(int a, int b){
if (a>=n || b>=n) return 0;
return dep[a]+dep[b]-2*dep[lca(a,b)];
}
}
void Init(int N, std::vector<int> U, std::vector<int> V) {
for (int x = 0; x<N; x++){
adjl[x].clear();
}
for (int x = 0; x<N-1; x++){
adjl[U[x]].push_back(V[x]);
adjl[V[x]].push_back(U[x]);
}
dfs1(0,-1);
n = N;
for (int x = 0; x<N; x++){
SetID(x,2*x+(dep[x]&1));
}
for (int x = 1; x<18; x++){
for (int y = 0; y<N; y++){
if (p[y][x-1]==-1) p[y][x] = -1;
else p[y][x] = p[p[y][x-1]][x-1];
}
}
}
std::string SendA(std::string S) {
int thing = 0;
for (int x = 0; x<20; x++){
if (S[x]=='1') thing += 1<<x;
}
std::string ans;
for (int x = thing; x<n*(n-1)/2; x+=(1<<20)){
int l = 0;
int r = n-1;
while (l+1<r){
int mid = (l+r)/2;
if (x<(mid)*(mid+1)/2){
r = mid;
}
else l = mid;
}
int b = r;
int a = x-(b)*(b-1)/2;
int t = getdist(a,b);
//printf("push val %d %d\n",a,b);
for (int x = 1; x<=13; x++){
ans.push_back((t&(1<<x))?'1':'0');
}
}
return ans;
}
#include "Benjamin.h"
#include <bits/stdc++.h>
namespace {
int storeX,storeY;
int storenum;
}
std::string SendB(int N, int X, int Y) {
int n1 = X/2;
int n2 = Y/2;
storeX = X;
storeY = Y;
std::string ans;
if (n1>n2){
std::swap(n1,n2);
std::swap(X,Y);
std::swap(storeX,storeY);
}
int num = 0;
for (int x = 0; x<n2; x++){
num += x;
}
num += n1;
for (int x = 0; x<20; x++){
ans.push_back((num&(1<<x))?'1':'0');
}
storenum = num;
return ans;
}
int Answer(std::string T) {
if (storeX==storeY) return 0;
int t = storenum>>20;
int ans = 0;
for (int x = 0; x<13; x++){
if (T[t*13+x]=='1'){
ans += (1<<x);
}
}
ans<<=1;
if ((storeX&1)!=(storeY&1)){
ans++;
}
return ans;
}
