#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
// Sender's global state (persists across the N-1 calls of the first run)
static int depth_arr[10005];
static int up[10005][15];
static int U_curr = 0, V_curr = 0;
static int U_base = 0, V_base = 0;
static long long W_val = 0;
static vector<int> comb_indices;
static int comb_vals = 0;
static int avail_count = 0;
long long n_choose_k(int n, int k) {
if (k < 0 || k > n) return 0;
if (k == 0 || k == n) return 1;
if (k > n / 2) k = n - k;
long long res = 1;
for (int i = 1; i <= k; ++i) {
res = res * (n - i + 1) / i;
}
return res;
}
int get_lca(int u, int v) {
if (depth_arr[u] < depth_arr[v]) swap(u, v);
for (int j = 14; j >= 0; --j) {
if (depth_arr[u] - (1 << j) >= depth_arr[v]) {
u = up[u][j];
}
}
if (u == v) return u;
for (int j = 14; 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) {
memset(depth_arr, 0, sizeof(depth_arr));
memset(up, 0, sizeof(up));
U_curr = 0; V_curr = 0;
U_base = 0; V_base = 0;
W_val = 0;
comb_indices.clear();
comb_vals = 0;
avail_count = 0;
}
depth_arr[i] = depth_arr[Pi] + 1;
up[i][0] = Pi;
for (int j = 1; j <= 14; ++j) {
up[i][j] = up[up[i][j - 1]][j - 1];
}
if (N > 100 && i == N - 150) {
U_base = U_curr;
V_base = V_curr;
W_val = (long long)U_base * N + V_base;
long long C = W_val / 64;
comb_vals = W_val % 64;
int k = 6;
for (int x = 0; x < 50 && k > 0; ++x) {
long long ways = n_choose_k(50 - 1 - x, k - 1);
if (C < ways) {
comb_indices.push_back(x);
k--;
} else {
C -= ways;
}
}
}
int dU = get_dist(i, U_curr);
int dV = get_dist(i, V_curr);
int dUV = get_dist(U_curr, V_curr);
int change = 0;
if (dU > dUV && dU >= dV) {
V_curr = i;
change = 3;
} else if (dV > dUV) {
U_curr = i;
change = 4;
}
if (N <= 100) {
if (i == N - 1) return U_curr * 105 + V_curr;
return 0;
} else {
if (i >= N - 150) {
if (change > 0) return change;
int ans = 0;
auto it = find(comb_indices.begin(), comb_indices.end(), avail_count);
if (it != comb_indices.end()) {
int idx = it - comb_indices.begin();
ans = ((comb_vals >> idx) & 1) + 1;
}
avail_count++;
return ans;
}
return 0;
}
}
std::pair<int, int> longest_path(std::vector<int> S) {
int N = S.size();
if (N <= 100) {
int val = S[N - 1];
return {val / 105, val % 105};
}
int final_U = -1, final_V = -2;
vector<int> comb_idx;
int comb_v = 0;
int avail_c = 0;
for (int i = N - 150; i < N; ++i) {
if (S[i] == 3) {
final_V = i;
} else if (S[i] == 4) {
final_U = i;
} else {
if (S[i] == 1 || S[i] == 2) {
comb_idx.push_back(avail_c);
comb_v |= ((S[i] - 1) << (comb_idx.size() - 1));
}
avail_c++;
}
}
if (comb_idx.size() == 6) {
long long C = 0;
int k = 6;
for (int i = 0; i < 50 && k > 0; ++i) {
if (find(comb_idx.begin(), comb_idx.end(), i) != comb_idx.end()) {
k--;
} else {
C += n_choose_k(50 - 1 - i, k - 1);
}
}
long long W = C * 64 + comb_v;
int U_base = W / N;
int V_base = W % N;
if (final_U == -1) final_U = U_base;
if (final_V == -2) final_V = V_base;
} else {
if (final_U == -1) final_U = 0;
if (final_V == -2) final_V = 0;
}
return {final_U, final_V};
}
