#include "migrations.h"
#include <queue>
std::vector<std::vector<int>> nn;
std::vector<int> d(1, 0);
int max = 0;
std::vector<int> p1;
std::vector<int> p2;
int send_message(int N, int i, int Pi)
{
if (nn.size() == 0)
{
nn = std::vector<std::vector<int>>(N, std::vector<int>());
}
nn[i].push_back(Pi);
nn[Pi].push_back(i);
d.push_back(1 + d[Pi]);
max = std::max(max, d.back());
if (i == N - 1)
{
if (d[N - 1] == max)
return 1;
if (d[N - 2] == max)
return 2;
if (d[N - 3] == max)
return 3;
if (d[N - 4] == max)
return 4;
return 0;
}
else if (i >= N - 3)
{
if (p1.size() == 0)
{
p1.push_back(0);
p1.push_back(0);
for (int j = 4; j <= 24; j++)
{
if (max == d[N - j])
{
p1[0] = j / 5;
p1[1] = j % 5;
break;
}
}
}
return p1[i - (N - 3)];
}
else if (i >= N - 9)
{
if (p2.size() == 0)
{
for (int j = 0; j < 6; j++)
p2.push_back(0);
for (int j = i; j >= 0; j--)
if (d[j] == max)
{
for (int k = 5; k >= 0 && j > 0; k--)
{
p2[k] = j % 5;
j /= 5;
}
break;
}
}
return p2[i - (N - 9)];
}
else
{
return 0;
}
}
std::pair<int, int> longest_path(std::vector<int> S)
{
int n = S.size();
if (S[n - 1] != 0)
{
return {0, n - S[n - 1]};
}
if (S[n - 2] != 0 || S[n - 3] != 0)
{
return {0, n - (S[n - 3] * 5 + S[n - 2])};
}
int ans = 0;
for (int i = n - 9, k = 0; k < 6; i++, k++)
{
ans *= 5;
ans += S[i];
}
return {0, ans};
}
