#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], fa[14][N];
int tu = 0, tv = 0, td = 0;
int mx0 = 0, ff0 = 0;
int pt = 0;
ll as = 0, bs = 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;
mx0 = 0, ff0 = 0, pt = 0;
as = 0, bs = 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 d0 = get_dis(i, 0);
bool flg0 = 0;
if (d0 > mx0) {
flg0 = 1;
mx0 = d0, ff0 = i;
}
int du = get_dis(i, tu), dv = get_dis(i, tv);
bool ok = 0;
int r = 0;
int mx = max(du, dv);
if (mx > td) {
ok = 1, td = mx;
if (du > dv) {
r = 1, tv = i;
} else {
r = 2, tu = i;
}
}
if (i == n - 28) {
if (!tu || !tv) {
pt = 1;
} else {
pt = 2;
as = min(tu, tv), bs = max(tu, tv);
idv = as * 10000ll + bs;
}
}
if (i == n - 15 && pt == 1) bs = ff0;
if (pt == 2 && i >= n - 27) {
int bit = i - n + 27;
return (ok ? r : 0) * 2 + (idv >> bit & 1) + 1;
}
if (pt == 1 && i >= n - 14) {
int bit = i - n + 14;
return (flg0 ? 1 : 0) * 2 + (bs >> bit & 1) + 1;
}
return 0;
}
pair<int, int> longest_path(vector<int> S) {
int n = S.size();
bool flg2 = 0;
for (int i = n - 27; i < n - 14; i++) {
if (S[i] > 0) flg2 = 1;
}
if (flg2) {
ll id = 0;
for (int i = n - 27; i < n; i++) {
int d = ((S[i] - 1) & 1);
id |= ((ll)d << (i - n + 27));
}
int wu = id / 10000, wv = id % 10000;
for (int i = n - 27; i < n; i++) {
int val = S[i] - 1;
int u = val / 2;
if (u == 1) wv = i;
if (u == 2) wu = i;
}
return {wu, wv};
} else {
int wv = 0;
for (int i = n - 14; i < n; i++) {
int d = ((S[i] - 1) & 1);
wv |= (d << (i - n + 14));
}
for (int i = n - 14; i < n; i++) {
int u = (S[i] - 1) / 2;
if (u == 1) wv = i;
}
return {0, wv};
}
}
