#include "Ali.h"
#include <bits/stdc++.h>
namespace {
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
bool done_precalc = false;
std::vector<std::pair<std::string, std::vector<std::vector<int>>>> all_trees;
void PreCalc() {
auto normalize = [&](std::string s) -> std::pair<bool, std::vector<std::vector<int>>> {
int n = std::count(s.begin(), s.end(), '1') + 1;
if (2 * n - 2 != s.size()) {
return {false, {}};
}
bool good = true;
std::vector<std::vector<int>> adj(n);
int cnt = 1;
std::vector<int> stk {0};
for (int i = 0; i < 2 * n - 2; ++i) {
if (s[i] == '1') {
if (stk.empty()) {
return {false, {}};
}
adj[stk.back()].emplace_back(cnt);
stk.emplace_back(cnt);
cnt += 1;
} else {
if (stk.empty()) {
return {false, {}};
}
stk.pop_back();
}
}
if (stk.size() != 1) {
return {false, {}};
}
std::vector<int> siz(n, 1);
std::vector<std::string> bit(n);
bool bad = false;
auto dfs = [&](auto&& self, int v) -> void {
for (auto u : adj[v]) {
self(self, u);
siz[v] += siz[u];
}
if (adj[v].size() >= 3) {
bad = true;
}
if (adj[v].size() == 2) {
int a = adj[v][0];
int b = adj[v][1];
if (bit[a] > bit[b]) {
bad = true;
}
}
for (auto u : adj[v]) {
bit[v] += "1";
bit[v] += bit[u];
bit[v] += "0";
}
if (v != 0 && siz[v] >= 7) {
bad = true;
return;
}
};
dfs(dfs, 0);
if (bad || bit[0] != s) {
return {false, {}};
}
return {true, adj};
};
for (int n = 1; n <= 13; ++n) {
for (int m = 0; m < (1 << 2 * n - 2); ++m) {
std::string s = "";
for (int i = 0; i < 2 * n - 2; ++i) {
if (m >> i & 1) {
s += '1';
} else {
s += '0';
}
}
auto[good, adj] = normalize(s);
if (good) {
all_trees.emplace_back(s, adj);
}
}
}
done_precalc = true;
debug(all_trees.size());
}
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]) {
res += "1";
self(self, u);
res += "0";
}
};
local_dfs(local_dfs, top[id]);
return res;
}
std::vector<std::string> bit;
void reorder(int id) {
std::vector<int> vrts = gs[id];
int n = int(vrts.size());
auto local_dfs = [&](auto&& self, int v) -> void {
std::vector<int> chs;
for (auto u : adj[v]) {
if (std::find(vrts.begin(), vrts.end(), u) == vrts.end()) {
continue;
}
chs.emplace_back(u);
self(self, u);
}
adj[v] = std::move(chs);
if (adj[v].size() >= 2) {
int& a = adj[v][0];
int& b = adj[v][1];
if (bit[a] > bit[b]) {
std::swap(a, b);
}
bit[v] = "1" + bit[a] + "01" + bit[b] + "0";
} else if (adj[v].size() == 1) {
int a = adj[v][0];
bit[v] = "1" + bit[a] + "0";
}
};
local_dfs(local_dfs, top[id]);
std::vector<int> stk;
auto reorder_dfs = [&](auto&& self, int v) -> void {
stk.emplace_back(v);
for (auto u : adj[v]) {
self(self, u);
}
};
reorder_dfs(reorder_dfs, top[id]);
gs[id] = std::move(stk);
}
}
void Init(int N, std::vector<int> U, std::vector<int> V) {
if (!done_precalc) {
PreCalc();
}
::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);
bit.assign(N, "");
for (int i = 0; i < n; ++i) {
reorder(ordgs[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]);
int ids1 = -1, ids2 = -1;
for (int i = 0; i < int(all_trees.size()); ++i) {
if (s1 == all_trees[i].first) {
ids1 = i;
}
if (s2 == all_trees[i].first) {
ids2 = i;
}
}
assert(ids1 != -1 && ids2 != -1);
debug(s1, ids1);
debug(s2, ids2);
auto[d, u] = dist(top[ordgs[gl]], top[ordgs[gr]]);
debug(d, u);
std::string res = fix(ids1, 9) + fix(ids2, 9) + 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
bool done_precalc = false;
std::vector<std::pair<std::string, std::vector<std::vector<int>>>> all_trees;
void PreCalc() {
auto normalize = [&](std::string s) -> std::pair<bool, std::vector<std::vector<int>>> {
int n = std::count(s.begin(), s.end(), '1') + 1;
if (2 * n - 2 != s.size()) {
return {false, {}};
}
bool good = true;
std::vector<std::vector<int>> adj(n);
int cnt = 1;
std::vector<int> stk {0};
for (int i = 0; i < 2 * n - 2; ++i) {
if (s[i] == '1') {
if (stk.empty()) {
return {false, {}};
}
adj[stk.back()].emplace_back(cnt);
stk.emplace_back(cnt);
cnt += 1;
} else {
if (stk.empty()) {
return {false, {}};
}
stk.pop_back();
}
}
if (stk.size() != 1) {
return {false, {}};
}
std::vector<int> siz(n, 1);
std::vector<std::string> bit(n);
bool bad = false;
auto dfs = [&](auto&& self, int v) -> void {
for (auto u : adj[v]) {
self(self, u);
siz[v] += siz[u];
}
if (adj[v].size() >= 3) {
bad = true;
}
if (adj[v].size() == 2) {
int a = adj[v][0];
int b = adj[v][1];
if (bit[a] > bit[b]) {
bad = true;
}
}
for (auto u : adj[v]) {
bit[v] += "1";
bit[v] += bit[u];
bit[v] += "0";
}
if (v != 0 && siz[v] >= 7) {
bad = true;
return;
}
};
dfs(dfs, 0);
if (bad || bit[0] != s) {
return {false, {}};
}
return {true, adj};
};
for (int n = 1; n <= 13; ++n) {
for (int m = 0; m < (1 << 2 * n - 2); ++m) {
std::string s = "";
for (int i = 0; i < 2 * n - 2; ++i) {
if (m >> i & 1) {
s += '1';
} else {
s += '0';
}
}
auto[good, adj] = normalize(s);
if (good) {
all_trees.emplace_back(s, adj);
}
}
}
done_precalc = true;
debug(all_trees.size());
}
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 (!done_precalc) {
PreCalc();
}
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 {
int ids1 = to_int(T.substr(0, 9));
int ids2 = to_int(T.substr(9, 9));
int d = to_int(T.substr(18, 14));
int u = to_int(T.substr(32, 4));
std::vector<std::vector<int>> g1 = all_trees[ids1].second;
std::vector<std::vector<int>> g2 = all_trees[ids2].second;
debug(g1);
debug(g2);
debug(d, u);
return d + answer_different_group(g1, g2, u, a, b);
}
return 1;
}
