#include "migrations.h"
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 10000;
const int LOG = 14; // 2^14 > 10000
const int K = 2500; // bucket size for ranking
static int N_global;
static int parent[MAXN];
static int depth[MAXN];
static int up[MAXN][LOG];
static int cur_a, cur_b;
static int stored_idx; // remainder for last step
static bool inited = false;
// ----- LCA and distance -----
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int k = 0; k < LOG; ++k)
if (diff & (1 << k))
u = up[u][k];
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];
}
int dist(int u, int v) {
int w = lca(u, v);
return depth[u] + depth[v] - 2 * depth[w];
}
// ----------------------------
int send_message(int N, int i, int Pi) {
if (!inited) {
N_global = N;
depth[0] = 0;
for (int k = 0; k < LOG; ++k) up[0][k] = 0;
cur_a = cur_b = 0;
inited = true;
}
// add node i
parent[i] = Pi;
depth[i] = depth[Pi] + 1;
up[i][0] = Pi;
for (int k = 1; k < LOG; ++k)
up[i][k] = up[ up[i][k-1] ][k-1];
if (i == N - 2) {
// update diameter with node i
int d_ab = dist(cur_a, cur_b);
int d_ai = dist(cur_a, i);
int d_bi = dist(cur_b, i);
int maxd = d_ab;
int new_a = cur_a, new_b = cur_b;
if (d_ai > maxd) { maxd = d_ai; new_a = cur_a; new_b = i; }
if (d_bi > maxd) { maxd = d_bi; new_a = i; new_b = cur_b; }
cur_a = new_a; cur_b = new_b;
// encode the pair (cur_a, cur_b)
int n = N - 1; // number of nodes before the last one
int lo = min(cur_a, cur_b), hi = max(cur_a, cur_b);
long long rank = lo * (2LL * n - lo - 1) / 2 + (hi - lo - 1);
stored_idx = rank % K;
int bucket = rank / K;
return bucket + 1; // 1 … 20000
}
else if (i == N - 1) {
// use the old diameter (cur_a, cur_b) to decide the final pair
int d_ab = dist(cur_a, cur_b);
int d_ai = dist(cur_a, i);
int d_bi = dist(cur_b, i);
int choice = 0; // 0 -> (cur_a,cur_b), 1 -> (cur_a,i), 2 -> (cur_b,i)
if (d_ai > d_ab) choice = 1;
else if (d_bi > d_ab) choice = 2;
int v2 = stored_idx * 3 + choice + 1;
return v2;
}
else {
// ordinary update for earlier nodes
int d_ab = dist(cur_a, cur_b);
int d_ai = dist(cur_a, i);
int d_bi = dist(cur_b, i);
int maxd = d_ab;
int new_a = cur_a, new_b = cur_b;
if (d_ai > maxd) { maxd = d_ai; new_a = cur_a; new_b = i; }
if (d_bi > maxd) { maxd = d_bi; new_a = i; new_b = cur_b; }
cur_a = new_a; cur_b = new_b;
return 0; // no message
}
}
pair<int, int> longest_path(vector<int> S) {
int N = S.size();
int v1 = S[N-2];
int v2 = S[N-1];
int bucket = v1 - 1;
int t = v2 - 1;
int idx = t / 3;
int choice = t % 3;
int n = N - 1; // number of nodes before last
long long rank = bucket * K + idx;
// find the unordered pair (lo,hi) from rank
int lo = -1, hi = -1;
for (int x = 0; x < n; ++x) {
long long start = x * (2LL * n - x - 1) / 2;
long long cnt = n - x - 1;
if (rank >= start && rank < start + cnt) {
lo = x;
hi = x + 1 + (rank - start);
break;
}
}
if (choice == 0)
return {lo, hi};
else if (choice == 1)
return {lo, N-1};
else // choice == 2
return {hi, N-1};
}
