#if 0
#include "migration.h"
#else
#endif
#include <algorithm>
#include <vector>
using namespace std;
vector<int> tree[10005];
pair<int, int> depth[10005];
int last[30], id11[3000], a1, a2, ta1, ta2, len = -1;
void dfs_depth(int u, int par, int d) {
depth[u] = {0, 0};
if(tree[u].size() == 1) depth[u] = {d, u};
for(int child: tree[u]) if(child != par) {
dfs_depth(child, u, d + 1);
depth[u] = max(depth[u], depth[child]);
}
}
void reset_a1a2(int n) {
dfs_depth(n, n, 0);
if(len == -1) {
a1 = depth[n].second;
dfs_depth(a1, a1, 0);
a2 = depth[a1].second;
len = depth[a1].first;
return;
}
if(tree[a1].size() == 1 && depth[a1].first > len) len++, a2 = n;
if(tree[a2].size() == 1 && depth[a2].first > len) len++, a1 = n;
}
void encode_last11(int num, int *to) {
int rem = num % 64, dv = num / 64;
for(int i = 0; i < (1 << 11); i++) if(__builtin_popcount(i) == 3) {
dv--;
if(dv == 0) {
for(int j = 0; j < 11; j++) if(i & (1 << j)) to[j] = 1 + (rem %4), rem /= 4;
break;
}
}
}
int decode_last11(int *from) {
int mask = 0, rem = 0, cnt = 0;
for(int j = 10; j >= 0; j--) if(from[j] != 0) {
mask |= (1 << j);
rem = 4 * rem + from[j] - 1;
}
for(int i = 0; i < (1 << 11); i++) if(__builtin_popcount(i) == 3) {
if(i == mask) break;
cnt++;
}
return cnt * 64 + rem;
}
int send_message(int N, int i, int Pi) {
tree[Pi].push_back(i);
tree[i].push_back(Pi);
N--;
if(i <= N - 28) return 0;
reset_a1a2(i);
if(i == N - 27) encode_last11(a2, last + 17), ta2 = a2;
if(i == N - 16) encode_last11(a1, last + 6), ta1 = a1;
if(i == N - 5 && a2 != ta2) {
int mask = (N - 4) - a2;
ta2 = a2;
last[5] = mask / 5, last[ 4] = mask % 5;
}
if(i == N - 3 && a1 != ta1) {
int mask = (N - 2) - a1;
ta1 = a1;
last[3] = mask / 4, last[2] = mask % 4;
}
if(i == N - 2 && a1 == i) last[2] = 4, ta1 = a1;
if(i == N - 1 && a2 != ta2) ta2 = a2, last[1] = N - a2;
if(i == N) {
if(a1 == N) last[0] = 1;
if(a2 == N && a1 == ta1) last[0] = 2;
if(a1 == N - 1 && a2 == ta2) last[0] = 3;
if(a1 == N - 1 && a2 == N) last[0] = 4;
}
return last[N - i];
}
pair<int, int> longest_path(vector<int> S) {
int N = S.size() - 1;
for(int i = 0; i < min(N,28); i++) last[i] = S[N - i];
a2 = decode_last11(last + 17);
a1 = decode_last11(last + 6);
if(last[5] != 0 || last[4] != 0) a2 = (N - 4) - 5 * last[5] - last[4];
if(last[2] == 4) a1 = N - 2;
else if(last[3] != 0 || last[2] != 0) a1 = (N - 2) - last[3] * 4 - last[2];
if(last[1] != 0) a2 = N - last[1];
if(last[0] == 1) a1 = N;
if(last[0] == 2) a2 = N;
if(last[0] == 3) a1 = N - 1;
if(last[0] == 4) a1 = N - 1, a2 = N;
return {a1, a2};
}
