#include <bits/stdc++.h>
#include "migrations.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(v) v.begin(), v.end()
constexpr ll inf = 1ll << 62ll;
#define SEED 3742435
mt19937 mt(SEED);
ll _ = 0;
ll n__;
vector<ll> p__;
vector<ll> depth__;
ll mx_id_1__ = 0, mx_id_2__ = 0;
queue<ll> seq__;
int prev_jam__ = 0;
ll sz__ = 0;
vector<vector<ll>> jmp__;
void calc_seq(ll i1, ll i2) {
seq__ = queue<ll>();
ll t = i1 * n__ + i2;
for (ll mask = 1; mask < n__ * n__; mask *= 2) {
seq__.push((t / mask) & 1);
}
}
void update_jmp(ll i) {
jmp__[i][0] = p__[i];
for (ll j = 1; j < 20; j++) {
if (jmp__[i][j-1] < 0) break;
jmp__[i][j] = jmp__[jmp__[i][j-1]][j-1];
}
}
ll lca_dist(ll i, ll j) {
if (depth__[i] > depth__[j]) swap(i, j);
ll res = depth__[j] - depth__[i];
for (ll k = 20-1; k >= 0; k--) {
if (jmp__[j][k] >= 0 && depth__[jmp__[j][k]] >= depth__[i]) j = jmp__[j][k];
}
if (i == j) return res;
for (ll k = 20-1; k >= 0; k--) {
if (jmp__[i][k] < 0) continue;
if (jmp__[i][k] != jmp__[j][k]) {
i = jmp__[i][k];
j = jmp__[j][k];
res += 2 * (1 << k);
}
}
return res + 2;
}
ll encrypt_random(ll nxt) {
ll rng = mt() % 5;
nxt -= rng;
nxt = (nxt % 5 + 5) % 5;
return nxt;
}
int send_message(int N, int i, int pi) {
if (i == 1) {
n__ = N;
p__ = vector<ll>(n__);
depth__ = vector<ll>(n__);
calc_seq(0, 0);
sz__ = seq__.size();
seq__ = queue<ll>();
jmp__ = vector<vector<ll>>(n__, vector<ll>(20, -1));
for (ll i = 1; i < n__; i++) jmp__[i][0] = 0;
}
ll rem_inc = n__ - i;
if (rem_inc == sz__ + 1) {
calc_seq(mx_id_1__, mx_id_2__);
seq__.push(0);
}
bool sending = (rem_inc <= sz__ + 1);
int jam = 0;
p__[i] = pi;
depth__[i] = depth__[pi] + 1;
update_jmp(i);
// update pair
//ll di2 = lca_dist(i, mx_id_2__);
//ll d12 = lca_dist(mx_id_1__, mx_id_2__);
//ll d1i = lca_dist(mx_id_1__, i);
if (lca_dist(i, mx_id_2__) > lca_dist(mx_id_1__, mx_id_2__)) {
mx_id_1__ = i;
if (sending) {
jam = 3;
}
}
else if (lca_dist(mx_id_1__, i) > lca_dist(mx_id_1__, mx_id_2__)) {
mx_id_2__ = i;
if (sending) {
jam = 4;
}
}
if (!sending) return 0;
if (jam) {
if (prev_jam__) {
if (jam == prev_jam__) { // minor
ll nxt = seq__.front(); seq__.pop();
return encrypt_random(nxt + 2);
}
else { // major
return encrypt_random(4);
}
}
if (!prev_jam__) prev_jam__ = jam;
return encrypt_random(jam);
}
ll nxt = seq__.front(); seq__.pop();
return encrypt_random(nxt);
}
std::pair<int, int> longest_path(std::vector<int> s) {
mt = mt19937(SEED);
n__ = s.size();
calc_seq(0, 0);
sz__ = seq__.size();
seq__ = queue<ll>();
mx_id_1__ = mx_id_2__ = prev_jam__ = 0;
bool jam_1 = false, jam_2 = false;
ll first = n__ - (sz__ + 1);
for (ll i = first; i < n__; i++) {
ll rng = mt() % 5;
s[i] += rng;
s[i] = (s[i] % 5 + 5) % 5;
if (!prev_jam__) {
if (s[i] >= 3) { // jam
prev_jam__ = s[i];
if (s[i] == 3) {
mx_id_1__ = i;
jam_1 = true;
}
if (s[i] == 4) {
mx_id_2__ = i;
jam_2 = true;
}
continue;
}
seq__.push(s[i]);
}
else {
if (s[i] == 4) { // major jam
if (prev_jam__ == 3) {
mx_id_2__ = i;
}
if (prev_jam__ == 4) {
mx_id_1__ = i;
}
jam_1 = jam_2 = true;
continue;
}
seq__.push(s[i] & 1);
ll j = s[i] / 2;
if (j) { // minor jam
if (prev_jam__ == 3) {
mx_id_1__ = i;
}
if (prev_jam__ == 4) {
mx_id_2__ = i;
}
}
}
}
if (seq__.size() < sz__) return {mx_id_1__, mx_id_2__};
ll r = 0;
for (ll mask = 1; mask < n__ * n__; mask *= 2) {
r |= mask * seq__.front(); seq__.pop();
}
ll r_1 = r / n__;
ll r_2 = r % n__;
if (!jam_1) mx_id_1__ = r_1;
if (!jam_2) mx_id_2__ = r_2;
return {mx_id_1__, mx_id_2__};
}
#ifdef TEST
#include "grader.cpp"
#endif
