#include "migrations.h"
#include<bits/stdc++.h>
using namespace std;
inline int getnum(int num, int b)
{
return (num >> (2*b)) & 3;
}
vector<int> ad[10005];
int h[10005], par[10005];
void update(int u, int Pu)
{
par[u] = Pu; h[u] = h[Pu] + 1;
}
int curnode = 0;
void update_diameter(int u)
{
if(h[u] > h[curnode]) curnode = u;
}
void brute(int l, int r)
{
for(int i = l; i <= r; i++) update_diameter(i);
}
int send_message(int n, int u, int Pu) {
//Subtask 1
n = u;
//[0, 9989]: nothing
//[9990, 9996]: decode node
//[9997, 9998]: decode node
//[9999]: decode node
update(n, Pu);
if(n <= 9989) return 0;
else if(n <= 9996){
int idx = n-9990;
if(idx == 0) brute(0, 9989);
return getnum(curnode, idx)+1;
}
else if(n <= 9998){
int idx = n-9997;
if(idx == 0) brute(9990, 9996);
int val = curnode;
if(curnode < 9990) val = 0;
else val = curnode - 9989;
return getnum(val, idx)+1;
}
else{
brute(9997, 9999);
int val = curnode;
if(curnode < 9997) val = 0;
else val = curnode - 9996;
return val + 1;
}
}
int read(vector<int> &S, int l, int r)
{
int ans = 0;
for(int i = l; i <= r; i++){
int idx = i-l;
ans += ((S[i]-1) << (idx * 2));
}
return ans;
}
pair<int, int> longest_path(vector<int> S) {
int u = read(S, 9990, 9996);
int add = read(S, 9997, 9998); if(add > 0) u = add + 9989;
add = read(S, 9999, 9999); if(add > 0) u = add + 9996;
return {0, u};
}
