#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 10005;
const int INF = 0x3f3f3f3f;
namespace FastIO {
const int SIZ = 1 << 20;
char ibuf[SIZ], *iS, *iT;
char obuf[SIZ], *oS = obuf, *oT = obuf + SIZ - 1;
inline char getch() {
return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZ, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
template <typename T>
inline void read(T& x) {
char c = getch();
x = 0;
bool f = 0;
while (!isdigit(c)) {
if (c == '-') f = 1;
c = getch();
}
while (isdigit(c)) {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getch();
}
if (f) x = -x;
}
inline void read(char& c) {
while ((c = getch()) <= 32);
}
inline void read(char* s) {
char c = getch();
while (c <= 32) c = getch();
while (c > 32) {
*s++ = c;
c = getch();
}
*s = '\0';
}
inline void read(string& s) {
s.clear();
char c = getch();
while (c <= 32) c = getch();
while (c > 32) {
s += c;
c = getch();
}
}
inline void flush() {
fwrite(obuf, 1, oS - obuf, stdout);
oS = obuf;
}
inline void putch(char x) {
*oS++ = x;
if (oS == oT) flush();
}
template <typename T>
inline void write(T x) {
if (x < 0) {
putch('-');
x = -x;
}
if (x > 9) write(x / 10);
putch(x % 10 + 48);
}
inline void write(const char* s) {
while (*s) putch(*s++);
}
inline void write(const string& s) {
for (char c : s) putch(c);
}
struct IO {
~IO() {
flush();
}
template <typename T>
IO& operator>>(T& x) {
read(x);
return *this;
}
template <typename T>
IO& operator<<(const T& x) {
write(x);
return *this;
}
} io;
} // namespace FastIO
using namespace FastIO;
using i128 = __int128;
using u128 = __uint128_t;
using ull = unsigned long long;
template <typename T>
constexpr std::make_unsigned_t<T> gcd(T a, T b) {
using U = std::make_unsigned_t<T>;
U m = a < 0 ? U(-a) : U(a);
U n = b < 0 ? U(-b) : U(b);
if (m == 0) return n;
if (n == 0) return m;
int i = __builtin_ctz(m);
m >>= i;
int j = __builtin_ctz(n);
n >>= j;
int k = min(i, j);
while (true) {
if (m > n) swap(m, n);
n -= m;
if (n == 0) return m << k;
n >>= __builtin_ctz(n);
}
}
inline int lg(int __n) {
return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n);
}
ll powmod(ll x, ll y, ll m = mod) {
ll res = 1;
while (y) {
if (y & 1) res = res * x % m;
y >>= 1;
x = x * x % m;
}
return res;
}
int dep[N], int fa[14][N];
int tu = 0, tv = 0, td = 0;
ll idv = 0;
int LCA(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for (int j = 0; j < 14; j++) {
if (d >> j & 1) u = fa[j][u];
}
if (u == v) return u;
for (int j = 13; j >= 0; j--) {
if (fa[j][u] != fa[j][v]) u = fa[j][u], v = fa[j][v];
}
return fa[0][u];
}
int get_dis(int u, int v) {
return dep[u] + dep[v] - 2 * dep[LCA(u, v)];
}
int send_message(int n, int i, int px) {
if (i == 1) {
dep[0] = 0;
for (int j = 0; j < 14; j++) fa[j][0] = 0;
tu = 0, tv = 0, td = 0;
idv = 0;
}
dep[i] = dep[px] + 1;
fa[0][i] = px;
for (int j = 1; j < 14; j++) fa[j][i] = fa[j - 1][fa[j - 1][i]];
int du = get_dis(i, tu);
int dv = get_dis(i, tv);
bool flg = 0;
int r = 0, mx = max(du, dv);
if (mx > td) {
flg = 1, td = mx;
if (du > dv) {
r = 1;
tv = i;
} else {
r = 2;
tu = i;
}
if (!tv && tu != 0) swap(tu, tv), r = 1;
}
if (i == n - 27) idv = tu * 10000ll + tv;
if (i >= n - 27) {
ll b = (idv >> (i - n + 27) & 1);
if (!flg) {
return b + 1;
} else {
if (r == 1) {
return b + 3;
} else {
return b + 5;
}
}
}
return 0;
}
pair<int, int> longest_path(vector<int> S) {
int n = S.size();
ll id = 0;
int wu = -1, wv = -1;
for (int i = n - 27; i < n; i++) {
if (!S[i]) continue;
ll b = ((S[i] - 1) & 1);
id |= (b << (i - n + 27));
if ((S[i] - 1) / 2 == 1) wv = i;
if ((S[i] - 1) / 2 == 2) wu = i;
}
if (wu == -1) wu = id / 10000;
if (wv == -1) wv = id % 10000;
return {wu, wv};
}
