#include "migrations.h"
#include <iostream>
#include <algorithm>
using namespace std;
int LOG = 14;
int d1, d2;
int to_send_1, to_send_2;
int diam_length;
vector<vector<int>> ad;
vector<int> dist;
void dfs(int v, int p) {
if(p != -1) dist[v] = dist[p] + 1;
for(int u: ad[v]) {
if(u == p) continue;
dfs(u, v);
}
}
int send_message(int N, int i, int Pi) {
if(i == 1) {
ad.resize(N);
d1 = 0, d2 = 0;
diam_length = 0;
}
int new_diam = 0; // 0 if not new, 1 if new d1 2 if new d2
ad[i].push_back(Pi);
ad[Pi].push_back(i);
dist.assign(N, 0);
dfs(i, -1);
int mx_dist = *max_element(dist.begin(), dist.end());
if(mx_dist > diam_length) {
diam_length = mx_dist;
if(dist[d2] == mx_dist) {
new_diam = 1;
d1 = i;
}
else if(dist[d1] == mx_dist) {
new_diam = 2;
d2 = i;
}
}
if(i + 2*LOG < N) return 0;
if(i + 2*LOG == N) to_send_1 = d1, to_send_2 = d2;
int message = 1;
// message modulo 2 gives info on diam
// message/3 gives info on new diam
if(i + LOG < N) {
// send 1
int bit = N - LOG - i - 1;
message += (to_send_1 >> bit) & 1;
message += 2*new_diam;
}
else {
// send 2
int bit = N - i - 1;
message += (to_send_2 >> bit) & 1;
message += 2*new_diam;
}
cerr << to_send_1 << " " << to_send_2 << endl;
return message;
}
std::pair<int, int> longest_path(std::vector<int> S) {
int N = S.size();
int d1 = 0, d2 = 0;
for(int i=0; i<N; i++) S[i]--;
for(int bit=0; bit<LOG; bit++) {
int i1 = N - LOG - 1 - bit;
d1 += (S[i1] % 2) << bit;
int i2 = N - 1 - bit;
d2 += (S[i2] % 2) << bit;
}
for(int i=N-2*LOG; i<N; i++) {
if(S[i] < 0) continue;
if(S[i]/2 == 1) d1 = i;
if(S[i]/2 == 2) d2 = i;
}
return {d1, d2};
}
