//Challenge: Accepted
#include "Ali.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 10005
#define pii pair<int, int>
#define ff first
#define ss second
const int bs = 10;
vector<int> adj[maxn];
int bid[maxn], bord[maxn], siz[maxn], par[maxn], dep[maxn], id[maxn];
bool isroot[maxn];
int root[maxn];
string trav[maxn];
int C = 0;
int st;
void dfs(int n, int pa, int d) {
par[n] = pa;
dep[n] = d;
siz[n] = 1;
debug(n);
for (int v:adj[n]) {
if (v != pa) {
dfs(v, n, d+1);
if (siz[v] < bs) {
siz[n] += siz[v];
}
}
}
if (siz[n] >= bs || n == st) {
debug("root", n, siz[n]);
isroot[n] = 1;
bid[n] = C;
root[C++] = n;
}
}
void getb(int n, int pa, int &ti) {
bord[n] = ti++;
for (int v:adj[n]) {
if (v != pa && !isroot[v]) {
trav[bid[n]] += '1';
bid[v] = bid[n];
getb(v, n, ti);
trav[bid[n]] += '0';
}
}
}
}
void Init(int N, std::vector<int> U, std::vector<int> V) {
for (int i = 0;i < N;i++) {
adj[i].clear();
trav[i].clear();
bid[i] = 0, bord[i] = 0;
siz[i] = 0;
isroot[i] = 0, root[i] = 0;
}
C = 0;
for (int i = 0;i < N - 1;i++) {
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
for (int i = 0;i < N;i++) {
if (adj[i].size() == 1) {
st = i;
dfs(st, -1, 0);
break;
}
}
for (int i = 0;i < N;i++) {
if (isroot[i]) {
int tmp = 0;
getb(i, par[i], tmp);
}
}
for (int i = 0;i < C;i++) {
while (trav[i].size() < 36) trav[i] += '0';
}
for (int i = 0;i < N;i++) {
id[i] = bid[i] * 2 * bs + bord[i];
//debug(bid[i], bord[i]);
SetID(i, id[i]);
}
}
std::string SendA(std::string S) {
int bx = 0, by = 0;
for (int i = 0;i < 10;i++) bx += (S[i] - '0') * (1<<i);
for (int i = 10;i < 20;i++) by += (S[i] - '0') * (1<<(i-10));
debug("senda", bx, by);
int dis = 0;
int px = root[bx], py = root[by], v = 0;
while (px != py) {
if (dep[px] < dep[py]) swap(px, py);
px = par[px];
dis++;
if (bid[px] == bid[py] && bid[px] == bx) {
v = bord[px];
break;
}
}
debug(dis);
string ret;
for (int i = 0;i < 14;i++) ret += char(((dis >> i) & 1) + '0');
ret.insert(ret.end(), trav[bx].begin(), trav[bx].end());
ret.insert(ret.end(), trav[by].begin(), trav[by].end());
for (int i = 0;i < 5;i++) ret += char(((v >> i) & 1) + '0');
debug(ret);
return ret;
}
//Challenge: Accepted
#include "Benjamin.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 10005
#define pii pair<int, int>
#define ff first
#define ss second
namespace {
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
const int bs = 10;
int bx, by, dx, dy;
int par[maxn], dep[maxn];
void decode(string s) {
int d = 0, cur = 0, id = 0;
dep[cur] = 0;
for (auto i:s) {
d += (i == '1' ? 1 : -1);
if (i - '0') {
dep[++id] = d;
par[id] = cur;
cur = id;
} else {
if (d < 0) return;
cur = par[cur];
}
}
}
}
std::string SendB(int N, int X, int Y) {
bx = X / (2 * bs), by = Y / (2 * bs);
dx = X % (2 * bs), dy = Y % (2 * bs);
if (bx < by) swap(bx, by), swap(dx, dy);
string ret;
for (int i = 0;i < 10;i++) ret += char(((bx >> i) & 1) + '0');
for (int i = 0;i < 10;i++) ret += char(((by >> i) & 1) + '0');
debug(bx, dx, by, dy);
return ret;
}
int Answer(std::string T) {
int ret = 0;
for (int i = 0;i < 14;i++) {
ret += (1<<i) * (T[i] - '0');
}
if (bx != by) {
decode(T.substr(14, 36));
int v = 0;
for (int i = 0;i < 5;i++) v += (1<<i) * (T[86 + i] - '0');
if (v) {
while (dx != v) {
if (dep[dx] < dep[v]) swap(dx, v);
dx = par[dx];
ret++;
}
} else {
ret += dep[dx];
}
decode(T.substr(50, 36));
ret += dep[dy];
} else {
decode(T.substr(14, 36));
while (dx != dy) {
if (dep[dx] < dep[dy]) swap(dx, dy);
dx = par[dx];
ret++;
}
}
return ret;
}
