#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
void dfs(int u, int p, vi &dist, vvi &adj) {
for (auto &v : adj[u]) {
if (v == p) continue;
dist[v] = dist[u] + 1;
dfs(v, u, dist, adj);
}
}
int furthest_from(int u, int n, vvi &adj) {
vector<int> dist(n);
dfs(u, u, dist, adj);
int f = 0; for (int i = 0; i < n; i++) if (dist[i] > dist[f]) f = i;
return f;
}
pi furthest_pair(int n, vvi &adj) {
vector<int> dist(n);
dfs(0, 0, dist, adj);
int f1 = 0; for (int i = 0; i < n; i++) if (dist[i] > dist[f1]) f1 = i;
dist = vi(n, 0);
dfs(f1, f1, dist, adj);
int f2 = 0; for (int i = 0; i < n; i++) if (dist[i] > dist[f2]) f2 = i;
return {min(f1, f2), max(f1, f2)};
}
vvi adj;
pi fr;
int send_message(int n, int i, int Pi) {
if (i <= 1) adj.assign(n+1, vi());
adj[Pi].push_back(i);
adj[i].push_back(Pi);
// if (i >= n - 18) {
// int furthest = furthest_from(0, n, adj);
// int bit = i - (n - 18);
// if (furthest == i) {
// return 2;
// } else {
// return (furthest & (1 << bit)) ? 1 : 0;
// }
// }
if (i == n - 2) {
fr = furthest_pair(n, adj);
return fr.first;
} else if (i == n - 1) {
auto f = furthest_pair(n, adj);
if (f.first == fr.first && f.second == fr.second) {
return f.second;
} else {
return 10000 + f.first;
}
}
return 0;
}
pi longest_path(vi S) {
int n = S.size();
if (S[n-1] >= 10000) {
return {n-1, S[n-1] - 10000};
} else {
return {S[n-1], S[n-2]};
}
// int pf = 0;
// for (int i = max(0, n - 18); i < n; i++) if (S[i] == 2) pf = i;
// if (pf != 0) return {0, pf};
// for (int i = n - 18; i < n; i++) {
// pf += S[i] << (i - (n - 18));
// }
// return {0, pf};
}
