#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;
deque<pair<int,int>> diameters;
deque<int> lag_queue;
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;
}
//find any diameter
//say that the first r of the n vertices are active at this point
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()};
if (diameter.first > diameter.second) diameter = {diameter.second, diameter.first};
diameters.push_back(diameter); //first diameter is for index N-28, and the last is for index N-1
if (site < N-14) {
//so 28 to 15
//28 to 22 is the 1st number
//21 to 15 is the 2nd number
int n1 = diameters[0].first;
int n2 = diameters[0].second; //keep the order of the parts consistent
vector<int> first_number = base(n1, 4, 7);
vector<int> second_number = base(n2, 4, 7);
lag_queue.push_back(site);
if (site < N-21) {
return first_number[site-(N-28)];
}
else {
return second_number[site-(N-21)];
}
}
else {
lag_queue.push_back(site);
assert(lag_queue.size());
int a,b;
int message = 0;
a = lag_queue.front(); lag_queue.pop_front(); b = lag_queue.front(), lag_queue.pop_front();
//int n1 = diameters[0].first;
//int n2 = diameters[0].second;
int r1 = diameters[0].first;
int r2 = diameters[0].second;
if ((r1 == a && r2 == b) || (r1 == b && r2 == a)) {
message = 5; //note here, we sort the values always
}
else if (r1 == a) {
message = 1;
}
else if (r2 == a) {
message = 2;
}
else if (r1 == b) {
message = 3;
}
else if (r2 == b) {
message = 4;
}
else {
message = 0;
}
diameters.push_front(diameter);
return message;
}
//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};
}
