#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
const int big_n = 1e4;
const int bitcnt_1 = 21;
const int bitcnt_2 = 14;
int n;
vector<int> par;
vector<vector<int> > graph;
vector<vector<int> > children;
int A, B;
int diam;
// maybe bigger is not enough, first part has to be bigger as well?
// so that negative .se; etc.
pii dfs_furthest(int cur, int pr) {
pii res = mp(0, cur);
for(int nei : graph[cur]) {
if(nei != pr) {
pii this_res = dfs_furthest(nei, cur);
this_res.fi++;
res = max(res, this_res);
}
}
return res;
}
int dist(int cur, int pr, int goal) {
if(cur == goal) {
return 0;
}
int res = 1e5;
for(int nei : graph[cur]) {
if(nei != pr) {
res = min(res, dist(nei, cur, goal) + 1);
}
}
return res;
}
void init() {
par.assign(big_n, -1);
graph.resize(big_n);
children.resize(big_n);
}
signed send_message(signed N, signed i, signed Pi) {
n = i + 1;
if(n == 2) {
init();
}
par[i] = Pi;
graph[i].pb(par[i]);
graph[par[i]].pb(i);
children[par[i]].pb(i);
int pos = bitcnt_1 - (big_n - n + 1);
if(pos < 0) {
return 0;
}
if(pos == 0) {
pii deepest = dfs_furthest(0, -1);
A = deepest.se;
deepest = dfs_furthest(A, -1);
B = deepest.se;
diam = deepest.fi;
}
if(pos < 7) {
pii deepest = dfs_furthest(i, -1);
if(deepest.fi > diam && dist(i, -1, A) <= diam) {
A = i;
diam++;
return 4;
} else {
if(deepest.fi > diam) {
diam++;
}
return (A >> (2 * pos)) & 3;
}
}
pos -= 7;
pii deepest = dfs_furthest(i, -1);
if(deepest.fi <= diam) {
return (B >> pos) & 1;
}
if(dist(i, -1, A) <= diam) {
// A valtozik
A = i;
diam++;
return ((B >> pos) & 1) + 2;
} else {
// B valtozik
B = i;
diam++;
return 4;
}
/*if (i == 1)
return 10;
else if (i == 2)
return 20;
else if (i == 3)
return 30;
else
return 0;*/
}
pair<signed, signed> longest_path(vector<signed> S) {
int A = 0, B = 0;
bool A_set = false, B_set = false;
for(int i = big_n - bitcnt_1; i < big_n - bitcnt_2; i++) {
if(S[i] == 4) {
A_set = true;
A = i;
}
}
for(int i = big_n - bitcnt_2; i < big_n; i++) {
if(S[i] >= 2 && S[i] <= 3) {
A_set = true;
A = i;
}
}
if(!A_set) {
int pos = 1;
for(int i = big_n - bitcnt_1; i < big_n - bitcnt_2; i++) {
A += pos * S[i];
pos *= 4;
}
}
for(int i = big_n - bitcnt_2; i < big_n; i++) {
if(S[i] == 4) {
B_set = true;
B = i;
}
}
if(!B_set) {
int pos = 1;
for(int i = big_n - bitcnt_2; i < big_n; i++) {
B += pos * (S[i] % 2);
pos *= 2;
}
}
/*for(int i = 0; i < 6; i++) {
for(int j = 0; j < 6; j++) {
cout << dist(i, -1, j) << " ";
}
cout << "\n";
}*/
//cout << overall_best.fi << " " << overall_best.se << "\n";
return mp(A, B);
//return {0, 3};
}
