#include "migrations.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());
const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 10005;
vector<int> g[maxN];
int dist[maxN], x, y = 1;
int bfs(int x, int y) {
for (int i = 0; i < maxN; i++) dist[i] = inf;
queue<int> q; q.push(x); dist[x] = 0;
while (!q.empty()) {
int v = q.front(); q.pop();
for (int u : g[v]) {
if (dist[u] == inf) {
dist[u] = dist[v] + 1; q.push(u);
}
}
} return dist[y];
}
int send_message(int n, int i, int pi) {
g[pi].pb(i); g[i].pb(pi);
if (i < n - 21) {
if (bfs(i, x) > bfs(x, y)) y = i;
if (bfs(i, y) > bfs(x, y)) x = i;
return 0;
}
if (i < n - 14) {
if (bfs(i, x) > bfs(x, y)) {
y = x; x = i; return 4;
}
if (bfs(i, y) > bfs(x, y)) {
x = i; return 4;
}
int tmp = x, pos = n - i - 15;
while (pos--) tmp /= 4;
return (tmp % 4);
}
int tmp = y, pos = n - i - 1;
while (pos--) tmp /= 2;
if (bfs(i, x) > bfs(x, y)) {
y = i; return 0;
}
if (bfs(i, y) > bfs(x, y)) {
x = i; return tmp % 2 + 1;
}
return tmp % 2 + 3;
}
pair<int, int> longest_path(vector<int> s) {
int x = 0, y = 0, n = s.size();
for (int i = 1; i < n; i++) {
if (i < n - 21) continue;
if (i < n - 14) {
if (s[i] == 4) x = i;
else {
int tmp = x, pos = n - i - 15, cur = 1;
while (pos--) tmp /= 4, cur *= 4;
x = x - (tmp % 4) * cur + s[i] * cur;
} continue;
}
if (s[i] == 0) y = i;
else if (s[i] <= 2) {
x = i;
int tmp = y, pos = n - i - 1, cur = 1;
while (pos--) tmp /= 2, cur *= 2;
y = y - (tmp % 2) * cur + (s[i] - 1) * cur;
} else {
int tmp = y, pos = n - i - 1, cur = 1;
while (pos--) tmp /= 2, cur *= 2;
y = y - (tmp % 2) * cur + (s[i] - 3) * cur;
}
}
return {x, y};
}
