#include <bits/stdc++.h>
using namespace std;
int p[10001];
vector<vector<int>> a;
vector<int> v;
void dfs(int u, int k, int cnt){
v[u] = cnt;
for(int e : a[u]) if(e != k) dfs(e, u, cnt + 1);
}
int vt[7];
pair<int,int> ml = {-1,-1};
int send_message(int N, int i, int Pi){
p[i] = Pi;
if(i >= N - 14 && i < N - 7){
a.assign(N + 1, {}); v.assign(N + 1, 0);
for(int j = 1; j <= N; j++) a[p[j]].push_back(j);
dfs(0, -1, 0);
int u = 0;
for(int j = 0; j <= N; j++) if(v[j] > v[u]) u = j;
dfs(u, -1, 0);
int vtx = u;
for(int j = 0; j <= N; j++) if(v[j] > v[vtx]) vtx = j;
int x = u, y = vtx;
if(x > y) swap(x, y);
if(i == N - 1 && ml.first != -1 && make_pair(x, y) != ml) return 4;
ml = make_pair(x, y);
int tmp = x;
for(int d = 6; d >= 0; --d){ vt[d] = tmp % 4; tmp /= 4; }
return vt[i - (N - 14)];
} else if(i >= N - 7){
a.assign(N + 1, {}); v.assign(N + 1, 0);
for(int j = 1; j <= N; j++) a[p[j]].push_back(j);
dfs(0, -1, 0);
int u = 0;
for(int j = 0; j <= N; j++) if(v[j] > v[u]) u = j;
dfs(u, -1, 0);
int vtx = u;
for(int j = 0; j <= N; j++) if(v[j] > v[vtx]) vtx = j;
int x = u, y = vtx;
if(x > y) swap(x, y);
if(i == N - 1 && ml.first != -1 && make_pair(x, y) != ml) return 4;
ml = make_pair(x, y);
int tmp = y;
for(int d = 6; d >= 0; --d){ vt[d] = tmp % 4; tmp /= 4; }
return vt[i - (N - 7)];
}
return 0;
}
pair<int,int> longest_path(vector<int> S){
int a1 = 0, a2 = 0;
for(int i = S.size() - 14; i < S.size() - 7; ++i){
if(S[i] == 4) return {0, i};
a1 = a1 * 4 + S[i];
}
for(int i = S.size() - 7; i < S.size(); ++i){
if(S[i] == 4) return {0, i};
a2 = a2 * 4 + S[i];
}
if(a1 > a2) swap(a1, a2);
return {a1, a2};
}
