#include <bits/stdc++.h>
using namespace std;
// Global state that survives between calls of send_message
static int N_glob = -1; // total number of sites in current test case
static int LOG_ = 0; // number of binary lifting levels
static vector<int> depth_; // depth_[v] = distance from root
static vector<vector<int>> up_; // up_[v][k] = 2^k-th ancestor of v
static vector<int> parent_; // direct parent
static int a_ = 0, b_ = 0; // current diameter endpoints
static int diam_len_ = 0; // current diameter length
static int msg_cnt_ = 0; // number of non-zero messages sent
static bool stop_ = false; // whether to stop sending further messages
static vector<int> S_; // answer list, S_[0] = 0
// --------------------------------------------------------------
// Helper functions for LCA and distance
// --------------------------------------------------------------
static int lca_(int u, int v) {
if (depth_[u] < depth_[v]) swap(u, v);
int diff = depth_[u] - depth_[v];
int bit = 0;
while (diff) {
if (diff & 1) u = up_[u][bit];
diff >>= 1;
++bit;
}
if (u == v) return u;
for (int k = LOG_ - 1; k >= 0; --k) {
if (up_[u][k] != up_[v][k]) {
u = up_[u][k];
v = up_[v][k];
}
}
return up_[u][0];
}
static int dist_(int u, int v) {
int w = lca_(u, v);
return depth_[u] + depth_[v] - 2 * depth_[w];
}
// --------------------------------------------------------------
// Research team – send_message
// --------------------------------------------------------------
int send_message(int N, int i, int Pi) {
// First call for a new test case?
if (N_glob == -1 || N != N_glob) {
N_glob = N;
LOG_ = 0;
while ((1 << LOG_) <= N_glob) ++LOG_;
++LOG_; // matches Python's bit_length() + 1 behavior
depth_.assign(N_glob, 0);
up_.assign(N_glob, vector<int>(LOG_, 0));
parent_.assign(N_glob, 0);
// Root (site 0) is its own ancestor
for (int k = 0; k < LOG_; ++k) up_[0][k] = 0;
// Initialize the diameter
a_ = b_ = 0;
diam_len_ = 0;
msg_cnt_ = 0;
stop_ = false;
S_.assign(N_glob, 0); // S_[0] stays 0
}
// Store the new vertex i
parent_[i] = Pi;
depth_[i] = depth_[Pi] + 1;
up_[i][0] = Pi;
for (int k = 1; k < LOG_; ++k) {
int anc = up_[i][k - 1];
up_[i][k] = up_[anc][k - 1];
}
// Try to enlarge the current diameter
int da = dist_(i, a_);
int db = dist_(i, b_);
bool updated = false;
int other = -1; // endpoint that stays unchanged
if (da > diam_len_ && da >= db && da >= 2 * diam_len_) {
// i becomes the new far endpoint, a_ stays the other endpoint
b_ = i;
diam_len_ = da;
other = a_;
updated = true;
} else if (db > diam_len_ && db >= 2 * diam_len_) {
// i becomes the new far endpoint, b_ stays the other endpoint
a_ = i;
diam_len_ = db;
other = b_;
updated = true;
}
// Decide whether to send a message from site i
if (!stop_ && msg_cnt_ < 50 && updated) {
// Send a non-zero integer equal to the other endpoint + 1
S_[i] = other + 1;
++msg_cnt_;
} else {
S_[i] = 0;
// After we have already sent 50 messages we may be asked
// to stop sending further messages.
if (!updated && !stop_ && msg_cnt_ >= 50) {
stop_ = true;
}
}
return S_[i];
}
// --------------------------------------------------------------
// Museum – longest_path
// --------------------------------------------------------------
std::pair<int, int> longest_path(std::vector<int> S) {
// Find the last (highest index) site that sent a non-zero message
int last_idx = -1;
for (int i = (int)S.size() - 1; i >= 0; --i) {
if (S[i] != 0) {
last_idx = i;
break;
}
}
if (last_idx == -1) {
// Safety; should not happen for a real test
return {0, 0};
}
int u = last_idx;
int v = S[last_idx] - 1; // the other endpoint stored in the message
return {u, v};
}
