#include "Ali.h"
#include <bits/stdc++.h>
using namespace std;
// plan:
// ali chooses random permutation on [0, n)
// benjamin sends as much info about X and Y as they can
// we send back all relevant dists
// benjamin parses them
namespace {
int n;
vector<vector<int>> adj;
int w;
} // namespace
void Init(int N, vector<int> U, vector<int> V) {
n = N;
w = bit_width(unsigned(n));
adj.clear();
adj.resize(n);
mt19937 gen(random_device{}());
vector<int> p(n);
iota(p.begin(), p.end(), 0);
shuffle(p.begin(), p.end(), gen);
for (int i = 0; i < n; ++i) { // node i is now referred to as p[i]
SetID(i, p[i]);
}
for (int i = 0; i < n - 1; ++i) {
adj[p[U[i]]].push_back(p[V[i]]), adj[p[V[i]]].push_back(p[U[i]]);
}
}
string SendA(string S) {
string ret;
auto send = [&](int x, int w) {
for (int i = 0; i < w; ++i) {
ret.push_back('0' + !!(x & 1 << i));
}
};
auto rev = [&](string s) { return reverse(s.begin(), s.end()), s; };
int x = stoi(rev(S.substr(0, w)), nullptr, 2);
int bits = 20 - w; // bits we have ab the later part
int y_minus_x_end = stoi(rev(S.substr(w)), nullptr, 2);
auto dist = ([&](int u) {
vector<int> dist(n, int(1e9));
dist[u] = 0;
vector<bool> vis(n);
queue<int> q;
q.push(u);
while (!q.empty()) {
int u = q.front();
q.pop();
if (vis[u]) {
continue;
}
vis[u] = true;
for (int &i : adj[u]) {
if (dist[u] + 1 < dist[i]) {
dist[i] = dist[u] + 1;
q.push(i);
}
}
}
return dist;
})(x);
for (int y = x + 1; y < n; ++y) {
int y_minus_x = y - x;
int end = y_minus_x & ((1 << bits) - 1); // (1<<3-1) = 111_2
if (end != y_minus_x_end) {
continue;
}
send(dist[y], w);
}
return ret;
}
#include "Benjamin.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int w, x, Y, n;
} // namespace
string SendB(int N, int X, int Y) {
n = N;
if (X > Y) {
swap(X, Y);
}
x = X, ::Y = Y;
string ret;
w = bit_width(unsigned(N));
auto send = [&](int x, int w) { // send the last w bits of x
for (int i = 0; i < w; ++i) {
ret.push_back('0' + !!(x & 1 << i));
}
};
send(X, w);
send(Y - X, 20 - w);
return ret;
}
int Answer(string T) {
int cursor = 0;
auto rev = [&](string s) { return reverse(s.begin(), s.end()), s; };
auto recv = [&]() {
return stoi(rev(T.substr(exchange(cursor, cursor + w), w)), nullptr, 2);
};
int bits = 20 - w;
for (int y = x + 1; y < n; ++y) {
if (((y - x) & ((1 << bits) - 1)) != ((Y - x) & ((1 << bits) - 1))) {
continue;
}
int dist = recv();
if (y == Y) {
return dist;
}
}
}
