#include <vector>
#include <algorithm>
using namespace std;
// 倍增LCA及树深维护
static int depth[10005];
static int up[14][10005];
// 在线直径和内部状态维护
static int U_node = 0, V_node = 0, D_tree = 0;
static long long id_val = 0;
// O(log N) 查询两点距离
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;
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 dU = get_dist(i, U_node);
int dV = get_dist(i, V_node);
bool increased = false;
int replaced = 0;
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 if (dV > dU) {
replaced = 2;
U_node = i;
} else { // dU == dV 时的特判：绝对偏袒保留 0 号节点
if (U_node == 0) {
replaced = 1;
V_node = i;
} else if (V_node == 0) {
replaced = 2;
U_node = i;
} else {
replaced = 1;
V_node = i;
}
}
}
// 在 N-27 步，冻结末期最初始的基础直径端点身份
if (i == N - 27) {
// 关键特化定轴：如果当前端点 V 是 0，强制将其交换锁定至 U_node
// 这样在 Subtask 1 中 U_node(0) 永远不被替换，也就永远规避掉发出信号 5 和 6
if (V_node == 0) {
swap(U_node, V_node);
// 如果碰巧当步发生了直径延展，变更被取代者标签
if (increased) replaced = 3 - replaced;
}
id_val = U_node * 10000LL + V_node;
}
// 协议启动：最后的 27 步无断点全频段连续播报 (M = 27 <= 50)
if (i >= N - 27) {
int bit_idx = i - (N - 27);
long long b = (id_val >> bit_idx) & 1;
// 原子级叠加协议：基础数据信息(b) 与 事件抢占信息(replaced) 完美融合
if (!increased) {
return b + 1; // 信号 1~2：只传底部位 (Z<=2)
} else {
if (replaced == 1)
return b + 3; // 信号 3~4：传底部位并宣告 V 突发易主 (Z<=4)
else
return b + 5; // 信号 5~6：传底部位并宣告 U 突发易主 (Z<=6)
}
}
return 0; // 前期积蓄能量，潜伏静默节省 M 额度
}
// ================== 博物馆 ==================
std::pair<int, int> longest_path(std::vector<int> S) {
int N = S.size();
long long id = 0;
int final_U = -1, final_V = -1;
for (int i = N - 27; i < N; i++) {
int val = S[i];
if (val == 0) continue;
// 解析载波信号的基数据位与控制事件位
long long b = (val - 1) % 2;
int state = (val - 1) / 2; // 0: 平静, 1: V 换届, 2: U 换届
id |= (b << (i - (N - 27)));
// 实时的演化覆写
if (state == 1) final_V = i;
if (state == 2) final_U = i;
}
int initial_U = id / 10000;
int initial_V = id % 10000;
// 如果某端点自始至终未曾变更，采用从底座恢复的基底端点
if (final_U == -1) final_U = initial_U;
if (final_V == -1) final_V = initial_V;
return {final_U, final_V};
}
