#include <bits/stdc++.h>
std::vector<std::vector<int>> adj;
int prev_max_idx = 0;
int send_message(int N, int i, int Pi) {
if (adj.empty()) {
adj.resize(N);
}
adj[i].push_back(Pi);
adj[Pi].push_back(i);
std::vector<int> d(N);
auto dfs = [&](auto &&self, int u, int p) -> void {
for (int &i : adj[u]) {
if (i != p) {
d[i] = d[u] + 1;
self(self, i, u);
}
}
};
dfs(dfs, 0, -1);
int it = std::max_element(d.begin(), d.end()) - d.begin();
if (d[it] > d[prev_max_idx]) {
prev_max_idx = it;
} else if (d[it] == d[prev_max_idx]) {
it = prev_max_idx;
}
if (i < N - 9) {
return 0;
}
if (i == it) {
return 4;
}
int ans = it;
for (int j = N - 9; j < i; ++j) {
ans /= 3;
}
return ans % 3 + 1;
}
std::pair<int, int> longest_path(std::vector<int> S) {
const int n = S.size();
for (int i = 1; i <= 9; ++i) {
if (S[n - i] == 4) {
return {0, n - i};
}
}
int ans = 0;
for (int pow = 1, i = 9; i >= 1; --i, pow *= 3) {
ans += (S[n - i] - 1) * pow;
}
return {0, ans};
}
