#include "migrations.h"
#include<bits/stdc++.h>
using namespace std;
inline int getnum(int num, int b)
{
return (num >> (2*b)) & 3;
}
vector<int> ad[10005];
int h[10005], jump[10005][20];
void update(int u, int Pu)
{
jump[u][0] = Pu; h[u] = h[Pu] + 1;
for(int i = 1; i <= 14; i++) jump[u][i] = jump[jump[u][i-1]][i-1];
}
int lca(int u, int v)
{
if(u == 0 || v == 0) return 0;
if(u == v) return u;
if(h[u] < h[v]) swap(u, v);
for(int i = 14; i >= 0; i--) if(h[jump[u][i]] >= h[v]) u = jump[u][i];
if(u == v) return u;
for(int i = 14; i >= 0; i--) if(jump[u][i] != jump[v][i]){
u = jump[u][i]; v = jump[v][i];
}
return jump[u][0];
}
int dis(int u, int v)
{
return h[u] + h[v] - 2*h[lca(u, v)];
}
pair<int, int> find_diameter(int n)
{
for(int i = 0; i <= n; i++) ad[i].clear();
for(int i = 1; i <= n; i++){
int pi = jump[i][0];
ad[pi].push_back(i); ad[i].push_back(pi);
}
vector<int> dis(n+1);
fill(dis.begin(), dis.end(), 1e9); dis[0] = 0;
queue<int> w; w.push(0);
while(w.size() > 0){
int u = w.front(); w.pop();
for(int v : ad[u]) if(dis[v] > dis[u] + 1){
dis[v] = dis[u] + 1; w.push(v);
}
}
int maxnode = 0;
for(int i = 0; i <= n; i++) if(dis[maxnode] < dis[i]) maxnode = i;
fill(dis.begin(), dis.end(), 1e9); dis[maxnode] = 0; w.push(maxnode);
while(w.size() > 0){
int u = w.front(); w.pop();
for(int v : ad[u]) if(dis[v] > dis[u] + 1){
dis[v] = dis[u] + 1; w.push(v);
}
}
int maxnode2 = 0;
for(int i = 0; i <= n; i++) if(dis[maxnode2] < dis[i]) maxnode2 = i;
return {maxnode, maxnode2};
}
pair<int, int> cur_diameter;
bool re_diameter = 0;
void update_diameter(int u)
{
int cur = dis(cur_diameter.first, cur_diameter.second);
int x = dis(cur_diameter.first, u);
int y = dis(cur_diameter.second, u);
if(x >= y && x > cur) cur_diameter.second = u;
else if(y > x && y > cur) cur_diameter.first = u;
}
vector<pair<int, int>> all_cases;
void brute(int l, int r)
{
all_cases.clear();
all_cases.push_back(cur_diameter);
for(int i = l; i <= r; i++){
all_cases.push_back(make_pair(cur_diameter.first, i));
all_cases.push_back(make_pair(i, cur_diameter.second));
}
for(int i = l; i <= r; i++){
for(int j = i+1; j <= r; j++) all_cases.push_back(make_pair(i, j));
}
sort(all_cases.begin(), all_cases.end());
if(re_diameter == 1){
for(int i = l; i <= r; i++) update_diameter(i);
if(cur_diameter.first >= l && cur_diameter.second >= l){
if(cur_diameter.first > cur_diameter.second) swap(cur_diameter.first, cur_diameter.second);
}
}
}
int send_message(int n, int u, int Pu) {
re_diameter = 1;
n = u;
//[0, 9973]: nothing
//[9974, 9987]: current diameter
//[9988, 9992]: diameter for the last 14 bits
//[9993, 9995]: diameter for the last 5 bits
//[9996, 9997]: diameter for the last 3 bits
//[9998, 9999]:
if(n <= 9973){update(n, Pu); return 0;}
else if(n <= 9987){
int idx = n-9974;
if(idx == 0) cur_diameter = find_diameter(9973);
//cerr<<"A"<<cur_diameter.first<<" "<<cur_diameter.second<<endl;
update(n, Pu);
if(idx <= 6) return getnum(cur_diameter.first, idx) + 1;
else return getnum(cur_diameter.second, idx-7) + 1;
}
else if(n <= 9992){
int idx = n-9988;
if(idx == 0){
brute(9974, 9987);
//There should be 120 cases
//cerr<<"A"<<all_cases.size()<<endl;
}
update(n, Pu);
int p = lower_bound(all_cases.begin(), all_cases.end(), cur_diameter) - all_cases.begin();
return getnum(p, idx) + 1;
}
else if(n <= 9995){
int idx = n-9993;
if(idx == 0){
brute(9988, 9992);
//There should be 21 cases
//cerr<<"B"<<all_cases.size()<<endl;
}
update(n, Pu);
int p = lower_bound(all_cases.begin(), all_cases.end(), cur_diameter) - all_cases.begin();
return getnum(p, idx) + 1;
}
else if(n <= 9997){
int idx = n-9996;
if(idx == 0){
brute(9993, 9995);
//There should be 10 cases
//cerr<<"C"<<all_cases.size()<<endl;
}
update(n, Pu);
int p = lower_bound(all_cases.begin(), all_cases.end(), cur_diameter) - all_cases.begin();
return getnum(p, idx) + 1;
}
else if(n == 9998){
brute(9996, 9997);
//There should be 6 cases
int p = lower_bound(all_cases.begin(), all_cases.end(), cur_diameter) - all_cases.begin();
update(n, Pu);
return p+1; //Solve with Z <= 6
}
else{
update(n, Pu);
brute(9998, 9999);
//There should be 6 cases
int p = lower_bound(all_cases.begin(), all_cases.end(), cur_diameter) - all_cases.begin();
return p+1; //Solve with Z <= 6
}
}
int read(vector<int> &S, int l, int r)
{
int ans = 0;
for(int i = l; i <= r; i++){
int idx = i-l;
ans += ((S[i]-1) << (idx * 2));
}
return ans;
}
pair<int, int> longest_path(vector<int> S) {
re_diameter = 0;
cur_diameter = {read(S, 9974, 9980), read(S, 9981, 9987)};
brute(9974, 9987);
int data = read(S, 9988, 9992);
cur_diameter = all_cases[data];
brute(9988, 9992);
data = read(S, 9993, 9995);
cur_diameter = all_cases[data];
brute(9993, 9995);
data = read(S, 9996, 9997);
cur_diameter = all_cases[data];
brute(9996, 9997);
data = read(S, 9998, 9998);
cur_diameter = all_cases[data];
brute(9998, 9999);
data = read(S, 9999, 9999);
cur_diameter = all_cases[data];
return cur_diameter;
}
