#include "Ali.h"
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace Ali{
int n, m;
vector<vector<int>> g;
vector<int> tour, tin, tout, dep;
vector<vector<int>> st;
vector<vector<int>> f;
vector<vector<vector<int>>> tr;
void dfs(int u, int p){
tour.push_back(u);
tin[u]=(int)tour.size()-1;
f[u][1]=1;
vector<int> ff(11, 1e9), gg(11, -1);
for (int v:g[u]) if (v!=p){
dep[v]=dep[u]+1;
dfs(v, u);
tour.push_back(u);
for (int j=0; j<=10; ++j) for (int k=0; k<=10-j; ++k) if (j+k){
if (ff[j+k]>f[u][j]+f[v][k]){
ff[j+k]=f[u][j]+f[v][k];
gg[j+k]=k;
}
}
tr[u].push_back(gg);
f[u]=ff;
}
f[u][0]=*min_element(f[u].begin()+1, f[u].end());
tout[u]=(int)tour.size()-1;
}
void trace(int u, int i, int p){
if (i==0) i=min_element(f[u].begin()+1, f[u].end())-f[u].begin();
int id=tr[u].size();
for (int j=(int)g[u].size()-1; j>=0; --j) if (g[u][j]!=p){
--id;
int w=tr[u][id][i];
trace(g[u][j], w, u);
i-=w;
}
}
int dist(int u, int v){
u=tin[u], v=tin[v];
if (u>v) swap(u, v);
int lg=__lg(v-u+1);
return dep[tour[u]]+dep[tour[v]]-min(st[lg][u], st[lg][v-(1<<lg)+1])*2;
}
void init(int N, vector<int> U, vector<int> V){
n=N;
m=n*2-1;
tour.clear();
g.assign(n, {});
tr.assign(n, {});
f.assign(n, vector<int>(11, 1e9));
for (int i=0; i<n-1; ++i) g[U[i]].push_back(V[i]), g[V[i]].push_back(U[i]);
tin.resize(n, 0); tout.resize(n, 0); dep.resize(n, 0);
dfs(0, -1);
assert(f[0][0]<=1024);
int lg=__lg(m*2-1);
st.assign(lg, vector<int>(m));
for (int i=0; i<m; ++i) st[0][i]=dep[tour[i]];
for (int i=1; i<lg; ++i){
for (int j=0; j+(1<<i)-1<m; ++j) st[i][j]=min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
}
for (int i=0; i<n; ++i) SetID(i, tin[i]);
}
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 SendA(string S){
int sum=m*(m+1)/2;
int size=(sum+(1<<20)-1)/(1<<20);
int id=0;
for (int i=0; i<20; ++i) id|=(S[i]-'0')<<i;
string ans;
pair<int, int> tl=get(id*size);
pair<int, int> tr=get(min(sum-1, (id+1)*size-1));
for (int i=tr.first; i>tl.first; --i){
int r=i==tr.first?tr.second:m-1;
int d=0;
for (int j=i; j<=r; ++j){
if (j!=r){
int nd=dist(tour[i], tour[j+1]);
ans.push_back('0'+(d<nd));
d=nd;
}
}
}
int r=tl.first==tr.first?tr.second:m-1;
int lg=__lg(n*2-1);
int d=dist(tour[tl.first], tour[tl.second]);
for (int i=0; i<lg; ++i) ans.push_back('0'+(d>>i&1));
for (int j=tl.second; j<=r; ++j){
if (j!=r){
int nd=dist(tour[tl.first], tour[j+1]);
ans.push_back('0'+(d<nd));
d=nd;
}
}
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{
int n, x, y, m;
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);
m=n*2-1;
int sum=m*(m+1)/2;
int size=(sum+(1<<20)-1)/(1<<20);
int id=get({x, y})/size;
string ans;
for (int i=0; i<20; ++i) ans.push_back('0'+(id>>i&1));
return ans;
}
int Answer(string T){
int sum=m*(m+1)/2;
int size=(sum+(1<<20)-1)/(1<<20);
int id=get({x, y})/size;
pair<int, int> tl=get(id*size);
pair<int, int> tr=get(min(sum-1, (id+1)*size-1));
int id_ans=0;
for (int i=tr.first; i>tl.first; --i){
int r=i==tr.first?tr.second:m-1;
int d=0;
for (int j=i; j<=r; ++j){
if (x==i && y==j) return d;
if (j!=r){
int nd=d+(T[id_ans++]-'0'?1:-1);
d=nd;
}
}
}
int r=tl.first==tr.first?tr.second:m-1;
int lg=__lg(n*2-1);
int d=0;
for (int i=0; i<lg; ++i) d|=(T[id_ans++]-'0')<<i;
for (int j=tl.second; j<=r; ++j){
if (x==tl.first && y==j) return d;
if (j!=r){
int nd=d+(T[id_ans++]-'0'?1:-1);
d=nd;
}
}
return -1;
}
}
std::string SendB(int N, int X, int Y) {
return Benjamin::SendB(N, X, Y);
}
int Answer(std::string T) {
return Benjamin::Answer(T);
}
