#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;
mt19937 mt(34056237);
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;
void calc_seq(ll i1, ll i2) {
seq__ = queue<ll>();
for (ll mask = 1; mask < n__; mask *= 2) {
seq__.push((i1 / mask) & 1);
}
for (ll mask = 1; mask < n__; mask *= 2) {
seq__.push((i2 / mask) & 1);
}
}
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>();
}
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;
if (depth__[i] > depth__[mx_id_1__]) {
mx_id_1__ = i;
if (sending) {
jam = 3;
}
}
if (!sending) return 0;
if (jam) {
if (prev_jam__) {
if (jam == prev_jam__) { // minor
ll nxt = seq__.front(); seq__.pop();
return nxt + 2;
}
else { // major
return 4;
}
}
if (!prev_jam__) prev_jam__ = jam;
return jam;
}
ll nxt = seq__.front(); seq__.pop();
return nxt;
}
std::pair<int, int> longest_path(std::vector<int> s) {
assert(*max_element(all(s)) == 1);
ll 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++) {
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_1 = 0, r_2 = 0;
for (ll mask = 1; mask < n; mask *= 2) {
r_1 |= mask * seq__.front(); seq__.pop();
}
for (ll mask = 1; mask < n; mask *= 2) {
r_2 |= mask * seq__.front(); seq__.pop();
}
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
