#include <vector>
#include <algorithm>
using namespace std;
// 用于 send_message 维护内部树深及倍增LCA
static int depth[10005];
static int up[14][10005];
static int U_node = 0, V_node = 0, D_tree = 0;
static int max_dist_0 = 0, furthest_from_0 = 0;
static int protocol = 0;
static long long A_star = 0, B_star = 0;
static long long id_val = 0;
int get_lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int j = 0; j < 14; j++) {
if ((diff >> j) & 1) u = up[j][u];
}
if (u == v) return u;
for (int j = 13; j >= 0; j--) {
if (up[j][u] != up[j][v]) {
u = up[j][u];
v = up[j][v];
}
}
return up[0][u];
}
int get_dist(int u, int v) {
return depth[u] + depth[v] - 2 * depth[get_lca(u, v)];
}
int send_message(int N, int i, int Pi) {
if (i == 1) { // 评测可能多次调用，复位全局变量
depth[0] = 0;
for (int j = 0; j < 14; j++) up[j][0] = 0;
U_node = 0; V_node = 0; D_tree = 0;
max_dist_0 = 0; furthest_from_0 = 0;
protocol = 0; A_star = 0; B_star = 0; id_val = 0;
}
// 树上倍增更新
depth[i] = depth[Pi] + 1;
up[0][i] = Pi;
for (int j = 1; j < 14; j++) {
up[j][i] = up[j-1][up[j-1][i]];
}
int dist0 = get_dist(i, 0);
bool dist0_inc = false;
if (dist0 > max_dist_0) {
dist0_inc = true;
max_dist_0 = dist0;
furthest_from_0 = i;
}
int dU = get_dist(i, U_node);
int dV = get_dist(i, V_node);
bool increased = false;
int replaced = 0; // 0:不变, 1: 替换V, 2: 替换U
int max_d = max(dU, dV);
// 直径在线贪心更新
if (max_d > D_tree) {
increased = true;
D_tree = max_d;
if (dU > dV) {
replaced = 1;
V_node = i;
} else {
replaced = 2;
U_node = i;
}
}
if (i == N - 28) { // 第 N-28 步时抉择协议
if (U_node == 0 || V_node == 0) {
protocol = 1; // 极大可能是 Subtask 1，用轻量级通信保分
} else {
protocol = 2; // 常规 Subtask 2
A_star = min(U_node, V_node);
B_star = max(U_node, V_node);
id_val = A_star * 10000LL + B_star;
}
}
if (i == N - 15 && protocol == 1) {
B_star = furthest_from_0;
}
if (protocol == 2 && i >= N - 27) { // 发送 Protocol 2: 27位组合位
int bit_idx = i - (N - 27);
int d_i = (id_val >> bit_idx) & 1;
int u_i = increased ? replaced : 0;
return u_i * 2 + d_i + 1; // 范围在 1 到 6
}
if (protocol == 1 && i >= N - 14) { // 发送 Protocol 1: 14位组合位
int bit_idx = i - (N - 14);
int d_i = (B_star >> bit_idx) & 1;
int u_i = dist0_inc ? 1 : 0;
return u_i * 2 + d_i + 1; // 范围在 1 到 4
}
return 0; // 沉默期
}
std::pair<int, int> longest_path(std::vector<int> S) {
int N = S.size();
bool is_p2 = false;
// 检查协议类型（如果倒数第 27 步到 15 步有非零，定是 protocol 2）
for (int i = N - 27; i < N - 14; i++) {
if (S[i] > 0) is_p2 = true;
}
if (is_p2) {
long long id = 0;
for (int i = N - 27; i < N; i++) {
int val = S[i] - 1;
int d = val % 2;
id |= ((long long)d << (i - (N - 27)));
}
int U = id / 10000;
int V = id % 10000;
for (int i = N - 27; i < N; i++) {
int val = S[i] - 1;
int u = val / 2;
if (u == 1) V = i;
if (u == 2) U = i;
}
return {U, V};
} else {
int V = 0;
for (int i = N - 14; i < N; i++) {
int val = S[i] - 1;
int d = val % 2;
V |= (d << (i - (N - 14)));
}
for (int i = N - 14; i < N; i++) {
int val = S[i] - 1;
int u = val / 2;
if (u == 1) V = i;
}
return {0, V};
}
}
