#include "migrations.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#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());
// #define int long long
// #define int unsigned long long
// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>
// const ll mod = 1e9 + 7;
// const ll mod = 998244353;
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};
}
// int main() {
// int N;
// assert(1 == scanf("%d", &N));
// std::vector<int> P(N, 0);
// for (int i = 1; i < N; ++i) {
// assert(1 == scanf("%d", &P[i]));
// }
// std::vector<int> S(N, 0);
// for (int i = 1; i < N; ++i) {
// S[i] = send_message(N, i, P[i]);
// }
// for (int i = 1; i < N; ++i) {
// printf("%d%c", S[i], " \n"[i + 1 == N]);
// }
// auto [U, V] = longest_path(S);
// printf("%d %d\n", U, V);
// fclose(stdout);
// return 0;
// }
