#include <bits/stdc++.h>
using namespace std;
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
#define INF (ll)1e18
#define mod 998244353
#define maxn 110
#include "migrations.h"
vector<ll> parent, dist;
array<ll, 2> diam = {-1, -1};
vector<vector<ll>> adj;
int send_message(int N, int i, int Pi) {
// ~ 65 punti
if (parent.empty()) {
parent.resize(N, -1);
dist.resize(N, 0);
adj.resize(N);
}
auto calc_dist = [&](ll a, ll b) {
// cerr << "calc_dist" _ a _ b << nf;
ll ans = 0;
if (dist[a] > dist[b]) swap(a, b);
while (dist[a] < dist[b]) {
// cerr << a _ b << nf;
b = parent[b]; ans++;
}
while (a != b) {
// cerr << a _ b << nf;
a = parent[a]; b = parent[b]; ans += 2;
}
return ans;
};
auto bfs = [&](ll N, ll start) {
vector<bool> vis(N, false);
vector<ll> dist(N, INF);
function<void(ll)> dfs = [&](ll s) {
vis[s] = true;
for (auto u : adj[s]) {
if (vis[u]) continue;
dist[u] = dist[s] + 1;
dfs(u);
}
};
dfs(start);
array<ll, 2> opt = {-INF, -1};
for (ll i = 0; i < N; i++) opt = max(opt, {dist[i], i});
assert(opt[0] != INF);
return opt[1];
};
auto calc_diam = [&](ll N) {
ll a = bfs(N, 0);
ll b = bfs(N, a);
// cerr << "diam" _ a _ b << nf;
return array<ll, 2>{a, b};
};
parent[i] = Pi;
adj[i].pb(Pi); adj[Pi].pb(i);
dist[i] = dist[Pi] + 1;
if (i < N - 27) return 0;
if (i == N - 27) {
diam = calc_diam(i + 1);
}
auto upd_diam = [&](ll x, ll y, ll nw, ll pos) {
ll d1 = calc_dist(x, y);
if (pos == 1) {
ll d2 = calc_dist(nw, y);
if (d2 > d1) {
diam = {nw, y}; return true;
}
}
if (pos == 2) {
ll d2 = calc_dist(x, nw);
if (d2 > d1) {
diam = {x, nw}; return true;
}
}
return false;
};
auto [x, y] = diam;
ll to_send = N * x + y;
ll b = N - 1 - i;
ll ans = ((to_send >> b) & 1) + 1;
if (upd_diam(x, y, i, 1)) ans += 2;
if (upd_diam(x, y, i, 2)) ans += 4;
assert(ans <= 6);
return ans;
}
std::pair<int, int> longest_path(std::vector<int> S) {
ll N = S.size();
ll encoded = 0;
array<ll, 2> overwrite = {-1, -1};
for (ll i = 0; i < N; i++) {
if (S[i] == 0) continue;
ll message = S[i] - 1;
ll b = N - i - 1;
ll val = message % 2;
ll over_pos = message / 2;
if (over_pos >= 1) {
overwrite[over_pos - 1] = i;
}
encoded += (val << b);
}
assert(encoded < N * N);
array<ll, 2> ans = {encoded / N, encoded % N};
for (ll i = 0; i < 2; i++) {
if (overwrite[i] != -1) ans[i] = overwrite[i];
}
return {ans[0], ans[1]};
}
