#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
vector<int> p;
int find(){
int n = (int) p.size();
vector<int> g[n];
for (int i = 1; i < n; i++){
g[p[i]].pb(i);
g[i].pb(p[i]);
}
function<pii(int, int)> dfs = [&](int v, int pr){
pii out = {0, v};
for (int i: g[v]){
if (i == pr) continue;
auto [d, x] = dfs(i, v);
out = max(out, {d + 1, x});
}
return out;
};
auto [d, x1] = dfs(0, 0);
return x1;
}
vector<int> q;
int f;
int send_message(int n, int i, int k){
if (i == 1) p.pb(0);
p.pb(k);
if (i < (n - 9)) return 0;
if (i == (n - 9)){
f = find();
for (int w = 0; w < 7; w++){
q.pb(f % 4);
f /= 4;
}
}
if (i == (n - 2)){
f = find();
if ((n - 8) <= f && f <= (n - 5)){
return (f - (n - 8));
}
return 4;
}
else if (i == (n - 1)){
f = find();
if ((n - 4) <= f && f <= (n - 1)){
return (f - (n - 4));
}
return 4;
}
int r = q.back(); q.pop_back();
return r;
}
pii longest_path(vector<int> s){
int n = (int) s.size();
int k = 0, pw = 1;
for (int i = n - 3; i >= n - 9; i--){
k += s[i] * pw;
pw *= 4;
}
if (s[n - 2] != 4){
k = (n - 8) + s[n - 2];
}
if (s[n - 1] != 4){
k = (n - 4) + s[n - 1];
}
return {0, k};
}
