#include "migrations.h"
#include <queue>
#include <cstdio>
#include <map>
#include <stdexcept>
#include <algorithm>
std::vector<std::vector<int>> nn;
int p1[32];
int p2[32];
int p3[32];
int p4[32];
int d1[10001];
int d2[10001];
int d3[10001];
std::map<int, int> lmap;
std::map<int, int> rmap;
void ClearMap(std::map<int, int> &m, int i)
{
m.clear();
m[i] = 0;
}
void AddMap(std::map<int, int> &m, int pi, int i)
{
auto it = m.find(pi);
if (it != m.end())
{
m[i] = 1 + it->second;
}
}
int GetMap(std::map<int, int> &m)
{
int max = -1;
int index = -1;
for (const auto &pair : m)
{
if (max < pair.second)
{
max = pair.second;
index = pair.first;
}
else if (max == pair.second)
{
if (index < pair.first)
index = pair.first;
}
}
return index;
}
int left = -1, right = -1;
void pack4(int to, int p[])
{
}
void pack5(int to, int p[], int count)
{
for (int i = count - 1; i >= 0; i--)
{
p[i] = to % 5;
to /= 5;
}
//if (to > 0)
// throw std::runtime_error("A runtime error occurred.");
}
int unpack5(std::vector<int> &s, int index, int count)
{
int ans = 0;
for (int i = index, k = 0; k < count; i++, k++)
{
ans *= 5;
ans += s[i];
}
return ans;
}
void dfs(int to, int from, int d[])
{
d[to] = 1 + d[from];
for (int j : nn[to])
{
if (j == from)
continue;
dfs(j, to, d);
}
}
int n;
std::pair<int, int> Step(int i)
{
d1[i] = -1;
dfs(i, i, d1);
int m1 = 0;
for (int j = 0; j <= n; j++)
if (d1[m1] <= d1[j])
m1 = j;
d2[m1] = -1;
dfs(m1, m1, d2);
int m2 = 0;
for (int j = 0; j <= n; j++)
if (d2[m2] <= d2[j])
m2 = j;
// printf("%d %d\n", m2, m1);
return std::make_pair(m2, m1);
}
int send_message(int N, int i, int Pi)
{
n = i;
if (nn.size() == 0)
{
nn = std::vector<std::vector<int>>(N, std::vector<int>());
}
nn[i].push_back(Pi);
nn[Pi].push_back(i);
AddMap(lmap, Pi, i);
AddMap(rmap, Pi, i);
if (i == N - 1)
{
auto p = Step(GetMap(lmap));
if (p.first == i)
{
if (p.second == i - 1)
{
return 3;
}
else
{
return 4;
}
}
else
{
if (p.second == i)
{
return 1;
}
else if (p.second == i - 1)
{
return 2;
}
}
}
else if (i == N - 2)
{
auto p = Step(GetMap(rmap));
if (p.second == left)
{
return 0;
}
else
{
left = p.second;
ClearMap(lmap, left);
return i + 1 - left;
}
}
else if (i == N - 3)
{
auto p = Step(GetMap(lmap));
if (p.second == right)
{
return 0;
}
else
{
right = p.second;
ClearMap(rmap, right);
return i + 1 - right;
}
}
else if (i >= N - 5)
{
if (i == N - 5)
{
auto p = Step(GetMap(rmap));
if (p.second == left)
{
pack5(0, p1, 2);
}
else
{
left = p.second;
ClearMap(lmap, left);
pack5(i + 1 - left, p1, 2);
}
}
return p1[i - (N - 5)];
}
else if (i >= N - 7)
{
if (i == N - 7)
{
auto p = Step(GetMap(lmap));
if (p.second == right)
{
pack5(0, p2, 2);
}
else
{
right = p.second;
ClearMap(rmap, right);
pack5(i + 1 - right, p2, 2);
}
}
return p2[i - (N - 7)];
}
else if (i >= N - 13)
{
if (i == N - 13)
{
auto p = Step(GetMap(rmap));
left = p.second;
ClearMap(lmap, left);
pack5(left, p3, 6);
}
return p3[i - (N - 13)];
}
else if (i >= N - 19)
{
if (i == N - 19)
{
auto p = Step(0);
right = std::max(p.first, p.second);
ClearMap(rmap, right);
pack5(right, p4, 6);
}
return p4[i - (N - 19)];
}
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S)
{
n = S.size();
int l = -1, r = -1;
for (int i = n - 1; i >= 0; i--)
{
if (i == n - 1)
{
if (S[i] == 4)
{
l = i;
}
else if (S[i] == 3)
{
r = i - 1;
}
else if (S[i] == 2)
{
r = i - 1;
}
else if (S[i] == 1)
{
r = i;
}
}
if (i == n - 2 && l == -1)
{
if (S[i] != 0)
{
l = i + 1 - S[i];
}
}
if (i == n - 3 && r == -1)
{
if (S[i] != 0)
{
r = i + 1 - S[i];
}
}
if (i == n - 5 && l == -1)
{
int p = unpack5(S, i, 2);
if (p != 0)
{
l = i + 1 - p;
}
}
if (i == n - 7 && r == -1)
{
int p = unpack5(S, i, 2);
if (p != 0)
{
r = i + 1 - p;
}
}
if (i == n - 13 && l == -1)
{
l = unpack5(S, i, 6);
}
if (i == n - 19 && r == -1)
{
r = unpack5(S, i, 6);
}
// printf("%d %d %d\n", i, l, r);
if (l != -1 && r != -1)
return {l, r};
}
return {0, 1};
}
