#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
vector<int> p;
pii find(int u){
int n = (int) p.size();
vector<int> g[n];
for (int i = 1; i < n; i++){
g[p[i]].pb(i);
g[i].pb(p[i]);
}
function<pii(int, int)> dfs = [&](int v, int pr){
pii out = {0, v};
for (int i: g[v]){
if (i == pr) continue;
auto [d, x] = dfs(i, v);
out = max(out, {d + 1, x});
}
return out;
};
return dfs(u, 0);
}
int f, G;
int send_message(int n, int i, int k){
if (i == 1) p.pb(0);
p.pb(k);
if (i == (n - 2)){
f = find(0).ss;
G = find(f).ss;
return f;
}
if (i == (n - 1)){
auto [d1, x] = find(0);
auto [d2, y] = find(x);
auto [a, x1] = find(f);
auto [b, y1] = find(G);
assert(max(a, b) == d2);
if (x == i || y == i){
return 1e4 + x + y - i;
}
return G;
}
return 0;
}
pii longest_path(vector<int> s){
int n = (int) s.size();
if (s[n - 1] >= 1e4){
int k = s[n - 1] - 1e4;
return {k, n - 1};
}
return {s[n - 2], s[n - 1]};
}
