#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> getbasep(int x, int p) {
vector<int> ans;
while (x) {
ans.push_back(x % p);
x /= p;
}
return ans;
}
int frombasep(vector<int>& v, int p) {
int x = 0, k = 1;
for (int i = 0; i < v.size(); i++) {
x += k * v[i];
k *= p;
}
return x;
}
const int MAXN = 1e5;
vector<int> adj[MAXN];
int A, B;
int Z = 14;
vector<int> Abase, Bbase;
int getfurthest(int node, int v) {
vector<int> dist(MAXN);
auto dfs = [&](int node, int par, auto& dfs) -> void {
for (int u : adj[node]) if (u != par) {
dist[u] = dist[node]+1;
dfs(u, node, dfs);
}
};
dfs(node, -1, dfs);
int furth = node;
for (int i = 0; i < MAXN; i++) if (dist[i] > dist[furth] || (dist[i] == dist[furth] && v == i)) furth = i;
return furth;
}
int send_message(int N, int i, int Pi) {
adj[Pi].push_back(i);
adj[i].push_back(Pi);
if (i < N - 2*Z) return 0;
else {
if (i == N - 2*Z) {
A = getfurthest(0, -1);
B = getfurthest(A, -1);
Abase = getbasep(A, 2);
while (Abase.size() < Z) Abase.push_back(0);
Bbase = getbasep(B, 2);
while (Bbase.size() < Z) Bbase.push_back(0);
}
if (i < N - Z) {
//we're returning A
int dig = Abase.back();
Abase.pop_back();
int AA = getfurthest(B, A);
if (AA != A) {
A = AA;
return 4;
}
else {
int BB = getfurthest(A, B);
if (BB != B) {
B = BB;
return dig+2;
}
else return dig;
}
} else {
//we're returning B
int dig = Bbase.back();
Bbase.pop_back();
int BB = getfurthest(A, B);
if (B != BB) {
B = BB;
return 4;
} else {
int AA = getfurthest(B, A);
if (A != AA) {
A = AA;
return dig+2;
} else return dig;
}
}
}
}
pair<int, int> longest_path(vector<int> S) {
int N = S.size();
int a=-1, b=-1;
vector<int> isbasea, isbaseb;
for (int i = 2*Z; i >= 1; i--) {
if (i > Z) {
if (S[N-i] == 4) a = N-i;
else if (S[N-i] > 1) b = N-i;
isbasea.push_back(S[N-i]%2);
} else {
if (S[N-i] == 4) b = N-i;
else if (S[N-i] > 1) a = N-i;
isbaseb.push_back(S[N-i]%2);
}
}
reverse(isbasea.begin(), isbasea.end());
reverse(isbaseb.begin(), isbaseb.end());
if (a == -1) a = frombasep(isbasea, 2);
if (b == -1) b = frombasep(isbaseb, 2);
return {a, b};
}
