#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;
int 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).ss;
}
int f;
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);
return f;
}
if (i == (n - 1)){
if (find(0) != f){
return 1e4 + find(n - 1);
}
return find(f);
}
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]};
}
