#include "Ali.h"
#include <bits/stdc++.h>
namespace {
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
int N;
std::vector<int> U;
std::vector<int> V;
int to_int(std::string s) {
int x = 0;
for (int i = 0; i < int(s.size()); ++i) {
x = x * 2 + int(s[i] - '0');
}
return x;
}
std::string fix(std::string s, int n) {
assert(s.size() <= n);
while (s.size() != n) {
s = '0' + s;
}
return s;
}
std::string fix(int x, int n) {
std::string s = "";
while (x) {
s = char('0' + x % 2) + s;
x /= 2;
}
return fix(s, n);
}
std::vector<std::vector<int>> adj;
int root;
std::vector<std::vector<int>> take;
std::vector<int> par;
std::vector<int> dep;
std::vector<std::vector<int>> gs;
std::vector<int> top;
std::vector<int> ordgs;
std::vector<int> idsv;
std::vector<int> idsg;
void dfs(int v) {
take[v].emplace_back(v);
for (auto u : adj[v]) {
par[u] = v;
dep[u] = dep[v] + 1;
adj[u].erase(std::find(adj[u].begin(), adj[u].end(), v));
dfs(u);
take[v].insert(take[v].end(), take[u].begin(), take[u].end());
}
if (int(take[v].size()) >= 7 || v == root) {
gs.emplace_back(take[v]);
top.emplace_back(v);
take[v].clear();
}
}
std::pair<int, int> decode_groups(int bt) {
int x = 0;
while (true) {
if (bt <= x) {
return {bt, x};
}
bt -= x + 1;
x += 1;
}
assert(false);
return {-1, -1};
}
std::pair<int, int> dist(int a, int b) {
debug(a, b);
int d = 0;
int u = a;
int v = b;
while (u != v) {
if (u == a && idsv[u] / 13 == idsv[v] / 13) {
break;
}
debug(u, v);
if (dep[v] < dep[u]) {
d += 1;
u = par[u];
} else {
d += 1;
v = par[v];
}
debug(u, v);
}
if (u == a) {
return {d, idsv[v] % 13};
} else {
return {d, 0};
}
}
std::string encode_euler(int id) {
debug(id, gs[id]);
std::string res = "";
auto local_dfs = [&](auto&& self, int v) -> void {
debug(v);
for (auto u : adj[v]) {
if (idsv[u] / 13 != idsv[top[id]] / 13) {
continue;
}
res += "1";
self(self, u);
res += "0";
}
};
local_dfs(local_dfs, top[id]);
return res;
}
}
void Init(int N, std::vector<int> U, std::vector<int> V) {
::N = N;
::U = U;
::V = V;
adj.assign(N, {});
take.assign(N, {});
gs.assign(0, {});
top.assign(0, 0);
dep.assign(N, 0);
par.assign(N, -1);
for (int i = 0; i < N - 1; ++i) {
adj[U[i]].emplace_back(V[i]);
adj[V[i]].emplace_back(U[i]);
}
root = 0;
while (adj[root].size() == 3) {
root += 1;
}
dep[root] = 0;
par[root] = root;
dfs(root);
int n = int(gs.size());
ordgs.assign(n, 0);
idsg.assign(n, -1);
idsv.assign(N, -1);
std::iota(ordgs.begin(), ordgs.end(), 0);
std::sort(ordgs.begin(), ordgs.end(), [&](auto lhs, auto rhs) {
return dep[top[lhs]] < dep[top[rhs]];
});
debug(gs);
for (int i = 0; i < n; ++i) {
idsg[ordgs[i]] = i;
for (int j = 0; j < int(gs[ordgs[i]].size()); ++j) {
int v = gs[ordgs[i]][j];
idsv[v] = 13 * i + j;
SetID(v, idsv[v]);
}
}
debug(idsv);
}
std::string SendA(std::string S) {
int bt = to_int(S);
auto[gl, gr] = decode_groups(bt);
debug(gl, gr);
if (gl == gr) {
std::string s1 = encode_euler(ordgs[gl]);
std::string res = fix(s1, 24);
return res;
} else {
std::string s1 = encode_euler(ordgs[gl]);
std::string s2 = encode_euler(ordgs[gr]);
debug(s1);
debug(s2);
auto[d, u] = dist(top[ordgs[gl]], top[ordgs[gr]]);
debug(d, u);
std::string res = fix(s1, 24) + fix(s2, 24) + fix(d, 14) + fix(u, 4);
return res;
}
}
#include "Benjamin.h"
#include <bits/stdc++.h>
namespace {
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
int N;
int X;
int Y;
int to_int(std::string s) {
int x = 0;
for (int i = 0; i < int(s.size()); ++i) {
x = x * 2 + int(s[i] - '0');
}
return x;
}
std::string fix(std::string s, int n) {
assert(s.size() <= n);
while (s.size() != n) {
s = '0' + s;
}
return s;
}
std::string fix(int x, int n) {
std::string s = "";
while (x) {
s = char('0' + x % 2) + s;
x /= 2;
}
return fix(s, n);
}
int encode_groups(int a, int b) {
int res = 0;
for (int i = 0; i < b; ++i) {
res += i + 1;
}
res += a;
return res;
}
std::vector<std::vector<int>> decode_euler(std::string s) {
int n = std::count(s.begin(), s.end(), '1');
while (s.size() > 2 * n) {
s = s.substr(1);
}
std::vector<std::vector<int>> adj(n + 1);
int cnt = 1;
std::vector<int> stk {0};
for (int i = 0; i < 2 * n; ++i) {
if (s[i] == '1') {
adj[stk.back()].emplace_back(cnt);
stk.emplace_back(cnt);
cnt += 1;
} else {
stk.pop_back();
}
}
return adj;
}
int answer_same_group(std::vector<std::vector<int>> g, int a, int b) {
debug(g, a, b);
int n = int(g.size());
std::vector<int> par(n, -1);
std::vector<int> dep(n, -1);
auto local_dfs = [&](auto&& self, int v) -> void {
for (auto u : g[v]) {
par[u] = v;
dep[u] = dep[v] + 1;
self(self, u);
}
};
dep[0] = 0;
local_dfs(local_dfs, 0);
debug(dep);
debug(par);
int res = 0;
while (a != b) {
debug(a, b);
if (dep[a] > dep[b]) {
res += 1;
a = par[a];
} else {
res += 1;
b = par[b];
}
debug(a, b);
}
return res;
}
int answer_different_group(std::vector<std::vector<int>> g1, std::vector<std::vector<int>> g2, int u, int a, int b) {
return answer_same_group(g1, a, u) + answer_same_group(g2, b, 0);
}
}
std::string SendB(int N, int X, int Y) {
if (X / 13 > Y / 13) {
std::swap(X, Y);
}
::N = N;
::X = X;
::Y = Y;
int id = encode_groups(X / 13, Y / 13);
return fix(id, 20);
}
int Answer(std::string T) {
int a = X % 13;
int b = Y % 13;
if (X / 13 == Y / 13) {
std::vector<std::vector<int>> g = decode_euler(T);
return answer_same_group(g, a, b);
} else {
std::string s1 = T.substr(0, 24);
std::string s2 = T.substr(24, 24);
int d = to_int(T.substr(48, 14));
int u = to_int(T.substr(62, 4));
std::vector<std::vector<int>> g1 = decode_euler(s1);
std::vector<std::vector<int>> g2 = decode_euler(s2);
debug(g1);
debug(g2);
debug(d, u);
return d + answer_different_group(g1, g2, u, a, b);
}
return 1;
}
