#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 - 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 mx1 = 0; for(int j = 0; j <= N; j++) if(v[j] > v[mx1]) mx1 = j; dfs(mx1, -1, 0); int mx2 = mx1; for(int j = 0; j <= N; j++) if(v[j] > v[mx2]) mx2 = j; if(mx1 > mx2) swap(mx1, mx2); if(i == N - 1 && ml.first != -1 && make_pair(mx1, mx2) != ml) return 4; ml = make_pair(mx1, mx2); int tmp = mx1; for(int d = 6; d >= 0; --d){ vt[d] = tmp % 4; tmp /= 4; } return vt[i - (N - 7)]; } else if(i >= N - 14){ 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 mx1 = 0; for(int j = 0; j <= N; j++) if(v[j] > v[mx1]) mx1 = j; dfs(mx1, -1, 0); int mx2 = mx1; for(int j = 0; j <= N; j++) if(v[j] > v[mx2]) mx2 = j; if(mx1 > mx2) swap(mx1, mx2); if(i == N - 1 && ml.first != -1 && make_pair(mx1, mx2) != ml) return 4; ml = make_pair(mx1, mx2); int tmp = mx2; for(int d = 6; d >= 0; --d){ vt[d] = tmp % 4; tmp /= 4; } return vt[i - (N - 14)]; } return 0; } pair<int,int> longest_path(vector<int> S){ int mx = 0, mx1 = 0; int M = (int)S.size(); for(int i = M-14; i < M-7; i++){ if(S[i] == 4) return {0, i}; mx = mx*4 + S[i]; } for(int i = M-7; i < M; i++){ if(S[i] == 4) return {0, i}; mx1 = mx1*4 + S[i]; } if(mx > mx1) swap(mx, mx1); return {mx, mx1}; }