#include "Ali.h"
#include <bits/stdc++.h>
namespace {
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
std::vector<std::vector<int>> all_good_ms = {
{},
{0},
{1},
{3, 5},
{7, 11, 13},
{15, 23, 27, 29, 45, 51},
{31, 47, 55, 59, 61, 91, 93, 103, 109, 115, 179},
{63, 95, 111, 119, 123, 125, 183, 187, 189, 207, 219, 221, 231, 237, 243, 359, 365, 371, 413, 435, 455, 459, 715},
{253, 381, 445, 477, 493, 499, 733, 749, 755, 829, 877, 883, 925, 947, 967, 971, 1437, 1459, 1479, 1483, 1651, 1739, 1819},
{1011, 1523, 1779, 1907, 1971, 1991, 1995, 2931, 2995, 3015, 3019, 3315, 3507, 3527, 3531, 3699, 3787, 3855, 3863, 3867, 5747, 5835, 5911, 5915, 6599, 6603, 6939, 7227, 7259},
{4039, 4043, 6087, 6091, 7111, 7115, 7623, 7627, 7883, 7951, 7959, 7963, 11719, 11723, 11979, 12047, 12055, 12059, 13255, 13259, 14027, 14103, 14107, 14791, 14795, 15131, 15415, 15419, 15451, 15463, 22983, 22987, 23323, 23611, 23643, 23655, 26395, 28795, 28859, 28891},
{16143, 16151, 16155, 24335, 24343, 24347, 28431, 28439, 28443, 30487, 30491, 31515, 31775, 31791, 31799, 31803, 31835, 31847, 46871, 46875, 47899, 48175, 48183, 48187, 48219, 48231, 53007, 53015, 53019, 56091, 56375, 56379, 56411, 56423, 59163, 60475, 60507, 61559, 61563, 61623, 61627, 61659, 61671, 61799, 91931, 93275, 94331, 94395, 94427, 94439, 94567, 105531, 105563, 105575},
{64543, 64559, 64567, 64571, 64603, 64615, 97311, 97327, 97335, 97339, 97371, 97383, 113711, 113719, 113723, 113755, 113767, 121911, 121915, 121947, 121959, 126011, 126043, 127087, 127095, 127099, 127159, 127163, 127183, 127195, 127207, 127335, 187447, 187451, 187483, 187495, 191547, 191579, 192631, 192635, 192695, 192699, 192719, 192731, 192743, 192871, 212023, 212027, 212059, 212071, 224347, 225403, 225467, 225499, 225511, 225639, 236603, 236635, 236647, 241883, 367675, 367707, 367719, 422011, 422075, 422107},
{258111, 258143, 258159, 258167, 258171, 258231, 258235, 258255, 258267, 258279, 258407, 389215, 389231, 389239, 389243, 389303, 389307, 389327, 389339, 389351, 389479, 454767, 454775, 454779, 454839, 454843, 454863, 454875, 454887, 455015, 487543, 487547, 487607, 487611, 487643, 487655, 487783, 503931, 503995, 504027, 749691, 749751, 749755, 749787, 749799, 749927, 766139, 766171, 847991, 847995, 848055, 848059, 848079, 848091, 848103, 848231, 897243, 946299, 946363, 946395, 946407, 946535, 1470587, 1470651, 1470683, 1470823},
};
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) {
// std::cerr << "{";
for (auto m : all_good_ms[n]) {
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) {
// std::cerr << m << ", ";
all_trees.emplace_back(s, adj);
}
}
// std::cerr << "}\n";
}
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
std::vector<std::vector<int>> all_good_ms = {
{},
{0},
{1},
{3, 5},
{7, 11, 13},
{15, 23, 27, 29, 45, 51},
{31, 47, 55, 59, 61, 91, 93, 103, 109, 115, 179},
{63, 95, 111, 119, 123, 125, 183, 187, 189, 207, 219, 221, 231, 237, 243, 359, 365, 371, 413, 435, 455, 459, 715},
{253, 381, 445, 477, 493, 499, 733, 749, 755, 829, 877, 883, 925, 947, 967, 971, 1437, 1459, 1479, 1483, 1651, 1739, 1819},
{1011, 1523, 1779, 1907, 1971, 1991, 1995, 2931, 2995, 3015, 3019, 3315, 3507, 3527, 3531, 3699, 3787, 3855, 3863, 3867, 5747, 5835, 5911, 5915, 6599, 6603, 6939, 7227, 7259},
{4039, 4043, 6087, 6091, 7111, 7115, 7623, 7627, 7883, 7951, 7959, 7963, 11719, 11723, 11979, 12047, 12055, 12059, 13255, 13259, 14027, 14103, 14107, 14791, 14795, 15131, 15415, 15419, 15451, 15463, 22983, 22987, 23323, 23611, 23643, 23655, 26395, 28795, 28859, 28891},
{16143, 16151, 16155, 24335, 24343, 24347, 28431, 28439, 28443, 30487, 30491, 31515, 31775, 31791, 31799, 31803, 31835, 31847, 46871, 46875, 47899, 48175, 48183, 48187, 48219, 48231, 53007, 53015, 53019, 56091, 56375, 56379, 56411, 56423, 59163, 60475, 60507, 61559, 61563, 61623, 61627, 61659, 61671, 61799, 91931, 93275, 94331, 94395, 94427, 94439, 94567, 105531, 105563, 105575},
{64543, 64559, 64567, 64571, 64603, 64615, 97311, 97327, 97335, 97339, 97371, 97383, 113711, 113719, 113723, 113755, 113767, 121911, 121915, 121947, 121959, 126011, 126043, 127087, 127095, 127099, 127159, 127163, 127183, 127195, 127207, 127335, 187447, 187451, 187483, 187495, 191547, 191579, 192631, 192635, 192695, 192699, 192719, 192731, 192743, 192871, 212023, 212027, 212059, 212071, 224347, 225403, 225467, 225499, 225511, 225639, 236603, 236635, 236647, 241883, 367675, 367707, 367719, 422011, 422075, 422107},
{258111, 258143, 258159, 258167, 258171, 258231, 258235, 258255, 258267, 258279, 258407, 389215, 389231, 389239, 389243, 389303, 389307, 389327, 389339, 389351, 389479, 454767, 454775, 454779, 454839, 454843, 454863, 454875, 454887, 455015, 487543, 487547, 487607, 487611, 487643, 487655, 487783, 503931, 503995, 504027, 749691, 749751, 749755, 749787, 749799, 749927, 766139, 766171, 847991, 847995, 848055, 848059, 848079, 848091, 848103, 848231, 897243, 946299, 946363, 946395, 946407, 946535, 1470587, 1470651, 1470683, 1470823},
};
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) {
// std::cerr << "{";
for (auto m : all_good_ms[n]) {
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) {
// std::cerr << m << ", ";
all_trees.emplace_back(s, adj);
}
}
// std::cerr << "}\n";
}
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;
}
