#include "Ali.h"
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace Ali{
const int N=1e5+1;
const int M=1429, SZ=13;
int n;
vector<int> g[N], g2[N];
int sz[N], par[N], dep[N], ID[N], f[N];
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;
}
vector<vector<int>> cc;
void dfs(int u, int p){
sz[u]=1;
par[u]=p;
dep[u]=p==-1?0:dep[p]+1;
if (p!=-1) g[u].erase(find(g[u].begin(), g[u].end(), p));
for (int v:g[u]) if (v!=p){
dfs(v, u);
if (sz[v]<7){
g2[u].push_back(v);
sz[u]+=sz[v];
}
}
if (sz[u]>=7) cc.emplace_back(1, u);
}
int dp[14];
void dfs2(int u, int id){
if (u!=cc[id][0]) cc[id].push_back(u);
for (int v:g2[u]){
dfs2(v, id);
}
}
int cnt;
void dfs3(int u, int id){
if ((int)g2[u].size()<2){
g2[u].push_back(++cnt);
++sz[cnt];
}else{
if (sz[g2[u][0]]<6) dfs3(g2[u][0], id);
else dfs3(g2[u][1], id);
}
++sz[u];
}
int dfs4(int u){
vector<int> vv;
for (int v:g2[u]){
vv.push_back(dfs4(v));
}
if (g2[u].empty()) return 0;
if (g2[u].size()==1){
return vv[0];
}
if (vv[0]>vv[1]){
swap(vv[0], vv[1]);
swap(g2[u][0], g2[u][1]);
}
int ans=0;
for (int j=0; j<sz[u]-1; ++j) if (j<=sz[u]-j-1 && sz[u]-j-1<7){
if (j==sz[g2[u][0]]){
if (j==sz[u]-j-1){
for (int k=0; k<vv[0]; ++k) ans+=dp[j]-k;
ans+=vv[1]-vv[0];
}else ans+=vv[0]*vv[1];
}else{
if (j==sz[u]-j-1) ans+=dp[j]*(dp[j]+1)/2;
else ans+=dp[j]*dp[sz[u]-j-1];
}
}
return ans;
}
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){
memset(dp, 0, sizeof dp);
dp[0]=1;
dp[1]=1;
for (int i=1; i<14; ++i){
for (int j=0; j<i-1; ++j) if (j<=i-j-1 && i-j-1<7){
if (j==i-j-1) dp[i]+=dp[j]*(dp[j]+1)/2;
else dp[i]+=dp[j]*dp[i-j-1];
}
}
cc.clear();
n=_N;
for (int i=0; i<n*2; ++i) g[i].clear(), g2[i].clear();
for (int i=0; i<n-1; ++i) g[U[i]].push_back(V[i]), g[V[i]].push_back(U[i]);
dfs(0, -1);
if (sz[0]<7) cc.emplace_back(1, 0);
cnt=n;
for (int i=0; i<(int)cc.size(); ++i){
dfs2(cc[i][0], i);
while (sz[cc[i][0]]<13) dfs3(cc[i][0], i);
f[i]=dfs4(cc[i][0]);
cc[i].resize(1);
dfs2(cc[i][0], i);
}
for (int i=0; i<(int)cc.size(); ++i){
for (int j=0; j<(int)cc[i].size(); ++j) if (cc[i][j]<n) 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){
int val=f[gx];
for (int i=0; i<7; ++i) ans.push_back('0'+(val>>i&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;
int val=ID[ux]%SZ;
val=val*66+f[gx];
val=val*66+f[gy];
int d=dist(ux, uy);
val=val*10000+d;
int lg=30;
for (int i=0; i<lg; ++i) ans.push_back('0'+(val>>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;
}
vector<int> g[20];
int dp[14], cnt, par[14], dep[14];
void dfs(int u, int sz, int val){
for (int j=0; j<sz-1; ++j) if (j<=sz-j-1 && sz-j-1<7){
int sum=0;
if (j==sz-j-1) sum=dp[j]*(dp[j]+1)/2;
else sum=dp[j]*dp[sz-j-1];
if (val>=sum) val-=sum;
else{
if (j==sz-j-1){
int fx, fy;
for (int k=0; k<=dp[j]; ++k){
if (val>=dp[j]-k) val-=dp[j]-k;
else{
fx=k, fy=fx+val;
break;
}
}
if (j){
++cnt;
par[cnt]=u;
dep[cnt]=dep[u]+1;
g[u].push_back(cnt);
dfs(cnt, j, fx);
}
if (sz-j-1){
++cnt;
par[cnt]=u;
dep[cnt]=dep[u]+1;
g[u].push_back(cnt);
dfs(cnt, sz-j-1, fy);
}
}else{
int fx, fy;
fy=val%dp[sz-j-1], fx=val/dp[sz-j-1];
if (j){
++cnt;
par[cnt]=u;
dep[cnt]=dep[u]+1;
g[u].push_back(cnt);
dfs(cnt, j, fx);
}
if (sz-j-1){
++cnt;
par[cnt]=u;
dep[cnt]=dep[u]+1;
g[u].push_back(cnt);
dfs(cnt, sz-j-1, fy);
}
}
break;
}
}
}
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;
}
int Answer(string T){
memset(dp, 0, sizeof dp);
dp[0]=1;
dp[1]=1;
for (int i=1; i<14; ++i){
for (int j=0; j<i-1; ++j) if (j<=i-j-1 && i-j-1<7){
if (j==i-j-1) dp[i]+=dp[j]*(dp[j]+1)/2;
else dp[i]+=dp[j]*dp[i-j-1];
}
}
int gx=x/SZ, gy=y/SZ;
int ans=-1;
if (gx==gy){
int fx=0;
for (int i=0; i<7; ++i) fx|=(T[i]-'0')<<i;
cnt=0;
for (int i=0; i<14; ++i) g[i].clear();
dfs(0, 13, fx);
ans=dist(x%SZ, y%SZ);
}else{
int val=0;
for (int i=0; i<30; ++i) val|=(T[i]-'0')<<i;
int ux=0, fx=0, fy=0, d=0;
d=val%10000, val/=10000;
fy=val%66, val/=66;
fx=val%66, val/=66;
ux=val;
cnt=0;
for (int i=0; i<14; ++i) g[i].clear();
dfs(0, 13, fx);
int dx=dist(ux, x%SZ);
cnt=0;
for (int i=0; i<14; ++i) g[i].clear();
dfs(0, 13, fy);
int dy=dist(0, y%SZ);
ans=d+dx+dy;
}
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);
}
