#include "telepathy.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
namespace{
vector<int> adjlst[210];
pair<int,int> dfs(int i, int p){
pair<int,int> big = {0,i};
for(int j : adjlst[i]){
if(j == p) continue;
big = max(big,dfs(j,i));
}
big.first++;
return big;
}
vector<int>* path(int i, int p , int v){
if(i == v) return new vector<int>({v});
for(int j : adjlst[i]){
if(j == p) continue;
vector<int>* temp = path(j,i,v);
if(!(temp -> empty())){
temp -> push_back(i);
return temp;
}
}
return new vector<int>();
}
vector<int> diam(){
vector<int>* temp = path(dfs(0,-1).second,-1,0);
return *path( dfs( (*temp)[0],-1).second, -1 , (*temp)[0]);
}
}
std::vector<int> Aitana(int N, std::vector<int> A, std::vector<int> B, int S, int subtask) {
for(int i = 0; i < N; i++) adjlst[i].clear();
for(int i = 0; i < N - 1; i++){
adjlst[A[i]].push_back(B[i]);
adjlst[B[i]].push_back(A[i]);
}
vector<int> v = diam();
assert (v.size() == N);
int d1 = v[v.size()/2];
int d2 = v[(v.size()-1)/2];
//printf("s");
int cont = 1;
v = *path(S,-1,d1);
vector<int> ans = {S};
v.pop_back();
//printf("e");
int curr = S;
for(int i = 0; ; i++){
if(v.empty()) break;
for(int j = 0; j < (1<<i); j++){
if(i % 2 == 0){
if(v.empty()) break;
curr = v.back();
ans.push_back(curr);
v.pop_back();
cont++;
}
else{
ans.push_back(curr);
cont++;
}
}
}
while(cont < 10 * N + 1){
if(cont % 4 == 1 || cont % 4 == 2){
ans.push_back(d1);
}
else{
ans.push_back(d2);
}
cont++;
}
return ans;
}
std::vector<int> Bruno(int N, std::vector<int> C, std::vector<int> D, int T, int subtask) {
for(int i = 0; i < N; i++) adjlst[i].clear();
for(int i = 0; i < N - 1; i++){
adjlst[C[i]].push_back(D[i]);
adjlst[D[i]].push_back(C[i]);
}
vector<int> v = diam();
assert (v.size() == N);
int d1 = v[v.size()/2];
int d2 = v[(v.size()-1)/2];
int cont = 1;
v = *path(T,-1,d1);
vector<int> ans = {T};
v.pop_back();
int curr = T;
for(int i = 0; ; i++){
if(v.empty()) break;
for(int j = 0; j < (1<<i); j++){
if(i % 2 == 1){
if(v.empty()) break;
curr = v.back();
ans.push_back(curr);
v.pop_back();
cont++;
}
else{
ans.push_back(curr);
cont++;
}
}
}
while(cont < 10 * N + 1){
if(cont % 4 == 0 || cont % 4 == 1){
ans.push_back(d1);
}
else{
ans.push_back(d2);
}
cont++;
}
return ans;
}
/*
int main(){
int N = 149;
vector<int> u;
vector<int> v;
for(int i = 1; i < N; i++) v.push_back(i);
for(int i = 1; i < N; i++) u.push_back(i - 1);
for(int i = 1; i < N - 1; i++){
int x = rng() % i;
swap(v[i],v[x]);
swap(u[i],u[x]);
}
for(int i :v) printf("%d ",i);
printf("\n");
for(int i : u) printf("%d ",i);
printf("\n");
vector<int> t = Aitana(N, u, v, rng() % N, 2);
Bruno(N, u, v, rng() % N, 2);
for(int i : t) printf("%d ",i);
}
*/
