#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int K = 14;
int n;
vector<int> parent;
vector<int> depth;
vector<vector<int>> adjlist;
vector<vector<int>> lift;
pair<int,int> relev_diameter;
pair<int,int> curr_diameter;
int curr_best_dist = -1;
void prv(vector<int> v) {
for (auto i:v) {
cout << i <<" ";
}
cout << endl;
}
int LCA(int u, int v) {
if (u==v) return u;
if (depth[u] > depth[v]) swap(u,v);
//u is now at a lower depth than v
for (int i=K-1; i>=0; i--) {
if (depth[v] >= depth[u] + (1LL<<i)) {
v = lift[v][i];
}
}
assert(depth[u] == depth[v]);
if (u==v) return u;
for (int i=K-1; i>=0; i--) {
if (lift[u][i] != lift[v][i]) {
u = lift[u][i];
v = lift[v][i];
}
}
u = parent[u];
v = parent[v];
assert(u==v);
return u;
}
int dist(int u, int v) {
return depth[u] + depth[v] - 2 * depth[LCA(u, v)];
}
vector<int> base(int n, int base, int length) {
vector<int> res;
for (int i=0; i<length; i++) {
res.push_back(n%base);
n /= base;
}
reverse(res.begin(), res.end());
return res;
}
int antibase(vector<int> based, int base) {
int su = 0;
for (int i=0; i<based.size(); i++) {
su += based[i];
if (i+1 != based.size()) su *= base;
}
return su;
}
pair<int,int> diameter;
signed send_message(signed N, signed site, signed Pi) {
n=N;
if (site==1) {
parent = vector<int>(N, -1);
parent[0] = 0; //careful!
depth = vector<int>(N, 0);
adjlist = vector<vector<int>>(N);
lift = vector<vector<int>>(N, vector<int>(K, -1));
for (int i=0; i<K; i++) lift[0][i] = 0;
}
parent[site] = Pi;
lift[site][0] = parent[site];
depth[site] = depth[parent[site]] + 1;
adjlist[site].push_back(parent[site]);
adjlist[parent[site]].push_back(site);
for (int i=1; i<K; i++) {
lift[site][i] = lift[lift[site][i-1]][i-1];
//cout << i <<" " << site <<" " << depth[site] <<" " << " " << depth[lift[site][i]] << " " << lift[site][i] << endl;
assert(depth[lift[site][i]] <= depth[site]);
assert(depth[lift[site][i]] >= depth[site] - (1LL<<i));
if (lift[site][i] != 0) {
assert(depth[lift[site][i]] == depth[site] - (1LL<<i));
}
}
if (site<N-28) {
return 0;
}
//cout << "CURRENTLY PROCESSING " << site <<" " << curr_best_dist << " " << curr_diameter.first <<" " << curr_diameter.second << endl;
if (site == N-28) {
int r = site+1;
vector<int> indices(r); iota(indices.begin(), indices.end(), (int)0);
sort(indices.begin(), indices.end(), [&](const int u, const int v) {
return depth[u] < depth[v];
});
int furthest = indices.back();
vector<int> furthest_distances(r); for (int i=0; i<r; i++) furthest_distances[i] = dist(furthest, i);
sort(indices.begin(), indices.end(), [&](const int u, const int v) {
return furthest_distances[u] < furthest_distances[v];
});
//cout << "SITE " << site << "FURTHEST " << furthest << endl;
//prv(furthest_distances);
diameter = {furthest, indices.back()};
int dist = furthest_distances[indices.back()];
if (diameter.first > diameter.second) diameter = {diameter.second, diameter.first};
relev_diameter = diameter;
curr_best_dist = dist;
}
if (site <= N-15 && site >= N-28) {
//so 28 to 15
//28 to 22 is the 1st number
//21 to 15 is the 2nd number
int n1 = relev_diameter.first;
int n2 = relev_diameter.second; //keep the order of the parts consistent
curr_diameter = relev_diameter;
vector<int> first_number = base(n1, 4, 7);
vector<int> second_number = base(n2, 4, 7);
if (site < N-21) {
return first_number[site-(N-28)];
}
else {
return second_number[site-(N-21)];
}
}
//now we're in the last 14 indices
int ind1 = curr_diameter.first;
int ind2 = curr_diameter.second;
int c = N - (2*(N-site));
int d = c + 1;
int r = d + 1;
//cout << "AIMING "<< "PREV " << ind1 <<" " << ind2 <<" NEW CANDIDATES " << c << " " << d << endl;
//we need to check if any of these have superseded the current diameter
//or if they together form a better diameter
vector<int> dist1(r); for (int i=0; i<r; i++) dist1[i] = dist(ind1, i);
vector<int> dist2(r); for (int i=0; i<r; i++) dist2[i] = dist(ind2, i);
vector<int> distc(r); for (int i=0; i<r; i++) distc[i] = dist(c, i);
vector<int> distd(r); for (int i=0; i<r; i++) distd[i] = dist(d, i);
assert(distc[d] == distd[c]);
assert(dist1[ind2] == dist2[ind1]);
//cout << r <<" "<< c <<" " << d << endl;
vector<int> message_pots = {curr_best_dist, dist2[c], dist2[d], dist1[c], dist1[d], distc[d]};
int maximum = *max_element(message_pots.begin(), message_pots.end());
//cout << "TES " << maximum <<" " << *max_element(dist1.begin(), dist1.end()) << endl;
assert(maximum >= *max_element(dist1.begin(), dist1.end()));
curr_best_dist = maximum;
//int relev_index = -1;
for (int i=0; i<6; i++) {
if (message_pots[i] == maximum) {
if (i==5) {
curr_diameter = {c, d};
}
else if (i==1) {
curr_diameter = {c, curr_diameter.second};
}
else if (i==3) {
curr_diameter = {curr_diameter.first, c};
}
else if (i==2) {
curr_diameter = {d, curr_diameter.second};
}
else if (i==4) {
curr_diameter = {curr_diameter.first, d};
}
return i;
}
}
//if (site==5) cout << "LC" <<" " << LCA(5,1) << endl;
//if (N-27 <= site && site <= N-)
assert(false);
}
std::pair<signed, signed> longest_path(std::vector<signed> S) {
int N = S.size();
//cout << N << endl;
vector<int> first_number(S.begin()+(N-28), S.begin()+(N-21));
assert(first_number.size() == 7);
vector<int> second_number(S.begin()+(N-21), S.begin()+(N-14));
assert(second_number.size() == 7);
//prv(first_number);
//prv(second_number);
int real_n1 = antibase(first_number, 4);
int real_n2 = antibase(second_number, 4);
pair<int,int> curdiam = {real_n1, real_n2};
for (int i=N-14; i<N; i++) {
int ind1 = N - (2*(N-i));
int ind2 = ind1 + 1;
if (S[i]==5) {
curdiam = {ind1, ind2};
}
else if (S[i]==1) {
curdiam = {ind1, curdiam.second};
}
else if (S[i]==3) {
curdiam = {curdiam.first, ind1};
}
else if (S[i]==2) {
curdiam = {ind2, curdiam.second};
}
else if (S[i]==4) {
curdiam = {curdiam.first, ind2};
}
}
return {curdiam.first, curdiam.second};
}
