#include "Ali.h"
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace Ali{
const int M=1429, SZ=13;
int n;
vector<vector<int>> g, g2;
vector<int> par, dep, ID;
vector<vector<int>> f;
vector<vector<vector<int>>> tr;
vector<vector<int>> cc;
pair<int, int> get(int id){
for (int i=0; i<M; ++i){
if (id>=M-i) id-=M-i;
else return {i, i+id};
}
return {-1, -1};
}
int get(pair<int, int> t){
int ans=0;
for (int i=0; i<t.first; ++i) ans+=M-i;
ans+=t.second-t.first;
return ans;
}
void dfs(int u, int p){
f[u][1]=1;
par[u]=p;
dep[u]=p==-1?0:dep[p]+1;
reverse(g[u].begin(), g[u].end());
for (int v:g[u]) if (v!=p){
vector<int> ff(SZ+1, 1e9), gg(SZ+1, -1);
dfs(v, u);
for (int j=1; j<=SZ; ++j) for (int k=0; k<=SZ-j; ++k){
if (ff[j+k]>f[u][j]+f[v][k]-(!!k)){
ff[j+k]=f[u][j]+f[v][k]-(!!k);
gg[j+k]=k;
}
}
tr[u].push_back(gg);
f[u]=ff;
}
reverse(g[u].begin(), g[u].end());
f[u][0]=*min_element(f[u].begin()+1, f[u].end());
}
void trace(int u, int i, int p, int id){
if (i==0){
i=min_element(f[u].begin()+1, f[u].end())-f[u].begin();
id=cc.size();
cc.emplace_back(1, u);
}else cc[id].push_back(u);
int t=tr[u].size();
for (int v:g[u]) if (v!=p){
--t;
int w=tr[u][t][i];
if (w) g2[u].push_back(v);
trace(v, w, u, id);
i-=w;
}
}
int dist(int u, int 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;
}
void init(int N, vector<int> U, vector<int> V){
n=N;
g.assign(n, {});
g2.assign(n, {});
tr.assign(n, {});
f.assign(n, vector<int>(SZ+1, 1e9));
cc.clear();
for (int i=0; i<n-1; ++i) g[U[i]].push_back(V[i]), g[V[i]].push_back(U[i]);
par.resize(n, 0); dep.resize(n, 0); ID.resize(n, 0);
dfs(0, -1);
trace(0, 0, -1, -1);
for (int i=0; i<(int)cc.size(); ++i){
for (int j=0; j<(int)cc[i].size(); ++j) SetID(cc[i][j], i*SZ+j), ID[cc[i][j]]=i*SZ+j;
}
}
string SendA(string S){
string ans;
int gx=0, gy=0;
int t=0;
for (int i=0; i<20; ++i) t|=(S[i]-'0')<<i;
tie(gx, gy)=get(t);
if (gx==gy){
for (int i=1; i<SZ; ++i){
int id=i<(int)cc[gx].size()?ID[par[cc[gx][i]]]%SZ:0;
for (int j=0; j<4; ++j){
ans.push_back('0'+(id>>j&1));
}
}
}else{
int ux=cc[gx][0], uy=cc[gy][0];
int u=uy;
while (u!=-1 && ID[u]/SZ!=gx) u=par[u];
if (u!=-1) ux=u;
for (int i=0; i<4; ++i) ans.push_back('0'+((ID[ux]%SZ)>>i&1));
for (int i=0; i<SZ; ++i) if (i!=ID[ux]%SZ){
int d=i<(int)cc[gx].size()?dist(ux, cc[gx][i]):0;
for (int j=0; j<4; ++j) ans.push_back('0'+(d>>j&1));
}
for (int i=0; i<SZ; ++i) if (i!=ID[uy]%SZ){
int d=i<(int)cc[gy].size()?dist(uy, cc[gy][i]):0;
for (int j=0; j<4; ++j) ans.push_back('0'+(d>>j&1));
}
int d=dist(ux, uy);
int lg=__lg(n*2-1);
for (int i=0; i<lg; ++i) ans.push_back('0'+(d>>i&1));
}
return ans;
}
}
void Init(int N, std::vector<int> U, std::vector<int> V) {
Ali::init(N, U, V);
}
std::string SendA(std::string S) {
return Ali::SendA(S);
}
#include "Benjamin.h"
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace Benjamin{
const int M=1429, SZ=13;
int n, x, y;
pair<int, int> get(int id){
for (int i=0; i<M; ++i){
if (id>=M-i) id-=M-i;
else return {i, i+id};
}
return {-1, -1};
}
int get(pair<int, int> t){
int ans=0;
for (int i=0; i<t.first; ++i) ans+=M-i;
ans+=t.second-t.first;
return ans;
}
string SendB(int N, int X, int Y){
n=N, x=X, y=Y;
if (x>y) swap(x, y);
int gx=x/SZ, gy=y/SZ;
int t=get({gx, gy});
string ans;
for (int i=0; i<20; ++i) ans.push_back('0'+(t>>i&1));
return ans;
}
int Answer(string T){
int gx=x/SZ, gy=y/SZ;
int ans=-1;
if (gx==gy){
vector<int> par(SZ);
par[0]=-1;
for (int i=1; i<SZ; ++i){
for (int j=0; j<4; ++j) par[i]|=(T[(i-1)*4+j]-'0')<<j;
}
vector<int> vx, vy;
x%=SZ, y%=SZ;
while (x!=-1) vx.push_back(x), x=par[x];
while (y!=-1) vy.push_back(y), y=par[y];
reverse(vx.begin(), vx.end());
reverse(vy.begin(), vy.end());
int id=0;
while (id<(int)vx.size() && id<(int)vy.size() && vx[id]==vy[id]) ++id;
ans=(int)vx.size()+(int)vy.size()-id*2;
}else{
int ux=0, uy=0, id=0;
for (int i=0; i<4; ++i) ux|=(T[id++]-'0')<<i;
x%=SZ, y%=SZ;
int dx=0, dy=0;
for (int i=0; i<SZ; ++i) if (i!=ux){
int d=0;
for (int j=0; j<4; ++j) d|=(T[id++]-'0')<<j;
if (x==i) dx=d;
}
for (int i=0; i<SZ; ++i) if (i!=uy){
int d=0;
for (int j=0; j<4; ++j) d|=(T[id++]-'0')<<j;
if (y==i) dy=d;
}
int d=0;
int lg=__lg(n*2-1);
for (int i=0; i<lg; ++i) d|=(T[id++]-'0')<<i;
ans=dx+dy+d;
}
return ans;
}
}
std::string SendB(int N, int X, int Y) {
return Benjamin::SendB(N, X, Y);
}
int Answer(std::string T) {
return Benjamin::Answer(T);
}
