#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Sender's global state
static int depth_arr[100005];
static int up[100005][17];
static int U_curr = 0, V_curr = 0;
static int max_dist = 0;
static int msg_count = 0;
static bool is_simple_path = true;
int get_lca(int u, int v) {
if (depth_arr[u] < depth_arr[v]) swap(u, v);
for (int j = 16; j >= 0; --j) {
if (depth_arr[u] - (1 << j) >= depth_arr[v]) u = up[u][j];
}
if (u == v) return u;
for (int j = 16; j >= 0; --j) {
if (up[u][j] != up[v][j]) {
u = up[u][j];
v = up[v][j];
}
}
return up[u][0];
}
int get_dist(int u, int v) {
return depth_arr[u] + depth_arr[v] - 2 * depth_arr[get_lca(u, v)];
}
int send_message(int N, int i, int Pi) {
if (i == 1) {
U_curr = 0; V_curr = 0; max_dist = 0; msg_count = 0;
is_simple_path = true;
depth_arr[0] = 0;
for (int j = 0; j <= 16; ++j) up[0][j] = 0;
}
if (Pi != i - 1) is_simple_path = false;
depth_arr[i] = depth_arr[Pi] + 1;
up[i][0] = Pi;
for (int j = 1; j <= 16; ++j) {
up[i][j] = up[up[i][j - 1]][j - 1];
}
int dU = get_dist(i, U_curr);
int dV = get_dist(i, V_curr);
// If it's a simple path, we remain perfectly silent (0 messages)
if (is_simple_path) return 0;
bool changed = false;
int previous_U = U_curr, previous_V = V_curr;
if (dU > max_dist || dV > max_dist) {
if (dU >= dV) { V_curr = i; max_dist = dU; }
else { U_curr = i; max_dist = dV; }
changed = true;
}
// We only send a message if the diameter changed AND we have quota
// We encode the OTHER endpoint so the Museum can pair it with `i`
if (changed && msg_count < 48) {
msg_count++;
// If U was replaced by i, we send V_curr + 1. If V was replaced, we send U_curr + 1
return (dU >= dV) ? (previous_U + 1) : (previous_V + 1);
}
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S) {
int N = S.size();
int final_U = 0, final_V = 0;
bool received_any = false;
for (int i = 1; i < N; ++i) {
if (S[i] > 0) {
received_any = true;
final_V = i; // The index where the diameter changed
final_U = S[i] - 1; // The other endpoint encoded in the value
}
}
// If the sender was perfectly silent, it was an adversarial simple path graph
if (!received_any) {
return {0, N - 1};
}
// Otherwise, we safely return the last recorded endpoints
return {final_U, final_V};
}
