#include <vector>
#include <algorithm>
static std::vector<int> adj[10005];
static int U_curr = -1, V_curr = -1;
static std::vector<int> bits_to_send;
static int bit_idx = 0;
int get_dist(int u, int v) {
if (u == v) return 0;
std::vector<int> q, dist(10005, -1);
q.push_back(u);
dist[u] = 0;
int head = 0;
while (head < q.size()) {
int curr = q[head++];
if (curr == v) return dist[curr];
for (int nxt : adj[curr]) {
if (dist[nxt] == -1) {
dist[nxt] = dist[curr] + 1;
q.push_back(nxt);
}
}
}
return -1;
}
std::pair<int, int> get_diameter(int max_node) {
if (max_node == 0) return {0, 0};
std::vector<int> q, dist(10005, -1);
q.push_back(0); dist[0] = 0;
int head = 0, farthest = 0, max_d = 0;
while (head < q.size()) {
int curr = q[head++];
if (dist[curr] > max_d) { max_d = dist[curr]; farthest = curr; }
for (int nxt : adj[curr]) {
if (nxt <= max_node && dist[nxt] == -1) {
dist[nxt] = dist[curr] + 1;
q.push_back(nxt);
}
}
}
int U = farthest;
q.clear(); dist.assign(10005, -1);
q.push_back(U); dist[U] = 0;
head = 0; max_d = 0; farthest = U;
while (head < q.size()) {
int curr = q[head++];
if (dist[curr] > max_d) { max_d = dist[curr]; farthest = curr; }
for (int nxt : adj[curr]) {
if (nxt <= max_node && dist[nxt] == -1) {
dist[nxt] = dist[curr] + 1;
q.push_back(nxt);
}
}
}
return {U, farthest};
}
int send_message(int N, int i, int Pi) {
int B = std::min(45, N - 2);
if (i == 1) {
for (int j = 0; j <= N; j++) adj[j].clear();
U_curr = -1; V_curr = -1;
bits_to_send.clear();
bit_idx = 0;
}
adj[i].push_back(Pi);
adj[Pi].push_back(i);
if (i == N - B - 1) {
std::pair<int, int> p = get_diameter(i);
U_curr = p.first;
V_curr = p.second;
for (int bit = 0; bit < 14; bit++) bits_to_send.push_back((U_curr >> bit) & 1);
for (int bit = 0; bit < 14; bit++) bits_to_send.push_back((V_curr >> bit) & 1);
}
if (i >= N - B) {
int dU = get_dist(i, U_curr);
int dV = get_dist(i, V_curr);
int D = get_dist(U_curr, V_curr);
if (dU > D && dU >= dV) {
V_curr = i;
bits_to_send.resize(14);
return 4;
} else if (dV > D && dV > dU) {
U_curr = i;
if (bit_idx < 14) bit_idx = 14;
return 3;
} else {
if (bit_idx < bits_to_send.size()) {
int b = bits_to_send[bit_idx++];
return b + 1;
}
return 1;
}
}
return 0;
}
std::pair<int,int> longest_path(std::vector<int> S) {
int N = S.size();
int B = std::min(45, N - 2);
int U_final = -1, V_final = -1;
std::vector<int> u_bits, v_bits;
int target = 0;
for (int i = N - B; i < N; i++) {
if (S[i] == 0) continue;
if (S[i] == 3) {
U_final = i;
target = 1;
} else if (S[i] == 4) {
V_final = i;
} else {
int b = S[i] - 1;
if (target == 0) {
u_bits.push_back(b);
if (u_bits.size() == 14) target = 1;
} else {
if (v_bits.size() < 14) v_bits.push_back(b);
}
}
}
if (U_final == -1) {
U_final = 0;
for (int i = 0; i < u_bits.size(); i++) U_final |= (u_bits[i] << i);
}
if (V_final == -1) {
V_final = 0;
for (int i = 0; i < v_bits.size(); i++) V_final |= (v_bits[i] << i);
}
return {U_final, V_final};
}
