#include "Ali.h"
#include <string>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
string drzewkaA[66] = {"000000111111000000111111","000000111111000001011111","000000111111000001101111","000000111111000001110111","000000111111000001111011","000000111111000010110111","000000111111000010111011","000000111111000011001111","000000111111000011011011","000000111111000011100111","000000111111000101100111","000001011111000001011111","000001011111000001101111","000001011111000001110111","000001011111000001111011","000001011111000010110111","000001011111000010111011","000001011111000011001111","000001011111000011011011","000001011111000011100111","000001011111000101100111","000001101111000001101111","000001101111000001110111","000001101111000001111011","000001101111000010110111","000001101111000010111011","000001101111000011001111","000001101111000011011011","000001101111000011100111","000001101111000101100111","000001110111000001110111","000001110111000001111011","000001110111000010110111","000001110111000010111011","000001110111000011001111","000001110111000011011011","000001110111000011100111","000001110111000101100111","000001111011000001111011","000001111011000010110111","000001111011000010111011","000001111011000011001111","000001111011000011011011","000001111011000011100111","000001111011000101100111","000010110111000010110111","000010110111000010111011","000010110111000011001111","000010110111000011011011","000010110111000011100111","000010110111000101100111","000010111011000010111011","000010111011000011001111","000010111011000011011011","000010111011000011100111","000010111011000101100111","000011001111000011001111","000011001111000011011011","000011001111000011100111","000011001111000101100111","000011011011000011011011","000011011011000011100111","000011011011000101100111","000011100111000011100111","000011100111000101100111","000101100111000101100111",};
const int B = 7;
vector<int> graf1[10010], graf2[10010];
int preorder[10010]; int preit;
int legenda[30010];
int bijekcja[10010];
int nr2;
int id[10010];
int r[10010];
bool odw[10010];
void dfs1(int x, int o){
preorder[preit++] = x;
r[x]=1;
for(auto j: graf1[x])
if(j!=o)
dfs1(j, x);
if(r[x]<B){
if(o!=-1){
r[o]+=r[x];
graf2[o].push_back(x);
graf2[x].push_back(o);
}
}
}
struct grupa{
int drzewkoid;
vector<int>numery;
vector<int>graf[14];
string napisypoddrzew[14];
int r[14];
int wolny;
int preorder[14];
int preit=0;
};
vector<grupa>grupy;
int dfsG1(int x, int o, int ile, grupa &G){
if(o==0){
if(x<(int)G.numery.size())
ile = min(ile, B-1-r[G.numery[x]]);
else
ile = min(ile, B-2);
}
//printf("%d %d\n", x, ile);
int zrobione = 0;
if(zrobione>=ile)return 0;
while(zrobione<ile && ((G.graf[x].size()<3 && o!=-1) || G.graf[x].size()<2))
{
G.graf[x].push_back(G.wolny);
G.graf[G.wolny++].push_back(x);
zrobione++;
}
if(zrobione>=ile)return zrobione;
for(auto j: G.graf[x])
if(j!=o)
zrobione+=dfsG1(j, x, ile-zrobione, G);
return zrobione;
}
bool cmp(int x, int y){
// cout<<"\""<<grupy[nr2].napisypoddrzew[x]<<"\" \""<<grupy[nr2].napisypoddrzew[y]<<"\" "<< (grupy[nr2].napisypoddrzew[x]<grupy[nr2].napisypoddrzew[y])<<"\n";
return ("0"+grupy[nr2].napisypoddrzew[x]+"1")<("0"+grupy[nr2].napisypoddrzew[y]+"1");
}
void dfsG2(int x, int o, grupa &G){
for(auto j: G.graf[x])
if(j!=o){
dfsG2(j, x, G);
}
for(int i=0;i<(int)G.graf[x].size();i++)
if(G.graf[x][i]==o){
swap(G.graf[x][i], G.graf[x].back());
G.graf[x].pop_back();
break;
}
sort(G.graf[x].begin(), G.graf[x].end(), cmp);
for(auto j: G.graf[x])
G.napisypoddrzew[x]+="0"+G.napisypoddrzew[j]+"1";
}
void dfsG3(int x, grupa &G){
//printf("%d %d\n", x, G.preit);
G.preorder[x] = G.preit++;
for(auto j: G.graf[x])
dfsG3(j, G);
}
void konfiguruj(int ng){
nr2 = ng;
auto &G = grupy[ng];
G.wolny = G.numery.size();
int i;
for(i=0;i<(int)G.numery.size();i++)
bijekcja[G.numery[i]] = i;
for(auto j: G.numery)
for(auto k: graf2[j])
G.graf[bijekcja[j]].push_back(bijekcja[k]);
int dopelnij = 2*B-1-r[G.numery[0]];
/*
printf("Grupa nr %d\n", ng);
for(i=0;i<13;i++){
printf("%d: ", i);
for(auto j: G.graf[i])
printf("%d ", j);
printf("\n");
}*/
dfsG1(0, -1, dopelnij, G);
/*
printf("Do dopelnienia %d, Po dopelnieniu Grupa nr %d\n", dopelnij, ng);
for(i=0;i<13;i++){
printf("%d: ", i);
for(auto j: G.graf[i])
printf("%d ", j);
printf("\n");
}*/
dfsG2(0, -1, G);
// jeszcze trzeba stworzyc legende
dfsG3(0, G);
/*
printf("Ostatecznie Grupa nr %d\n", ng);
for(i=0;i<13;i++){
printf("%d: ", i);
for(auto j: G.graf[i])
printf("%d ", j);
printf("\n");
}*/
// printf("Ppreorder: ");for(i=0;i<13;i++)printf("%d ", G.preorder[i]);printf("\n");
for(i=0;i<(int)G.numery.size();i++){
// printf("id[%d] = %d %d\n", G.numery[i], ng*2*B+G.preorder[i], preorder[i]);
id[G.numery[i]] = ng*2*B+G.preorder[i];
legenda[ng*2*B+G.preorder[i]] = G.numery[i];
}
// cout<<G.napisypoddrzew[0]<<"\n";
for(i=0;i<66;i++)
if(G.napisypoddrzew[0]==drzewkaA[i])break;
// printf("%d\n", i);
G.drzewkoid = i;
}
void dfs2(int x, int o){
odw[x] = 1;
grupy.back().numery.push_back(x);
for(auto j: graf2[x])
if(j!=o)
dfs2(j, x);
}
string drzewko;
void dfs3(int x, int o){
for(auto j: graf2[x])
if(j!=o){
drzewko+='0';
dfs3(j,x);
drzewko+='1';
}
}
int odleglosci[30010][3];
int najblizej[3];
int n;
void dfs4(int x, int o, int szukany, int nro){
if(o==-1)
odleglosci[x][nro] = 0;
else
odleglosci[x][nro] = odleglosci[o][nro]+1;
if(id[x]/(2*B)==szukany)
najblizej[nro] = min(najblizej[nro], odleglosci[x][nro]);
for(auto j: graf1[x])
if(j!=o)
dfs4(j, x, szukany, nro);
}
int korzen;
void Init(int N, std::vector<int> U, std::vector<int> V) {
grupy.clear();
int i;
n = N;
for(i=0;i<3*N;i++){
legenda[i] = -1;
odleglosci[i][0] = 0;
odleglosci[i][1] = 0;
odleglosci[i][2] = 0;
}
drzewko.clear();
preit = 0;
nr2 = 0;
for(i=0;i<n;i++){
graf1[i].clear();
graf2[i].clear();
odw[i] = 0;
preorder[i] = 0;
id[i] = 0;
r[i] = 0;
}
for(i=0;i<N-1;i++){
graf1[U[i]].push_back(V[i]);
graf1[V[i]].push_back(U[i]);
}
for(i=0;i<n;i++)
if(graf1[i].size()<=2)break;
korzen = i;
dfs1(korzen,-1);
for(i=0;i<N;i++)
if(!odw[preorder[i]]){
nr2 = 0;
grupy.push_back({});
dfs2(preorder[i], -1);
}
for(i=0;i<(int)grupy.size();i++)
konfiguruj(i);
for(i=0;i<N;i++)
SetID(i, id[i]);
}
std::string SendA(std::string S) {
//cout<<"otzyamalam string: "<<S<<"\n";
int liczba = 0, i;
for(i=0;i<20;i++)
if(S[i]=='1')
liczba+=(1<<i);
int u = 0, v;
int suma = 0;
for(i=1;;i++){
if(suma+i<=liczba)
suma+=i;
else
break;
}
u = i-1;
v = liczba-suma;
//u>=v
// printf("odczytalam : u = %d, v = %d\n", u, v);
if(u==v){
int pom = grupy[u].drzewkoid;
string out;
for(i=0;i<7;i++)
out+='0'+((pom>>i)&1);
return out;
}
// for(i=0;i<14*grupy.size();i++)
// printf("%d: id = %d\n", i, id[i]);
najblizej[0]=1000000;
dfs4(legenda[u*2*B], -1, v, 0);
int pv=-2137;
for(i=0;i<n;i++)
if(odleglosci[i][0]==najblizej[0] && id[i]/(2*B)==v){
pv = i;
break;
}
// printf("pv = %d\n", pv);
string out;
/*
for(i=0;i<14;i++)
out+='0'+((najblizej[0]>>i)&1);
for(i=0;i<4;i++)
out+='0'+(((id[pv]%(2*B))>>i)&1);
//dodaj drzewko v
for(i=0;i<7;i++)
out+='0'+((grupy[v].drzewkoid>>i)&1);
//dodaj drzewko u
for(i=0;i<7;i++)
out+='0'+((grupy[u].drzewkoid>>i)&1);
// cout<<najblizej[0]<<" "<<out<<"\n";
*/
//najblizej[0] od 0 do 10000 ?
//id[pv]%(2*B) od 0 do 12 ?
//grupy[v].drzewkoid od 0 do 65
//grupy[u].drzewkoid od 0 do 65
long long res = 0;
res+=najblizej[0];
res*=13;
res+=id[pv]%(2*B);
res*=66;
res+=grupy[v].drzewkoid;
res*=66;
res+=grupy[u].drzewkoid;
// printf("%d %d %d %d\n", najblizej[0], id[pv]%(2*B), grupy[v].drzewkoid, grupy[u].drzewkoid);
for(i=0;;i++){
if(res<=(1<<i)){
for(int j=0;j<i;j++)
out+='0'+((res>>j) &1);
return out;
}
res-=1<<i;
}
return out;
}
#include "Benjamin.h"
#include <string>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
string drzewkaB[66] = {"000000111111000000111111","000000111111000001011111","000000111111000001101111","000000111111000001110111","000000111111000001111011","000000111111000010110111","000000111111000010111011","000000111111000011001111","000000111111000011011011","000000111111000011100111","000000111111000101100111","000001011111000001011111","000001011111000001101111","000001011111000001110111","000001011111000001111011","000001011111000010110111","000001011111000010111011","000001011111000011001111","000001011111000011011011","000001011111000011100111","000001011111000101100111","000001101111000001101111","000001101111000001110111","000001101111000001111011","000001101111000010110111","000001101111000010111011","000001101111000011001111","000001101111000011011011","000001101111000011100111","000001101111000101100111","000001110111000001110111","000001110111000001111011","000001110111000010110111","000001110111000010111011","000001110111000011001111","000001110111000011011011","000001110111000011100111","000001110111000101100111","000001111011000001111011","000001111011000010110111","000001111011000010111011","000001111011000011001111","000001111011000011011011","000001111011000011100111","000001111011000101100111","000010110111000010110111","000010110111000010111011","000010110111000011001111","000010110111000011011011","000010110111000011100111","000010110111000101100111","000010111011000010111011","000010111011000011001111","000010111011000011011011","000010111011000011100111","000010111011000101100111","000011001111000011001111","000011001111000011011011","000011001111000011100111","000011001111000101100111","000011011011000011011011","000011011011000011100111","000011011011000101100111","000011100111000011100111","000011100111000101100111","000101100111000101100111",};
const int B = 7;
int x,y;
std::string SendB(int N, int X, int Y) {
//printf("Benjamin: X=%d Y=%d\n", X, Y);
int i;
if(X>Y)swap(X,Y);//X<Y
x = X;
y = Y;
int u, v;
v = X/(2*B);
u = Y/(2*B);
int suma=0;
for(i=0;i<=u;i++)
suma+=i;
suma+=v;
string out;
for(i=0;i<20;i++)
out+='0'+((suma>>i)&1);
//cout<<out;exit(0);
return out;
}
vector<int>graf[20];
int odl[20];
void dfs(int x, int o){
if(o>-1)
odl[x] = odl[o]+1;
for(auto j: graf[x])
if(j!=o)
dfs(j, x);
}
int Answer(std::string T) {
//cout<<T<<"\n";
int u, v, i;
for(i=0;i<20;i++){
graf[i].clear();
odl[i] = 0;
}
v = x/(2*B);
u = y/(2*B);
if(u==v){
int pom = 0;
for(i=0;i<7;i++)
if(T[0+i]=='1')
pom+=1<<i;
T = drzewkaB[pom];
stack<int>stos;
stos.push(0);
int it=1;
for(auto j:T){
if(j=='0'){//dodaj
graf[stos.top()].push_back(it);
graf[it].push_back(stos.top());
stos.push(it++);
}
else
stos.pop();
}
odl[x%(2*B)]=0;
dfs(x%(2*B), -1);
return odl[y%(2*B)];
}
int wynik = 0;
int pom=0;
long long res = 0;
for(i=0;i<(int)T.size();i++)
res+=1<<i;
for(i=0;i<(int)T.size();i++)
if(T[i]=='1')
res+=1<<i;
int ur = res%66;
res/=66;
int vr = res%66;
res/=66;
int pv = res%13;
res/=13;
int odleglosc = res;
// printf("%d %d %d %d", odleglosc, pv, vr, ur);
wynik = odleglosc;
//printf("odlegloc miedzy grupami= %d\n", pom);
//printf("pv = %d\n", pv);
stack<int>stos;
string drzewko = drzewkaB[vr];
stos.push(0);
int it=1;
for(auto j:drzewko){
if(j=='0'){//dodaj
graf[stos.top()].push_back(it);
graf[it].push_back(stos.top());
stos.push(it++);
}
else
stos.pop();
if(stos.size()==0)break;
}
odl[pv] = 0;
dfs(pv, -1);
wynik += odl[x%(2*B)];
//printf("odleglosc w v = %d\n", odl[x%(2*B)]);
drzewko= drzewkaB[ur];
while(stos.size())stos.pop();
stos.push(0);
for(i=0;i<20;i++){
graf[i].clear();
odl[i] = 0;
}
it=1;
for(auto j:drzewko){
if(j=='0'){//dodaj
graf[stos.top()].push_back(it);
graf[it].push_back(stos.top());
stos.push(it++);
}
else
stos.pop();
if(stos.size()==0)break;
}
odl[0] = 0;
dfs(0, -1);
wynik += odl[y%(2*B)];
//printf("odleglosc w u = %d, y = %d\n", odl[y%(2*B)], y%(2*B));
return wynik;
}
//10000000000000 1100 0100001 0100001
