#include "telepathy.h"
#include <bits/stdc++.h>
using namespace std;
#define MASK(n) (1LL << (n))
template <class T> bool maximize(T &x, T y) {
if (x < y) {
x = y;
return true;
}
return false;
}
const int N = 200;
int sz[N], ma[N], par[N];
vector<int> adj[N];
void dfs(int u, int fa) {
sz[u] = 1, ma[u] = -1;
for (auto v : adj[u]) if (v != fa) {
dfs(v, u);
sz[u] += sz[v];
maximize(ma[u], sz[v]);
}
}
void dfs2(int u, int fa) {
for (auto v : adj[u]) if (v != fa) {
par[v] = u;
dfs2(v, u);
}
}
vector<int> getPath(int s, int t) {
dfs2(s, -1); vector<int> path;
while (t != s) path.emplace_back(t), t = par[t];
path.emplace_back(s);
reverse(path.begin(), path.end());
return path;
}
vector<int> Aitana(int n, vector<int> A, vector<int> B, int S, int subtask) {
for (int i = 0; i < n; ++i) adj[i].clear();
for (int i = 0; i < A.size(); ++i) {
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
dfs(0, -1);
vector<int> centroids;
for (int i = 0; i < n; ++i)
if (max(ma[i], n - sz[i]) <= n / 2) centroids.emplace_back(i);
if (centroids.size() == 1) centroids.emplace_back(centroids[0]);
vector<int> path = getPath(centroids[0], S);
path.pop_back();
vector<int> ans = {S};
for (int phase = 0; ; ++phase) {
if (path.empty()) break;
for (int i = 0; i < MASK(phase); ++i) {
if (phase % 2 == 0) {
if (path.empty()) break;
ans.emplace_back(path.back());
path.pop_back();
}
else {
ans.emplace_back(ans.back());
}
}
}
while (ans.size() < 10 * n + 1) {
if (ans.size() & 1) ans.emplace_back(centroids[1]);
else ans.emplace_back(centroids[0]);
}
return ans;
}
vector<int> Bruno(int n, vector<int> A, vector<int> B, int T, int subtask) {
for (int i = 0; i < n; ++i) adj[i].clear();
for (int i = 0; i < A.size(); ++i) {
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
dfs(0, -1);
vector<int> centroids;
for (int i = 0; i < n; ++i)
if (max(ma[i], n - sz[i]) <= n / 2) centroids.emplace_back(i);
if (centroids.size() == 1) centroids.emplace_back(centroids[0]);
vector<int> path = getPath(centroids[0], T);
path.pop_back();
vector<int> ans = {T};
for (int phase = 0; ; ++phase) {
if (path.empty()) break;
for (int i = 0; i < MASK(phase); ++i) {
if (phase % 2 == 1) {
if (path.empty()) break;
ans.emplace_back(path.back());
path.pop_back();
}
else {
ans.emplace_back(ans.back());
}
}
}
while (ans.size() < 10 * n + 1) ans.emplace_back(centroids[0]);
return ans;
}
