#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 dUV = 0;
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) {
// Initialize the root node exactly once
if (i == 1) {
U_curr = 0;
V_curr = 0;
dUV = 0;
depth_arr[0] = 0;
for (int j = 0; j <= 16; ++j) {
up[0][j] = 0;
}
}
// Add node i to the tree
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];
}
// Check distances to the current diameter endpoints
int dU = get_dist(i, U_curr);
int dV = get_dist(i, V_curr);
// If the diameter strictly increases
if (dU > dUV || dV > dUV) {
if (dU >= dV) {
// New diameter is (U_curr, i). V_curr is replaced.
V_curr = i;
dUV = dU;
return 1;
} else {
// New diameter is (V_curr, i). U_curr is replaced.
U_curr = i;
dUV = dV;
return 2;
}
}
// Diameter didn't change
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S) {
int U = 0, V = 0;
// The Museum simply replays the endpoint swaps sequentially
for (int i = 1; i < S.size(); ++i) {
if (S[i] == 1) {
V = i; // 1 meant V was replaced by i
} else if (S[i] == 2) {
U = i; // 2 meant U was replaced by i
}
}
return {U, V};
}
