/* https://www2.ioi-jp.org/camp/2022/2022-sp-tasks/contest2/flights-review.pdf */
#include "Ali.h"
#include <cstring>
#include <string>
#include <vector>
using namespace std;
typedef vector<int> vi;
namespace Ali {
const int N = 10000, B = 7, K = B * 2 - 1, M = (N + B - 1) / B;
const int L = 20;
const int LN = 14; /* LN = ceil(log2(N)) */
const int LK = 4; /* LK = ceil(log2(K)) */
const int LT = 9; /* LT = ceil(log2(dp[B] + ... + dp[K])) */
int min(int a, int b) { return a < b ? a : b; }
int dp[K + 1];
void init() {
memset(dp, 0, (K + 1) * sizeof *dp), dp[0] = 1;
for (int s1 = 0; s1 < B; s1++) {
for (int s2 = 0; s2 < s1; s2++)
dp[s1 + s2 + 1] += dp[s1] * dp[s2];
dp[s1 + s1 + 1] += dp[s1] * (dp[s1] + 1) / 2;
}
}
string encode(int n, int x) {
string cc(n, '?');
for (int i = 0; i < n; i++)
cc[i] = (x >> i & 1) + '0';
return cc;
}
int decode(string cc) {
int n = cc.size(), x = 0;
for (int i = 0; i < n; i++)
if (cc[i] == '1')
x |= 1 << i;
return x;
}
int encode_pair(int i, int j) {
return j * (j + 1) / 2 + i;
}
void decode_pair(int x, int &i, int &j) {
j = 0;
while (x >= j + 1)
x -= ++j;
i = x;
}
int encode_tree(int n, int x) {
while (--n)
x += dp[n];
return x;
}
int ej[N][3], eo[N], n;
void append(int i, int j) {
ej[i][eo[i]++] = j;
}
void detach(int i, int j) {
for (int o = eo[i]; o--; )
if (ej[i][o] == j) {
ej[i][o] = ej[i][--eo[i]];
return;
}
}
int dd[N], pp[N], sz[N], xx[N], hh[N], gg[N];
int ii[M], iii[M][K], kk[M], m;
int dfs1(int p, int i, int d) {
pp[i] = p, dd[i] = d;
detach(i, p);
int s = 1;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
s += dfs1(i, j, d + 1);
}
if (s >= B || p == -1) {
ii[m++] = i, s = 0;
if (p != -1)
detach(p, i);
}
return s;
}
void dfs2(int i) {
sz[i] = 1;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
dfs2(j);
sz[i] += sz[j];
}
if (eo[i] == 0)
xx[i] = 0;
else if (eo[i] == 1)
xx[i] = xx[ej[i][0]];
else {
int &j1 = ej[i][0], &j2 = ej[i][1];
if (sz[j1] < sz[j2] || sz[j1] == sz[j2] && xx[j1] > xx[j2]) {
int tmp;
tmp = j1, j1 = j2, j2 = tmp;
}
xx[i] = 0;
for (int n1 = min(sz[i] - 1, B - 1), n2 = sz[i] - 1 - n1; n1 > sz[j1]; n1--, n2++)
xx[i] += dp[n1] * dp[n2];
xx[i] += sz[j1] != sz[j2] ? xx[j1] * dp[sz[j2]] + xx[j2] : encode_pair(xx[j1], xx[j2]);
}
}
void dfs3(int i, int h) {
hh[i] = h, iii[h][gg[i] = kk[h]++] = i;
for (int o = 0; o < eo[i]; o++) {
int j = ej[i][o];
dfs3(j, h);
}
}
void init(vi uu, vi vv, int n_) {
init();
n = n_;
memset(eo, 0, n * sizeof *eo);
for (int h = 0; h < n - 1; h++)
append(uu[h], vv[h]), append(vv[h], uu[h]);
int i = 0;
while (eo[i] > 2)
i++;
m = 0, dfs1(-1, i, 0);
int tmp;
for (int h1 = 0, h2 = m - 1; h1 < h2; h1++, h2--)
tmp = ii[h1], ii[h1] = ii[h2], ii[h2] = tmp;
for (int h = m - 1; h >= 0; h--) {
i = ii[h];
dfs2(i);
kk[h] = 0, dfs3(i, h);
}
for (i = 0; i < n; i++)
SetID(i, hh[i] * K + gg[i]);
}
int lca(int i, int j) {
while (i != j)
if (dd[i] > dd[j])
i = pp[i];
else
j = pp[j];
return i;
}
int dist(int i, int j) {
return dd[i] + dd[j] - dd[lca(i, j)] * 2;
}
string send(string cc) {
int hu, hv; decode_pair(decode(cc), hu, hv);
int u = iii[hu][0], v = iii[hv][0], u_, v_;
if (hu == hv)
return encode(LT, encode_tree(sz[u], xx[u]));
if (dist(u, v) != dd[v] - dd[u])
u_ = u, v_ = v;
else {
u_ = v, v_ = v;
while (hh[u_] != hh[u])
u_ = pp[u_];
}
return encode(LT, encode_tree(sz[u], xx[u])) + encode(LT, encode_tree(sz[v], xx[v]))
+ encode(LK, gg[u_]) + encode(LK, gg[v_])
+ encode(LN, dist(u_, v_));
}
}
void Init(int n, vi ii, vi jj) {
Ali::init(ii, jj, n);
}
string SendA(string cc) {
return Ali::send(cc);
}
/* https://www2.ioi-jp.org/camp/2022/2022-sp-tasks/contest2/flights-review.pdf */
#include "Benjamin.h"
#include <cstring>
#include <string>
#include <vector>
using namespace std;
typedef vector<int> vi;
namespace Benjamin {
const int N = 10000, B = 7, K = B * 2 - 1, M = (N + B - 1) / B;
const int L = 20;
const int LN = 14; /* LN = ceil(log2(N)) */
const int LK = 4; /* LK = ceil(log2(K)) */
const int LT = 9; /* LT = ceil(log2(dp[B] + ... + dp[K])) */
int min(int a, int b) { return a < b ? a : b; }
int dp[K + 1];
void init() {
memset(dp, 0, (K + 1) * sizeof *dp), dp[0] = 1;
for (int s1 = 0; s1 < B; s1++) {
for (int s2 = 0; s2 < s1; s2++)
dp[s1 + s2 + 1] += dp[s1] * dp[s2];
dp[s1 + s1 + 1] += dp[s1] * (dp[s1] + 1) / 2;
}
}
string encode(int n, int x) {
string cc(n, '?');
for (int i = 0; i < n; i++)
cc[i] = (x >> i & 1) + '0';
return cc;
}
int decode(string cc) {
int n = cc.size(), x = 0;
for (int i = 0; i < n; i++)
if (cc[i] == '1')
x |= 1 << i;
return x;
}
int encode_pair(int i, int j) {
return j * (j + 1) / 2 + i;
}
void decode_pair(int x, int &i, int &j) {
j = 0;
while (x >= j + 1)
x -= ++j;
i = x;
}
void decode_tree_(int *pp, int n, int p, int i, int x) {
pp[i] = p;
if (n == 1)
return;
int n1 = min(n - 1, B - 1), n2 = n - 1 - n1;
while (n1 > n2 && x >= dp[n1] * dp[n2])
x -= dp[n1] * dp[n2], n1--, n2++;
if (n2 == 0)
decode_tree_(pp, n1, i, i + 1, x);
else {
int x1, x2;
if (n1 != n2)
x1 = x / dp[n2], x2 = x % dp[n2];
else
decode_pair(x, x1, x2);
decode_tree_(pp, n1, i, i + 1, x1), decode_tree_(pp, n2, i, i + 1 + n1, x2);
}
}
int decode_tree(int *pp, int x) {
int n = 1;
while (n < K && x >= dp[n])
x -= dp[n++];
pp[0] = -1, decode_tree_(pp, n, -1, 0, x);
return n;
}
int n, hu, gu, hv, gv;
string send(int n_, int u, int v) {
init();
n = n_;
if (u > v) {
int tmp;
tmp = u, u = v, v = tmp;
}
hu = u / K, gu = u % K, hv = v / K, gv = v % K;
return encode(L, encode_pair(hu, hv));
}
int qu[K], ppu[K], ppv[K];
int dist(int *pp, int i, int j) {
int d = 0;
while (i != j) {
d++;
if (i > j)
i = pp[i];
else
j = pp[j];
}
return d;
}
int answer(string cc) {
if (hu == hv) {
decode_tree(ppu, decode(cc));
return dist(ppu, gu, gv);
}
decode_tree(ppu, decode(string(cc, 0, LT)));
decode_tree(ppv, decode(string(cc, LT, LT)));
int gu_ = decode(string(cc, LT * 2, LK));
int gv_ = decode(string(cc, LT * 2 + LK, LK));
int d = decode(string(cc, LT * 2 + LK * 2, LN));
return dist(ppu, gu, gu_) + d + dist(ppv, gv_, gv);
}
}
string SendB(int n, int u, int v) {
return Benjamin::send(n, u, v);
}
int Answer(string cc) {
return Benjamin::answer(cc);
}
