#include "telepathy.h"
#include <bits/stdc++.h>
using namespace std;
const int MN = 200;
int LOG = 8;
int n, st;
vector<vector<int>> tree;
vector<int> dep, par, sub;
int root = -1;
void get_subs(int node, int p = -1) {
sub[node] = 1;
for (auto next: tree[node]) {
if (next == p) continue;
get_subs(next, node);
sub[node] += sub[next];
}
}
void root_centroid(int node, int p = -1) {
root = node;
int mx = -1;
for (auto next: tree[node]) {
if (next == p) continue;
if (mx == -1 || sub[next] > sub[mx]) mx = next;
}
if (mx == -1) return;
if (2 * sub[mx] >= n) root_centroid(mx, node);
else return;
}
void precalc(int node, int p = -1) {
par[node] = p;
for (auto next: tree[node]) {
if (next == p) continue;
dep[next] = dep[node] + 1;
precalc(next, node);
}
}
void process_tree() {
dep.assign(n, 0);
par.assign(n, 0);
sub.assign(n, 0);
get_subs(1);
root_centroid(1);
precalc(root);
LOG = ceil(log2(n));
}
vector<pair<int, int>> ranges;
vector<int> climb_up(int curr) {
vector<int> ans = {curr};
for (int i = 1; i < LOG; i++) {
int sz = (1 << i);
for (int j = 0; j < n; j += sz) {
int currL = j;
int currR = j + sz - 1;
if (currL > dep[curr] || currR < dep[curr]) continue;
int tot = sz;
while (dep[curr] != currL) {
curr = par[curr];
ans.push_back(curr);
tot--;
}
while (tot--) ans.push_back(curr);
break;
}
}
return ans;
}
vector<int> Aitana(int N, std::vector<int> A, std::vector<int> B, int S, int subtask) {
n = N;
st = S;
tree.clear();
tree.resize(n);
for (int i = 0; i < n-1; i++) {
tree[A[i]].push_back(B[i]);
tree[B[i]].push_back(A[i]);
}
process_tree();
vector<int> ans = climb_up(st);
int mx = -1;
for (auto next: tree[root]) {
if (mx == -1 || sub[next] > sub[mx]) mx = next;
}
if (mx != -1) ans.push_back(mx);
cout << "DBG: " << ans.size() << "\n";
while (ans.size() < 10*n + 1) ans.push_back(ans.back());
return ans;
}
vector<int> Bruno(int N, std::vector<int> C, std::vector<int> D, int T, int subtask) {
n = N;
st = T;
tree.clear();
tree.resize(n);
for (int i = 0; i < n-1; i++) {
tree[C[i]].push_back(D[i]);
tree[D[i]].push_back(C[i]);
}
process_tree();
vector<int> ans = climb_up(st);
while (ans.size() < 10*n + 1) ans.push_back(ans.back());
return ans;
}
