#include<bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> st;
void to_binary(int num) {
for (int i = 0; i < 13; i++) {
if (num&1)
st.pb(1);
else
st.pb(0);
num >>= 1;
}
}
int from_binary(vector<int> v) {
int num = 0;
for (int e : v) {
num <<= 1;
num += e;
}
return num;
}
vector<int> graph[10001], depth(10001, 0);
int mxv;
void dfs(int u, int p, int &mx) {
if (depth[u] > depth[mxv])
mxv = u;
for (int e : graph[u])
if (e != p) {
depth[e] = depth[u]+1;
dfs(e, u, mx);
}
}
int send_message(int N, int i, int Pi) {
graph[Pi].pb(i);
if (i < N-14)
return 0;
if (i == N-14) {
mxv = 0;
depth.resize(10001, 0);
dfs(0, 0, mxv);
st.clear();
to_binary(mxv);
return 0;
} else if (i > N-14) {
int nmx = 0;
depth.resize(10001, 0);
dfs(0, 0, nmx);
if (depth[i] > depth[mxv]) {
mxv = i;
return 2;
}
}
int tp = st.back();
st.pop_back();
return tp;
}
pair<int, int> longest_path(std::vector<int> S) {
for (int i = S.size()-1; i >= S.size()-13; i--)
if (S[i] == 2)
return make_pair(0, i);
vector<int> v;
for (int i = S.size()-13; i < S.size(); i++)
v.pb(S[i]);
return make_pair(0, from_binary(v));
}
