#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> l4;
typedef pair<double, double> dd;
#define mp make_pair
#define pb push_back
#define mp3(a,b,c) mp(mp(a, b), c)
#define debug(x) cerr << #x << " = " << x << " "
typedef pair<double, double> dd;
typedef pair<double, dd> d3;
const double eps = 1e-9;
const int N = 10000;
const int M = 50;
const int F = 10000 - 50;
int h[N] = {0};
int maxi = 0;
int cur = 0;
int send_message(int N, int i, int Pi)
{
h[i] = h[Pi] + 1;
bool _new = false;
if (h[i] > h[maxi]) maxi = i, _new = true;
if (i < F) return 0;
if (i == F)
{
cur = maxi;
}
int msg = -1;
if (_new) msg = 3;
else if (cur <= 0)
{
msg = 2;
}
else
{
msg = cur&1;
cur >>= 1;
}
return msg;
}
std::pair<int,int> longest_path(std::vector<int> S)
{
assert(S.size() == N);
int i;
for (i = N-1; i >= F && S[i] == 2; --i);
if (S[i] == 3) return mp(0, i);
// cout << "i = " << i << endl;
int ret = 0;
while (i >= F)
{
ret = ret * 2 + S[i];
// cout << "ret met " << i << "," << S[i] << " and become " << ret << endl;
--i;
}
return mp(0, ret);
}
