#include "Ali.h"
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace {
vector<string> t6{
"0001100111",
"0001011011",
"0000111011",
"0000011111",
"0000101111",
"0001110011",
"0010110011",
"0001101101",
"0000111101",
"0000110111",
"0001011101",
};
vector<string> t7{
"000011100111",
"000011011011",
"000001101111",
"000110110011",
"000011011101",
};
vector<int> st{0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4};
vector<int> add{3, 3, 2, 3, 4, 1, 2, 5, 2, 0, 3};
vector<int> g[14], gg[14];
int d[14], num[14], par[14];
map<vector<int>, int> mp1, mp2;
void clear(){
for (int i=0; i<14; ++i) g[i].clear(), gg[i].clear();
}
void build(string s, int root){
int id=0, cur=0;
auto dfs=[&](auto &&self, int u) -> void {
while (s[id]=='0'){
++id;
++cur;
gg[u].push_back(cur);
self(self, cur);
}
++id;
};
dfs(dfs, 0);
cur=0;
queue<int> q;
q.push(0);
num[0]=cur;
par[num[0]]=-1;
while (q.size()){
int u=q.front(); q.pop();
for (int v:gg[u]){
num[v]=++cur;
g[num[u]].push_back(num[v]);
g[num[v]].push_back(num[u]);
par[num[v]]=num[u];
q.push(v);
}
}
auto dfs2=[&](auto &&self, int u, int p) -> void {
for (int v:g[u]) if (v!=p){
d[v]=d[u]+1;
self(self, v, u);
}
};
d[root]=0;
dfs2(dfs2, root, 0);
}
void gen(){
for (int i=0; i<11; ++i){
for (int j=st[i]; j<5; ++j){
string t="0"+t7[j]+"10"+t6[i]+"1";
clear();
build(t, 0);
vector<int> dd(d, d+14);
if (!mp1.count(dd)) mp1[dd]=mp1.size();
}
}
// cout << mp1.size() << '\n';
set<vector<int>> tt;
for (int i=0; i<11; ++i){
for (int j=st[i]; j<5; ++j){
string t="0"+t7[j]+"10"+t6[i]+"1";
clear();
build(t, 0);
vector<int> ff(d, d+14);
sort(ff.begin(), ff.end());
for (int k=0; k<14; ++k) if ((int)g[k].size()<=2){
clear();
build(t, k);
vector<int> dd(d, d+14);
if (!mp2.count(dd)) mp2[dd]=mp2.size();
}
}
}
// cout << mp2.size() << '\n';
}
}
namespace Ali{
const int N=3e4+1;
const int M=1429, SZ=14;
int n;
vector<int> g[N], g2[N];
int sz[N], par[N], dep[N], ID[N], deg[N];
string 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);
}
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].empty() || ((int)g2[u].size()==1 && sz[g2[u][0]]==6)){
g2[u].push_back(++cnt);
par[cnt]=u;
dep[cnt]=dep[u]+1;
++sz[cnt];
}else{
if (sz[g2[u][0]]<6) dfs3(g2[u][0], id);
else dfs3(g2[u][1], id);
}
++sz[u];
}
void dfs4(int u){
vector<string> vv;
for (int v:g2[u]){
dfs4(v);
vv.push_back(f[v]);
}
if (g2[u].empty()){
f[u]="";
return;
}
if (g2[u].size()==1){
f[u]="0"+vv[0]+"1";
return;
}
if (vv[0]<vv[1] && vv[0].size()<=vv[1].size()){
swap(vv[0], vv[1]);
swap(g2[u][0], g2[u][1]);
}
f[u]="0"+vv[0]+"10"+vv[1]+"1";
}
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){
if (mp1.empty()) gen();
cc.clear();
n=_N;
for (int i=0; i<N; ++i) g[i].clear(), g2[i].clear(), sz[i]=0;
for (int i=0; i<n-1; ++i) g[U[i]].push_back(V[i]), g[V[i]].push_back(U[i]), ++deg[U[i]], ++deg[V[i]];
int root=0;
while ((int)g[root].size()==3) ++root;
dfs(root, -1);
if (sz[root]<7) cc.emplace_back(1, root);
reverse(cc.begin(), cc.end());
cnt=n;
for (int i=0; i<(int)cc.size(); ++i){
int root=cc[i][0];
dfs2(root, i);
while (sz[root]<13) dfs3(root, i);
dfs4(root);
cc[i].resize(1);
dfs2(root, i);
int id0=find(t6.begin(), t6.end(), f[g2[root][0]])-t6.begin();
int id1=find(t6.begin(), t6.end(), f[g2[root][1]])-t6.begin();
assert(id0<11 && id1<11);
int u=cc[i][add[id0]+1];
g2[u].push_back(++cnt);
par[cnt]=u;
dep[cnt]=dep[u]+1;
dfs4(root);
int id=find(t7.begin(), t7.end(), f[g2[root][0]])-t7.begin();
assert(id<5);
vector<int> ord;
ord.push_back(root);
int begin=0;
while (begin<(int)ord.size()){
int u=ord[begin++];
for (int v:g2[u]) ord.push_back(v);
}
cc[i]=ord;
vector<int> dd;
for (int j:cc[i]) dd.push_back(dist(j, cc[i][0]));
assert(mp1.count(dd));
}
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;
}
}
int get1(int id){
vector<int> dd;
for (int j:cc[id]) dd.push_back(dist(cc[id][0], j));
assert(mp1.count(dd));
return mp1[dd];
}
int get2(int id, int root){
vector<int> dd;
for (int j:cc[id]) dd.push_back(dist(root, j));
assert(mp2.count(dd));
return mp2[dd];
}
string get_string(int num){
string ans;
for (int len=1; len<=24; ++len){
if (num<(1<<len)){
for (int j=0; j<len; ++j) ans.push_back('0'+(num>>j&1));
return ans;
}else num-=(1<<len);
}
assert(false);
return "";
}
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 root=cc[gx][0];
int id0=find(t7.begin(), t7.end(), f[g2[root][0]])-t7.begin();
int id1=find(t6.begin(), t6.end(), f[g2[root][1]])-t6.begin();
int val=0;
for (int i=0; i<11; ++i){
for (int j=st[i]; j<5; ++j, ++val){
if (id1==i && j==id0){
ans=get_string(val);
}
}
}
assert(ans.size());
}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 d=dist(ux, uy);
int val=0;
if (d>=5020){
val=get1(gx);
val=val*((int)mp1.size())+get1(gy);
val=val*5020+(d-5020);
val+=((int)mp2.size())*((int)mp1.size())*5020;
}else{
val=get2(gx, ux);
val=val*((int)mp1.size())+get1(gy);
val=val*5020+d;
}
val+=28;
ans=get_string(val);
}
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 {
vector<string> t6{
"0001100111",
"0001011011",
"0000111011",
"0000011111",
"0000101111",
"0001110011",
"0010110011",
"0001101101",
"0000111101",
"0000110111",
"0001011101",
};
vector<string> t7{
"000011100111",
"000011011011",
"000001101111",
"000110110011",
"000011011101",
};
vector<int> st{0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4};
vector<int> add{3, 3, 2, 3, 4, 1, 2, 5, 2, 0, 3};
vector<int> g[14], gg[14];
int d[14], num[14], par[14];
map<vector<int>, int> mp1, mp2;
void clear(){
for (int i=0; i<14; ++i) g[i].clear(), gg[i].clear();
}
void build(string s, int root){
int id=0, cur=0;
auto dfs=[&](auto &&self, int u) -> void {
while (s[id]=='0'){
++id;
++cur;
gg[u].push_back(cur);
self(self, cur);
}
++id;
};
dfs(dfs, 0);
cur=0;
queue<int> q;
q.push(0);
num[0]=cur;
par[num[0]]=-1;
while (q.size()){
int u=q.front(); q.pop();
for (int v:gg[u]){
num[v]=++cur;
g[num[u]].push_back(num[v]);
g[num[v]].push_back(num[u]);
par[num[v]]=num[u];
q.push(v);
}
}
auto dfs2=[&](auto &&self, int u, int p) -> void {
for (int v:g[u]) if (v!=p){
d[v]=d[u]+1;
self(self, v, u);
}
};
d[root]=0;
dfs2(dfs2, root, 0);
}
void gen(){
for (int i=0; i<11; ++i){
for (int j=st[i]; j<5; ++j){
string t="0"+t7[j]+"10"+t6[i]+"1";
clear();
build(t, 0);
vector<int> dd(d, d+14);
if (!mp1.count(dd)) mp1[dd]=mp1.size();
}
}
// cout << mp1.size() << '\n';
set<vector<int>> tt;
for (int i=0; i<11; ++i){
for (int j=st[i]; j<5; ++j){
string t="0"+t7[j]+"10"+t6[i]+"1";
clear();
build(t, 0);
vector<int> ff(d, d+14);
sort(ff.begin(), ff.end());
for (int k=0; k<14; ++k) if ((int)g[k].size()<=2){
clear();
build(t, k);
vector<int> dd(d, d+14);
if (!mp2.count(dd)) mp2[dd]=mp2.size();
}
}
}
// cout << mp2.size() << '\n';
}
}
namespace Benjamin{
const int M=1429, SZ=14;
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 dist(int u, int v){
if (d[u]<d[v]) swap(u, v);
int ans=0;
while (d[u]>d[v]) u=par[u], ++ans;
while (u!=v) u=par[u], v=par[v], ans+=2;
return ans;
}
vector<int> find1(int id){
assert(id<(int)mp1.size());
for (auto &i:mp1) if (i.second==id) return i.first;
assert(false);
return {};
}
vector<int> find2(int id){
assert(id<(int)mp2.size());
for (auto &i:mp2) if (i.second==id) return i.first;
assert(false);
return {};
}
int get_number(string s){
int ans=0;
for (int len=1; len<(int)s.size(); ++len) ans+=1<<len;
for (int j=0; j<(int)s.size(); ++j) ans+=(s[j]-'0')<<j;
return ans;
}
int Answer(string T){
if (mp1.empty()) gen();
int gx=x/SZ, gy=y/SZ;
int ans=-1;
int val=get_number(T);
if (gx==gy){
ans=dist(x%SZ, y%SZ);
}else{
val-=28;
if (val>=((int)mp2.size())*((int)mp1.size())*5020){
val-=((int)mp2.size())*((int)mp1.size())*5020;
int d=val%5020+5020; val/=5020;
int idy=val%((int)mp1.size()); val/=(int)mp1.size();
int idx=val;
vector<int> dx=find1(idx);
vector<int> dy=find1(idy);
ans=d+dx[x%SZ]+dy[y%SZ];
}else{
int d=val%5020; val/=5020;
int idy=val%((int)mp1.size()); val/=(int)mp1.size();
int idx=val;
vector<int> dx=find2(idx);
vector<int> dy=find1(idy);
ans=d+dx[x%SZ]+dy[y%SZ];
}
}
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);
}
