#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl "\n" // remove in interactive
#endif
const int N = 10000;
const int logN = 14;
int par[logN][N];
int depth[N];
int lca(int a, int b)
{
if(depth[a]<depth[b])
swap(a,b);
int l = depth[a]-depth[b];
for(int i = 0;i<logN;i++) if(l&(1<<i)) a = par[i][a];
if(a==b)
return a;
assert(depth[a] == depth[b]);
for(int i = logN-1;i>=0;i--)
if(par[i][a]!=par[i][b])
{
a = par[i][a],b = par[i][b];
}
return par[0][a];
}
int pathlen(int a, int b){
return depth[a] + depth[b] - 2 * depth[lca(a, b)];
}
vector<pair<int, int>> pool;
vector<int> L = {221, 13};
const int T1 = N - (4 + 13 + 221);
const int T2 = N - (4 + 13);
const int T3 = N - 4;
int a, b, P, Q, R;
int A, B;
vector<int> message;
int message_pos;
int pos_4;
void get(int ID, int l, int max_non_zero){
vector<int> msg, pos, pos2, msg2;
function<void(int)> recurse = [&](int i){
ID--;
if(ID == -1){
msg2 = msg;
pos2 = pos;
return;
}
if(i == max_non_zero) return;
// next non-zero
int prv = i == 0 ? -1: pos[i - 1];
for(int j = prv + 1; j < l; j++){
for(int v = 1; v <= 3; v++){
msg.push_back(v);
pos.push_back(j);
recurse(i + 1);
msg.pop_back();
pos.pop_back();
}
}
};
recurse(0);
// trace(pos2, msg2, ID);
int j = 0;
message.resize(l, 0);
for(int i = 0; i < sz(msg2); i++){
message[pos2[i]] = msg2[i];
}
message_pos = 0;
pos_4 = -1;
}
vector<vector<int>> cliques_6, cliques_4, paths;
vector<vector<pair<int, int>>> parts;
int id = -1;
int send_message(int n, int i, int Pi) {
par[0][i] = Pi;
depth[i] = depth[Pi] + 1;
for(int j = 1; j < logN; j++) {
par[j][i] = par[j - 1][par[j - 1][i]];
}
int d_ab = pathlen(a, b);
int d_ia = pathlen(i, a);
int d_ib = pathlen(i, b);
if(d_ia >= max(d_ib, d_ab)){
b = i;
}
else if(d_ib >= max(d_ia, d_ab)){
a = i;
}
if(a < b) swap(a, b);
// trace(i, a, b);
if(i < T1) return 0;
if(i == T1){
A = a; B = b;
int ID = (a * (a - 1)) / 2 + b;
get(ID, L[0], 3); // cost = 3
}
if(i < T2){
if(i != T1){
if(a == i || b == i){
if(a != A && a != B && b != A && b != B){
pos_4 = i;
return 4;
}
}
}
return message[message_pos++];
}
if(i == T2){
// trace(pos_4);
// compute the pool
P = A, Q = B, R = i;
pool.clear();
if(pos_4 != -1){
P = pos_4; Q = pos_4;
}
pool.push_back({P, Q});
pool.push_back({P, R});
pool.push_back({Q, R});
for(int j = T1; j < T2; j++){
pool.push_back({P, j});
pool.push_back({Q, j});
pool.push_back({R, j});
}
for(auto& it: pool){
if(it.first < it.second) swap(it.first, it.second);
}
sort(all(pool));
if(a < b) swap(a, b);
A = a; B = b;
int ID = -1;
for(int i = 0; i < pool.size(); i++){
if(pool[i].first == a && pool[i].second == b){
ID = i;
break;
}
}
// trace(A, B);
assert(ID != -1);
get(ID, L[1], 2); // cost = 2
}
if(i < T3){
if(i != T2){
if(a == i || b == i){
if(a != A && a != B && b != A && b != B){
pos_4 = i;
return 4;
}
}
}
return message[message_pos++];
}
if(i == T3){
P = A, Q = B, R = i;
if(pos_4 != -1){
P = pos_4; Q = pos_4;
}
// cover using K6 graphs
// T2 + 1, ... i - 1 -- 12 nodes
// P Q R
cliques_6 = {
{P, Q, R, T2 + 1, T2 + 2, T2 + 3},
{P, Q, R, T2 + 4, T2 + 5, T2 + 6},
{P, Q, R, T2 + 7, T2 + 8, T2 + 9},
{P, Q, R, T2 + 10, T2 + 11, T2 + 12},
{P, Q, R, T2 + 1, T2 + 2, T2 + 3}
};
// trace(cliques_6);
// trace(cliques_6, pos_4);
for(int i = 0; i < 5; i++){
if(find(all(cliques_6[i]), a) != cliques_6[i].end() &&
find(all(cliques_6[i]), b) != cliques_6[i].end()){
id = i;
break;
}
}
assert(id != -1);
return id;
}
if(i == T3 + 1){
vector<int> nodes = cliques_6[id];
nodes.push_back(i);
cliques_4 = {
{nodes[0], nodes[1], nodes[2], nodes[3]},
{nodes[0], nodes[1], nodes[2], nodes[4]},
{nodes[0], nodes[1], nodes[2], nodes[5]},
{nodes[0], nodes[1], nodes[2], nodes[6]},
{nodes[3], nodes[4], nodes[5], nodes[6]}
};
// trace(cliques_4);
id = -1;
for(int i = 0; i < 5; i++){
if(find(all(cliques_4[i]), a) != cliques_4[i].end() &&
find(all(cliques_4[i]), b) != cliques_4[i].end()){
id = i;
break;
}
}
assert(id != -1);
return id;
}
if(i == T3 + 2){
vector<int> nodes = cliques_4[id];
nodes.push_back(i);
paths = {
{1, 0, 4},
{1, 2, 3},
{0, 2, 4},
{3, 4, 1},
{1, 3, 0}
};
id = -1;
for(int ii = 0; ii < paths.size(); ii++){
vector<int> path = paths[ii];
vector<int> newpath = path;
for(int j = 0; j < sz(path); j++){
newpath[j] = nodes[path[j]];
}
vector<pair<int, int>> part;
for(int j = 0; j + 1 < path.size(); j++){
int u = nodes[path[j]];
int v = nodes[path[j + 1]];
if(u < v) swap(u, v);
part.push_back({u, v});
if(a == u && b == v) id = ii;
}
paths[ii] = newpath;
parts.push_back(part);
}
// trace(paths, parts);
assert(id != -1);
return id;
}
vector<pair<int, int>> fin;
if(i == T3 + 3){
vector<int> path = paths[id];
fin = parts[id];
fin.push_back({path[0], i});
fin.push_back({path[1], i});
fin.push_back({path[2], i});
for(auto& it: fin){
if(it.first < it.second) swap(it.first, it.second);
}
sort(all(fin));
// trace(fin);
id = -1;
for(int j = 0; j < fin.size(); j++){
if(fin[j].first == a && fin[j].second == b){
id = j;
break;
}
}
assert(id != -1);
// trace(a, b);
return id;
}
return 0;
}
int getID(int l, int max_non_zero) {
vector<int> msg, pos, pos2, msg2;
for(int i = 0; i < l; i++) if(message[i] != 0) {
pos2.push_back(i);
msg2.push_back(message[i]);
}
int ID = -1;
int cur = -1;
function<void(int)> recurse = [&](int i){
cur++;
if(msg == msg2 && pos == pos2) {
ID = cur;
return;
}
if(i == max_non_zero) return;
// next non-zero
int prv = i == 0 ? -1: pos[i - 1];
for(int j = prv + 1; j < l; j++){
for(int v = 1; v <= 3; v++){
msg.push_back(v);
pos.push_back(j);
recurse(i + 1);
msg.pop_back();
pos.pop_back();
}
}
};
recurse(0);
return ID;
}
std::pair<int, int> longest_path(std::vector<int> S) {
// return {0, 3};
a, b = 0, 0;
message.clear();
pos_4 = -1;
for(int i = T1; i < T2; i++){
message.push_back(S[i]);
if(S[i] == 4) pos_4 = i;
}
if(pos_4 != -1){
P = pos_4; Q = pos_4; R = T2;
} else{
int ID = getID(L[0], 3);
for(int _a = 1; _a < N; _a++){
for(int _b = 0; _b < _a; _b++){
ID--;
if(ID == -1){
a = _a;
b = _b;
break;
}
}
}
P = a; Q = b; R = T2;
}
pool.clear();
pool.push_back({P, Q});
pool.push_back({P, R});
pool.push_back({Q, R});
for(int j = T1; j < T2; j++){
pool.push_back({P, j});
pool.push_back({Q, j});
pool.push_back({R, j});
}
for(auto& it: pool){
if(it.first < it.second) swap(it.first, it.second);
}
sort(all(pool));
message.clear();
pos_4 = -1;
for(int i = T2; i < T3; i++){
message.push_back(S[i]);
if(S[i] == 4) pos_4 = i;
}
if(pos_4 != -1){
P = pos_4; Q = pos_4; R = T3;
} else{
int ID = getID(L[1], 2);
a = pool[ID].first;
b = pool[ID].second;
P = a; Q = b; R = T3;
}
cliques_6 = {
{P, Q, R, T2 + 1, T2 + 2, T2 + 3},
{P, Q, R, T2 + 4, T2 + 5, T2 + 6},
{P, Q, R, T2 + 7, T2 + 8, T2 + 9},
{P, Q, R, T2 + 10, T2 + 11, T2 + 12},
{P, Q, R, T2 + 1, T2 + 2, T2 + 3}
};
// trace(cliques_6, pos_4);
id = S[T3];
vector<int> nodes = cliques_6[id];
nodes.push_back(T3 + 1);
cliques_4 = {
{nodes[0], nodes[1], nodes[2], nodes[3]},
{nodes[0], nodes[1], nodes[2], nodes[4]},
{nodes[0], nodes[1], nodes[2], nodes[5]},
{nodes[0], nodes[1], nodes[2], nodes[6]},
{nodes[3], nodes[4], nodes[5], nodes[6]}
};
id = S[T3 + 1];
nodes = cliques_4[id];
nodes.push_back(T3 + 2);
paths = {
{1, 0, 4},
{1, 2, 3},
{0, 2, 4},
{3, 4, 1},
{1, 3, 0}
};
for(int ii = 0; ii < paths.size(); ii++){
vector<int> path = paths[ii];
vector<int> newpath = path;
for(int j = 0; j < sz(path); j++){
newpath[j] = nodes[path[j]];
}
vector<pair<int, int>> part;
for(int j = 0; j + 1 < path.size(); j++){
int u = nodes[path[j]];
int v = nodes[path[j + 1]];
if(u < v) swap(u, v);
part.push_back({u, v});
}
paths[ii] = newpath;
parts.push_back(part);
}
id = S[T3 + 2];
vector<int> path = paths[id];
vector<pair<int, int>> fin = parts[id];
fin.push_back({path[0], T3 + 3});
fin.push_back({path[1], T3 + 3});
fin.push_back({path[2], T3 + 3});
for(auto& it: fin){
if(it.first < it.second) swap(it.first, it.second);
}
sort(all(fin));
id = S[T3 + 3];
// trace(cliques_6, cliques_4, paths, parts, fin);
return {fin[id].first, fin[id].second};
}
