#include "telepathy.h"
#include <bits/stdc++.h>
using namespace std;
namespace{
vector<int> adjlst[210];
vector<int> dfs(int i, int p){
pair<int,vector<int>> big = {0,{}};
for(int j : adjlst[i]){
if(j == p) continue;
vector<int> temp = dfs(j,i);
big = max(big,{temp.size(), temp});
}
big.second.push_back(i);
return big.second;
}
vector<int> diam(){
vector<int> temp = dfs(0,-1);
return dfs(temp[0],-1);
}
vector<int> path(int i, int p , int v){
if(i == v) return {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 vector<int>();
}
}
std::vector<int> Aitana(int N, std::vector<int> A, std::vector<int> B, int S, int subtask) {
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();
int d1 = v[v.size()/2];
int d2 = v[(v.size()-1)/2];
int cont = 1;
v = path(S,-1,d1);
vector<int> ans = {S};
v.pop_back();
int curr = S;
for(int i = 0; ; i++){
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 - 1; i++){
adjlst[C[i]].push_back(D[i]);
adjlst[D[i]].push_back(C[i]);
}
vector<int> v = diam();
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++){
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;
}
