#include "bits/stdc++.h"
#include "migrations.h"
using namespace std;
int n = 1e4;
vector<vector<int>> p(n, vector<int>(20, -1));
vector<int> d(n), x(n), y(n);
int a, b;
int C(int n, int k)
{
int res = 1;
for (int i = 1; i <= k; i++)
res = res * (n - i + 1) / i;
return res;
}
vector<int> encode(int k, int r, int g)
{
vector<int> ans(r);
int left = g;
for (int i = 0; i < r; i++)
{
int x = C(r - i - 1, left);
if (x <= k)
k -= x, left--, ans[i] = 1;
}
return ans;
}
int decode(vector<int> v, int r, int g)
{
int k = 0;
int left = g;
for (int i = 0; i < r; i++)
if (v[i])
k += C(r - i - 1, left--);
return k;
}
vector<int> chosen;
int kup(int a, int k)
{
for (int i = 19; i >= 0; i--)
{
if ((k >> i) & 1)
a = p[a][i];
if (a == -1)
return -1;
}
return a;
}
int lca(int a, int b)
{
if (d[a] > d[b])
swap(a, b);
b = kup(b, d[b] - d[a]);
if (a == b)
return a;
for (int i = 19; i >= 0; i--)
if (p[a][i] != p[b][i])
a = p[a][i], b = p[b][i];
return p[a][0];
}
int dist(int a, int b)
{
return d[a] + d[b] - 2 * d[lca(a, b)];
}
int send_message(int N, int i, int Pi)
{
y[i] = y[i - 1];
x[i] = x[i - 1];
p[i][0] = Pi;
d[i] = d[Pi] + 1;
for (int j = 1; j < 20; j++)
if (p[i][j - 1] != -1)
p[i][j] = p[p[i][j - 1]][j - 1];
if (dist(i, x[i]) > dist(x[i], y[i]))
y[i] = i;
else if (dist(i, y[i]) > dist(x[i], y[i]))
x[i] = i;
// 60 3 3 1 1
// y x _
// _ y _
// _ x y
// y _ x
// _ y x
if (i < N - 68)
return 0;
if (i == N - 68)
{
b = x[i] + y[i] * n;
chosen = encode(b / 256, 60, 4);
b %= 256;
}
if (i < N - 8)
{
if (chosen[i - (N - 68)])
{
int ret = b % 4 + 1;
b /= 4;
return ret;
}
return 0;
}
if (i == N - 8)
{
b = N - 68;
while (x[b] != x[i])
b++;
b -= N - 68;
}
if (i < N - 5)
{
if (x[i] != x[i - 1])
return 0;
int ret = b % 4 + 1;
b /= 4;
return ret;
}
if (i == N - 5)
{
b = N - 68;
while (y[b] != y[i])
b++;
b -= N - 68;
}
if (i < N - 2)
{
if (y[i] != y[i - 1])
return 0;
int ret = b % 4 + 1;
b /= 4;
return ret;
}
if (i == N - 2)
{
b = N - 6;
while (x[b] != x[i])
b++;
b -= N - 6;
return b;
}
if (i == N - 1)
{
if (x[i] == x[i - 1])
{
if (y[i] == y[i - 2])
return 0;
if (y[i] == y[i - 1])
return 1;
return 2;
}
if (y[i] == y[i - 2])
return 3;
return 4;
}
return 0;
}
pair<int, int> longest_path(vector<int> S)
{
int b, mult;
pair<int, int> ans = {0, 0};
vector<int> v;
b = 0, mult = 1;
for (int i = n - 68; i < n - 8; i++)
v.push_back(S[i]);
ans.first = decode(v, 60, 4) * 256;
for (int i = 0; i < 60; i++)
if (v[i])
ans.first += (v[i] - 1) * mult, mult *= 4;
ans.second = ans.first / n;
ans.first %= n;
b = 0, mult = 1;
for (int i = n - 8; i < n - 5; i++)
{
b += (S[i] - 1) * mult;
mult *= 4;
if (S[i] == 0)
ans.first = i, b = -1e4;
}
if (b > 0)
ans.first = n - 68 + b;
b = 0;
mult = 1;
for (int i = n - 5; i < n - 2; i++)
{
b += (S[i] - 1) * mult;
mult *= 4;
if (S[i] == 0)
ans.second = i, b = -1e4;
}
if (b > 0)
ans.second = n - 68 + b;
if (S[n - 2])
ans.first = n - 6 + S[n - 2];
if (S[n - 1] == 1)
ans.second = n - 2;
if (S[n - 1] == 2)
ans.second = n - 1;
if (S[n - 1] == 3)
ans.first = n - 1;
if (S[n - 1] == 4)
ans.first = n - 1, ans.second = n - 2;
return ans;
}
