#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int K = 14;
int n;
vector<int> parent;
vector<int> depth;
vector<vector<int>> adjlist;
vector<vector<int>> lift;
void prv(vector<int> v) {
for (auto i:v) {
cout << i <<" ";
}
cout << endl;
}
int LCA(int u, int v) {
if (u==v) return u;
if (depth[u] > depth[v]) swap(u,v);
//u is now at a lower depth than v
for (int i=K-1; i>=0; i--) {
if (depth[v] >= depth[u] + (1LL<<i)) {
v = lift[v][i];
}
}
assert(depth[u] == depth[v]);
for (int i=K-1; i>=0; i--) {
if (lift[u][i] != lift[v][i]) {
u = lift[u][i];
v = lift[v][i];
}
}
u = parent[u];
v = parent[v];
assert(u==v);
return u;
}
int dist(int u, int v) {
return depth[u] + depth[v] - 2 * depth[LCA(u, v)];
}
signed send_message(signed N, signed site, signed Pi) {
n=N;
if (site==1) {
parent = vector<int>(N, -1);
parent[0] = 0; //careful!
depth = vector<int>(N, 0);
adjlist = vector<vector<int>>(N);
lift = vector<vector<int>>(N, vector<int>(K, -1));
for (int i=0; i<K; i++) lift[0][i] = 0;
}
parent[site] = Pi;
lift[site][0] = parent[site];
depth[site] = depth[parent[site]] + 1;
adjlist[site].push_back(parent[site]);
adjlist[parent[site]].push_back(site);
for (int i=1; i<K; i++) {
lift[site][i] = lift[lift[site][i-1]][i-1];
//cout << i <<" " << site <<" " << depth[site] <<" " << " " << depth[lift[site][i]] << " " << lift[site][i] << endl;
assert(depth[lift[site][i]] <= depth[site]);
assert(depth[lift[site][i]] >= depth[site] - (1LL<<i));
if (lift[site][i] != 0) {
assert(depth[lift[site][i]] == depth[site] - (1LL<<i));
}
}
if (site<=N-4) {
return 0;
}
//find any diameter
//say that the first r of the n vertices are active at this point
int r = site+1;
vector<int> indices(r); iota(indices.begin(), indices.end(), (int)0);
sort(indices.begin(), indices.end(), [&](const int u, const int v) {
return depth[u] < depth[v];
});
int furthest = indices.back();
vector<int> furthest_distances(r); for (int i=0; i<r; i++) furthest_distances[i] = dist(furthest, i);
sort(indices.begin(), indices.end(), [&](const int u, const int v) {
return furthest_distances[u] < furthest_distances[v];
});
pair<int,int> diameter = {furthest, indices.back()};
if (site>=N-3) {
return furthest;
}
assert(false);
}
std::pair<signed, signed> longest_path(std::vector<signed> S) {
int furthest = S.back();
return {0, furthest};
}
