#include "Ali.h"
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace Ali{
int n;
vector<vector<int>> g;
vector<int> tour, tin, tout, dep;
vector<vector<int>> st;
void dfs(int u, int p){
tour.push_back(u);
tin[u]=(int)tour.size()-1;
for (int v:g[u]) if (v!=p) dep[v]=dep[u]+1, dfs(v, u), tour.push_back(u);
tout[u]=(int)tour.size()-1;
}
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[u]+dep[v]-min(st[lg][u], st[lg][v-(1<<lg)+1])*2;
}
void init(int N, vector<int> U, vector<int> V){
n=N;
g.clear(), tour.clear(), tin.clear(), tout.clear(), dep.clear(), st.clear();
g.resize(n);
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); tout.resize(n); dep.resize(n);
dfs(0, -1);
int lg=__lg((n*2-1)*2-1);
st.assign(lg, vector<int>(n*2-1));
for (int i=0; i<n*2-1; ++i) st[0][i]=dep[tour[i]];
for (int i=1; i<lg; ++i){
for (int j=0; j+(1<<i)-1<n*2-1; ++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]);
}
string SendA(string S){
int lg=__lg(n*2-1);
int x=0;
for (int i=0; i<lg; ++i) x|=(S[i]-'0')<<i;
int rem=20-lg;
int size=(n*2-1+(1<<rem)-1)>>rem;
int id=0;
for (int i=0; i<rem; ++i) id|=(S[i+lg]-'0')<<i;
string ans;
int d=dist(x, tour[id*size]);
for (int i=0; i<lg; ++i) ans.push_back('0'+(d>>i&1));
for (int i=id*size+1; i<(id+1)*size && i<n*2-1; ++i){
int nd=dist(x, tour[i]);
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;
string SendB(int N, int X, int Y){
n=N, x=X, y=Y;
if (x>y) swap(x, y);
int lg=__lg(n*2-1);
string ans;
for (int i=0; i<lg; ++i) ans.push_back('0'+(x>>i&1));
int rem=20-lg;
int size=(n*2-1+(1<<rem)-1)>>rem;
int id=y/size;
for (int i=0; i<rem; ++i) ans.push_back('0'+(id>>i&1));
return ans;
}
int Answer(string T){
int lg=__lg(n*2-1);
int rem=20-lg;
int size=(n*2-1+(1<<rem)-1)>>rem;
int id=y/size;
int idy=y-(id*size);
int d=0;
for (int i=0; i<lg; ++i) d|=(T[i]-'0')<<i;
for (int i=0; i+lg<=(int)T.size(); ++i){
if (idy==i) return d;
int nd=d+(T[i+lg]=='1'?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);
}
