/* 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)) */
int min(int a, int b) { return a < b ? a : b; }
void encode(string &aa, int i_, int n, int x) {
for (int i = 0; i < n; i++)
aa[i_ + i] = (x >> i & 1) + '0';
}
int decode(string &aa, int i_, int n) {
int x = 0;
for (int i = 0; i < n; i++)
if (aa[i_ + i] == '1')
x |= 1 << i;
return x;
}
void decode_pair(int n, int x, int &i, int &j) {
i = 0;
while (x >= n - i)
x -= n - i++;
j = i + x;
}
int ej[N][3], eo[N], n;
void append(int i, int j) {
ej[i][eo[i]++] = j;
}
int dd[N], pp[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;
int s = 1;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p)
s += dfs1(i, j, d + 1);
}
if (s >= B || p == -1)
ii[m++] = i, s = 0;
return s;
}
void dfs2(int p, int i, int h) {
if (hh[i] != -1)
return;
hh[i] = h, iii[h][gg[i] = kk[h]++] = i;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p)
dfs2(i, j, h);
}
}
void init(vi ii, vi jj, int n_) {
n = n_;
memset(eo, 0, n * sizeof *eo);
for (int h = 0; h < n - 1; h++)
append(ii[h], jj[h]), append(jj[h], ii[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;
memset(hh, -1, n * sizeof *hh);
for (int h = m - 1; h >= 0; h--) {
i = ii[h];
kk[h] = 0, dfs2(pp[i], i, h);
}
for (int 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 bb) {
int hu, hv; decode_pair(M, decode(bb, 0, L), hu, hv);
if (hu == hv) {
string cc((K - 1) * LK, '0');
for (int g = 1; g < kk[hu]; g++)
encode(cc, (g - 1) * LK, LK, gg[pp[iii[hu][g]]]);
return cc;
}
int u = iii[hu][0], v = iii[hv][0];
if (dist(u, v) == dd[v] - dd[u]) {
int u_ = v;
while (hh[u_] != hh[u])
u_ = pp[u_];
u = u_;
}
string cc(K * 2 * LK + LN, '0');
for (int g = 0; g < kk[hu]; g++)
encode(cc, g * LK, LK, dist(u, iii[hu][g]));
for (int g = 0; g < kk[hv]; g++)
encode(cc, (K + g) * LK, LK, dist(v, iii[hv][g]));
encode(cc, K * 2 * LK, LN, dist(u, v));
return cc;
}
}
void Init(int n, vi ii, vi jj) {
Ali::init(ii, jj, n);
}
string SendA(string bb) {
return Ali::send(bb);
}
/* https://www2.ioi-jp.org/camp/2022/2022-sp-tasks/contest2/flights-review.pdf */
#include "Benjamin.h"
#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)) */
int min(int a, int b) { return a < b ? a : b; }
void encode(string &aa, int i_, int n, int x) {
for (int i = 0; i < n; i++)
aa[i_ + i] = (x >> i & 1) + '0';
}
int decode(string &aa, int i_, int n) {
int x = 0;
for (int i = 0; i < n; i++)
if (aa[i_ + i] == '1')
x |= 1 << i;
return x;
}
int encode_pair(int n, int i, int j) {
return i * (n * 2 - i + 1) / 2 + j - i;
}
int n, hu, gu, hv, gv;
string send(int n_, int u, int v) {
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;
string bb(L, '0');
encode(bb, 0, L, encode_pair(M, hu, hv));
return bb;
}
int pp[K];
int answer(string aa) {
if (hu == hv) {
for (int g = 1; g < K; g++)
pp[g] = decode(aa, (g - 1) * LK, LK);
int d = 0;
while (gu != gv) {
d++;
if (gu > gv)
gu = pp[gu];
else
gv = pp[gv];
}
return d;
}
return decode(aa, gu * LK, LK) + decode(aa, (K + gv) * LK, LK) + decode(aa, K * 2 * LK, LN);
}
}
string SendB(int n, int u, int v) {
return Benjamin::send(n, u, v);
}
int Answer(string aa) {
return Benjamin::answer(aa);
}
