#include "migrations.h"
using namespace std;
#include <bits/stdc++.h>
vector<vector<int>> adj;
vector<int> dist_from_0;
void dfs(int u){
for(int v : adj[u]){
dist_from_0[v] = dist_from_0[u] + 1;
dfs(v);
}
}
int furtherest = 0;
int send_message(int N, int i, int Pi) {
if(i == 1){
adj.resize(N);
dist_from_0.resize(N, 0);
adj[Pi].push_back(1);
return 0;
}
adj[Pi].push_back(i);
if(i < 9996) return 0;
if(i == 9996){
int max_dist = 0;
dfs(0);
for(int iz = 0; iz < dist_from_0.size(); iz ++){
if(dist_from_0[iz] > max_dist){
max_dist = dist_from_0[iz];
furtherest = iz;
}
}
return (furtherest / 1000) % 10;
}
if(i == 9997){
return (furtherest / 100) % 10;
}
if(i == 9998){
return (furtherest / 10) % 10;
}
if(i == 9999){
int max_dist = 0;
int furth = 0;
dfs(0);
for(int iz = 0; iz < dist_from_0.size(); iz ++){
if(dist_from_0[iz] > max_dist){
max_dist = dist_from_0[iz];
furth = iz;
}
}
if(furth == furtherest){
return furtherest % 10;
}
return furth % 10 + 10;
}
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S) {
if(S.back() < 10){
int res = 0;
res += S[9996] * 1000;
res += S[9997] * 100;
res += S[9998] * 10;
res += S[9999];
return {0, res};
}
return {0, S.back() + 9980};
}
/*
g++ -std=gnu++20 -Wall -O2 -pipe -static -g -o migrations grader.cpp migrations.cpp
6
0 0 2 2 3
*/
