#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 10004, m = 16;
vector<int> g[N];
int dfs(int x, int p, int y, int d)
{
if (x == y)
return d;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i];
if (h == p)
continue;
int dd = dfs(h, x, y, d + 1);
if (dd != -1)
return dd;
}
return -1;
}
int dist(int x, int y)
{
return dfs(x, x, y, 0);
}
int a, b;
int send_message(int n, int x, int p)
{
g[x].push_back(p);
g[p].push_back(x);
int d = dist(a, b);
int da = dist(x, a);
int db = dist(x, b);
if (x < n - 32)
{
if (da > db)
{
if (da > d)
{
b = x;
}
}
else
{
if (db > d)
{
a = x;
}
}
return 0;
}
if (x < n - 16)
{
if (da > db)
{
if (da > d)
{
b = x;
}
}
else
{
if (db > d)
{
a = x;
return 2;
}
}
if (a >= n - 32)
return 0;
int i = x - (n - 32);
if ((a & (1 << i)))
return 1;
return 0;
}
{
if (da > db)
{
if (da > d)
{
b = x;
return 2;
}
}
else
{
if (db > d)
{
a = x;
int i = x - (n - 16);
if ((b & (1 << i)))
return 3;
return 4;
}
}
if (b >= n - 16)
return 0;
int i = x - (n - 16);
if ((b & (1 << i)))
return 1;
return 0;
}
}
std::pair<int, int> longest_path(std::vector<int> S)
{
int n = sz(S);
int a = 0;
for (int x = n - 32; x < n - 16; ++x)
{
if (S[x] == 2)
a = x;
else
{
if (a < n - 32)
{
int i = x - (n - 32);
if (S[x] == 1)
a |= (1 << i);
}
}
}
int b = 0;
for (int x = n - 16; x < n; ++x)
{
if (S[x] == 2)
b = x;
else if (S[x] < 2)
{
if (b < n - 16)
{
int i = x - (n - 16);
if (S[x] == 1)
b |= (1 << i);
}
}
else
{
a = x;
if (b < n - 16)
{
int i = x - (n - 16);
if (S[x] == 3)
b |= (1 << i);
}
}
}
return m_p(a, b);
}
