#include "telepathy.h"
using namespace std;
#include <iostream>
const int log = 8;
vector<int> bruma(int N, vector<int> A, vector<int> B, int S, int turn) {
vector<vector<int>> ad(N);
for(int i=0; i<N-1; i++) {
ad[A[i]].push_back(B[i]);
ad[B[i]].push_back(A[i]);
}
pair<int, int> centroid = {-1, -1};
vector<int> sz(N);
vector<int> up(N);
auto dfs = [&](auto &&self, int v, int p) -> void {
up[v] = p;
sz[v] = 1;
for(int u: ad[v]) {
if(u == p) continue;
self(self, u, v);
sz[v] += sz[u];
}
};
auto find_centroid = [&](auto &&self, int v, int p) -> void {
int sz_sum = 1;
bool is_centroid = 1;
for(int u: ad[v]) {
if(u == p) continue;
self(self, u, v);
sz_sum += sz[u];
if(sz[u] > N/2) is_centroid = 0;
}
if(N - sz_sum > N/2) is_centroid = 0;
if(is_centroid) {
centroid.second = v;
if(centroid.first == -1) centroid.first = v;
}
};
dfs(dfs, 0, 0);
find_centroid(find_centroid, 0, 0);
dfs(dfs, centroid.first, centroid.second);
dfs(dfs, centroid.second, centroid.first);
vector<int> ans;
int curr_node = S;
ans.push_back(curr_node);
for(int i=0; i<=log; i++) {
for(int j=0; j<(1 << i); j++) {
if(turn) curr_node = up[curr_node];
ans.push_back(curr_node);
if(ans.size() == 10*N + 1) return ans;
}
turn ^= 1;
}
while(ans.size() < 10*N + 1) ans.push_back(ans.back());
return ans;
}
vector<int> Aitana(int N, vector<int> A, vector<int> B, int S, int subtask) {
return bruma(N, A, B, S, 0);
}
vector<int> Bruno(int N, vector<int> C, vector<int> D, int T, int subtask) {
return bruma(N, C, D, T, 1);
}
