#include "Ali.h"
#include <string>
#include <vector>
#include <set>
#include <iostream>
#include <cassert>
using namespace std;
#define pb push_back
namespace {
const int THR=20;
const int MXG=1000;
const int B=22;
const int N=10050;
const int L=15;
int gid;
int idx[N];
string enc[N];
vector<int> nodes[N];
int sz[N];
set<pair<int,int>> bad;
vector<int> E[N];
int group[N],myIdx[N];
int par[N][L],dep[N];
}
void DFSEZ(int u,int p){
par[u][0]=p;
dep[u]=dep[p]+1;
for(int i=1;i<L;i++)par[u][i]=par[par[u][i-1]][i-1];
for(int v:E[u]){
if(v!=p){
DFSEZ(v,u);
}
}
}
int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=L-1;i>=0;i--)if(dep[par[u][i]]>=dep[v])u=par[u][i];
for(int i=L-1;i>=0;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
return u==v?v:par[v][0];
}
int DIST(int u,int v){
return dep[u]+dep[v]-2*dep[LCA(u,v)];
}
void DFS(int u,int p){
sz[u]=1;
for(int v:E[u]){
if(v==p)continue;
if(bad.count({u,v}))continue;
DFS(v,u);
sz[u]+=sz[v];
}
}
pair<int,int> Find(int u,int p,int n){
for(int v:E[u]){
if(v==p)continue;
if(bad.count({u,v}))continue;
if(sz[v]*3>=n-1 && (n-sz[v])*3>=n-1){
return {u,v};
}
auto tmp=Find(v,u,n);
if(tmp.first!=-1)return tmp;
}
return {-1,-1};
}
void Mark(int u,int p,int g){
group[u]=g;
myIdx[u]=idx[g]++;
nodes[g].pb(u);
//printf("%i ",u);
for(int v:E[u]){
if(v==p)continue;
if(bad.count({u,v}))continue;
enc[g]+='1';
Mark(v,u,g);
enc[g]+='0';
}
}
void Centroid(int u){
DFS(u,u);
if(sz[u]<=THR){
//printf("Group(%i) => ",gid);
Mark(u,u,gid);
gid++;
//printf("\n");
}else{
pair<int,int> edg=Find(u,u,sz[u]);
assert(edg.first!=-1);
bad.insert(edg);
bad.insert({edg.second,edg.first});
Centroid(edg.first);
Centroid(edg.second);
}
}
void Init(int N, std::vector<int> U, std::vector<int> V) {
for(int i=0;i<N;i++){
for(int j=0;j<L;j++){
par[i][j]=0;
}
dep[i]=0;
E[i].clear();
gid=0;
idx[i]=0;
group[i]=0;
myIdx[i]=0;
nodes[i].clear();
enc[i]="";
}
bad.clear();
for(int i=0;i<N-1;i++){
E[U[i]].pb(V[i]);
E[V[i]].pb(U[i]);
}
DFSEZ(0,0);
Centroid(0);
for(int i=0;i<N;i++){
SetID(i,group[i]*THR+myIdx[i]);
}
}
std::string SendA(std::string S) {
int val=0;
for(int i=0;i<20;i++){
val=val*2;
if(S[i]=='1')val++;
}
int GX=val/MXG;
int GY=val%MXG;
int dist=0;
int IX=0;
int IY=0;
if(GX!=GY){
dist=N*2;
int ii=0;
for(int i:nodes[GX]){
int jj=0;
for(int j:nodes[GY]){
int d=DIST(i,j);
if(dist>d){
dist=d;
IX=ii;
IY=jj;
}
jj++;
}
ii++;
}
}
int num=dist*THR*THR+IX*THR+IY;
string ans="";
for(int i=B-1;i>=0;i--){
if(num>>i&1)ans+="1";
else ans+="0";
}
ans+=enc[GX]+"0"+enc[GY];
//cout << ans << endl;
return ans;
}
#include "Benjamin.h"
#include <string>
#include <vector>
#include <stack>
#include <cassert>
using namespace std;
namespace {
const int THR=20;
const int MXG=1000;
const int B=22;
int GX,GY,UX,UY,n;
vector<int> E[THR];
int par[THR],dep[THR];
}
int Rec(string T,int ptr){
//printf("REC\n");
for(int i=0;i<THR;i++){
E[i].clear();
par[i]=0;
dep[i]=0;
}
stack<int> now;
now.push(0);
int idx=0;
while(ptr<T.size()){
if(T[ptr]=='1'){
idx++;
par[idx]=now.top();
//printf("%i -> %i\n",par[idx],idx);
dep[idx]=dep[now.top()]+1;
now.push(idx);
}else{
now.pop();
if(now.empty()){
return ptr;
}
}
ptr++;
}
return ptr;
}
int Dist(int u,int v){
//printf("DIST %i %i\n",u,v);
if(dep[u]<dep[v])swap(u,v);
int ans=0;
while(dep[u]>dep[v]){
u=par[u];
ans++;
}
while(u!=v){
u=par[u];
v=par[v];
ans+=2;
}
return ans;
}
std::string SendB(int N, int X, int Y) {
n=N;
GX=X/THR;
GY=Y/THR;
UX=X%THR;
UY=Y%THR;
//printf("X: (%i, %i) Y: (%i, %i)\n",GX,UX,GY,UY);
int val=GX*MXG+GY;
assert(val<1000000);
string ans="";
for(int i=19;i>=0;i--){
if(val>>i&1)ans+="1";
else ans+="0";
}
return ans;
}
int Answer(std::string T) {
int num=0;
for(int i=0;i<B;i++){
num*=2;
if(T[i]=='1')num++;
}
int dist=num/THR/THR;
int IX=(num/THR)%THR;
int IY=num%THR;
int ptr=Rec(T,B);
int ans=0;
if(GX==GY){
ans=Dist(UX,UY);
}else{
ans=dist+Dist(IX,UX);
Rec(T,ptr+1);
ans+=Dist(IY,UY);
}
return ans;
}
