#include <bits/stdc++.h> using namespace std; int p[10001]; vector<vector<int>> a; vector<int> v; void dfs(int u, int k, int cnt){ v[u] = cnt; for(int e : a[u]) if(e != k) dfs(e, u, cnt + 1); } int vt[7]; pair<int,int> ml = {-1,-1}; int send_message(int N, int i, int Pi){ p[i] = Pi; if(i >= N - 14 && i < N - 7){ a.assign(N + 1, {}); v.assign(N + 1, 0); for(int j = 1; j <= N; j++) a[p[j]].push_back(j); dfs(0, -1, 0); int u = 0; for(int j = 0; j <= N; j++) if(v[j] > v[u]) u = j; dfs(u, -1, 0); int vtx = u; for(int j = 0; j <= N; j++) if(v[j] > v[vtx]) vtx = j; int x = u, y = vtx; if(x > y) swap(x, y); if(i == N - 1 && ml.first != -1 && make_pair(x, y) != ml) return 4; ml = make_pair(x, y); int tmp = x; for(int d = 6; d >= 0; --d){ vt[d] = tmp % 4; tmp /= 4; } return vt[i - (N - 14)]; } else if(i >= N - 7){ a.assign(N + 1, {}); v.assign(N + 1, 0); for(int j = 1; j <= N; j++) a[p[j]].push_back(j); dfs(0, -1, 0); int u = 0; for(int j = 0; j <= N; j++) if(v[j] > v[u]) u = j; dfs(u, -1, 0); int vtx = u; for(int j = 0; j <= N; j++) if(v[j] > v[vtx]) vtx = j; int x = u, y = vtx; if(x > y) swap(x, y); if(i == N - 1 && ml.first != -1 && make_pair(x, y) != ml) return 4; ml = make_pair(x, y); int tmp = y; for(int d = 6; d >= 0; --d){ vt[d] = tmp % 4; tmp /= 4; } return vt[i - (N - 7)]; } return 0; } pair<int,int> longest_path(vector<int> S){ int a1 = 0, a2 = 0; for(int i = S.size() - 14; i < S.size() - 7; ++i){ if(S[i] == 4) return {0, i}; a1 = a1 * 4 + S[i]; } for(int i = S.size() - 7; i < S.size(); ++i){ if(S[i] == 4) return {0, i}; a2 = a2 * 4 + S[i]; } if(a1 > a2) swap(a1, a2); return {a1, a2}; }