#include "Ali.h"
#include <cstring>
#include <string>
#include <vector>
using namespace std;
typedef vector<int> vi;
namespace Ali {
const int N = 10000, K = 20;
const int B = 7, M = (N + B - 1) / B, L = 14; /* L = ceil(log2(N)) */
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 decode2(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;
}
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]);
for (int i = 0; i < n; i++)
SetID(i, i);
}
int dd[N];
void dfs(int p, int i, int d) {
dd[i] = d;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p)
dfs(i, j, d + 1);
}
}
string send(string bb) {
int u_, v_; decode2(M, decode(bb, 0, K), u_, v_);
int ul = u_ * B, ur = min((u_ + 1) * B, n), vl = v_ * B, vr = min((v_ + 1) * B, n);
string cc((ur - ul) * (vr - vl) * L, '?');
for (int u = ul; u < ur; u++) {
dfs(-1, u, 0);
for (int v = vl; v < vr; v++)
encode(cc, ((u - ul) * (vr - vl) + (v - vl)) * L, L, dd[v]);
}
return cc;
}
}
void Init(int n, vi ii, vi jj) {
Ali::init(ii, jj, n);
}
string SendA(string bb) {
return Ali::send(bb);
}
#include "Benjamin.h"
#include <string>
#include <vector>
using namespace std;
typedef vector<int> vi;
namespace Benjamin {
const int N = 10000, K = 20;
const int B = 7, M = (N + B - 1) / B, L = 14; /* L = ceil(log2(N)) */
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 encode2(int n, int i, int j) {
return i * (n * 2 - i + 1) / 2 + j - i;
}
int n, u, v, u_, v_;
string send(int n_, int u__, int v__) {
n = n_, u = u__, v = v__;
if (u > v) {
int tmp;
tmp = u, u = v, v = tmp;
}
u_ = u / B, v_ = v / B;
string bb(K, '?');
encode(bb, 0, K, encode2(M, u_, v_));
return bb;
}
int answer(string aa) {
int ul = u_ * B, vl = v_ * B, vr = min((v_ + 1) * B, n);
return decode(aa, ((u - ul) * (vr - vl) + (v - vl)) * L, L);
}
}
string SendB(int n, int u, int v) {
return Benjamin::send(n, u, v);
}
int Answer(string aa) {
return Benjamin::answer(aa);
}
