#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
const int MAXN = 1e4;
bool init = 0, preg[MAXN];
ll dist[MAXN], ma = 0, nod = 0, prog[MAXN];
void ini()
{
init = 1;
ll i, cant = 1;
preg[MAXN - 1] = 1;
for (i = MAXN - 1 - 2; i > 0; i)
{
preg[i] = 1;
cant = (cant + 1) * 2;
i -= cant;
i--;
}
}
ll ant = -1, a = 0, b = 0, nMa = 0, maD = 0;
vector<ll> grafo[MAXN];
ll vis[MAXN];
void dfs(ll nod, ll dis)
{
vis[nod] = 1;
if (dis > maD)
{
maD = dis;
nMa = nod;
}
else if (dis == maD)
nMa = max(nMa, nod);
for (auto k : grafo[nod])
{
if (vis[k])
continue;
dfs(k, dis + 1);
}
}
int send_message(int N, int i, int Pi)
{
if (init == 0)
ini();
grafo[i].pb(Pi);
grafo[Pi].pb(i);
ll auxA, auxB, dis;
if (preg[i])
{
memset(vis, 0, sizeof(vis));
auxA = a;
auxB = b;
maD = 0;
nMa = b;
dfs(a, 0);
b = nMa;
memset(vis, 0, sizeof(vis));
maD = 0;
nMa = a;
dfs(b, 0);
a = nMa;
memset(vis, 0, sizeof(vis));
maD = 0;
nMa = b;
dfs(a, 0);
b = nMa;
if (a < b)
swap(a, b);
if (auxA != a)
{
ll x = abs(i - a) + 1, j = i;
while (x > 2)
{
x -= 2;
j++;
}
prog[j] = x;
}
if (auxB != b)
{
ll x = abs(i - b) + 1, j = i;
while (x > 2)
{
x -= 2;
j++;
}
if (prog[j] != 0)
{
prog[j] += 2;
}
else
prog[j] = x;
}
}
if (prog[i] > 0)
return prog[i];
return 0;
}
pair<ll, ll> calc(ll i, vector<int> &s)
{
pair<ll, ll> p = {-1, -1};
ll ap = 0, dis = -1, act = 0, in = i;
for (i; i < MAXN; i++)
{
if (preg[i])
ap++;
if (ap > 1)
break;
if (s[i] != 0)
{
if (s[i] > 2)
{
dis = (act + 1) - 1;
p.fr = in - dis;
dis = (act + 2) - 1;
p.se = in - dis;
}
else
{
act = act + s[i];
dis = act - 1;
if (p.fr == -1)
p.fr = in - dis;
else
p.se = in - dis;
act = act - s[i];
}
}
act = act + 2;
}
return p;
}
std::pair<int, int> longest_path(std::vector<int> S)
{
pair<ll, ll> p = {0, 0}, a;
ll i;
ini();
for (i = 0; i < MAXN; i++)
{
if (preg[i])
{
a = calc(i, S);
if (a.fr != -1)
p.fr = a.fr;
if (a.se != -1)
p.se = a.se;
}
}
pair<int, int> an = p;
return an;
}
