#include "telepathy.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int;
const ll INF = 1e9;
vector<int> Aitana(int N, vector<int> A, vector<int> B, int S, int subtask) {
ll CONST = min(31, N);
vector<vector<ll> > adjMat(N, vector<ll>(N, INF));
vector<vector<ll> > adjList(N);
for (ll i = 0; i < N; i++) {
adjMat[i][i] = 0;
}
for (ll i = 0; i < N - 1; i++) {
adjMat[A[i]][B[i]] = adjMat[B[i]][A[i]] = 1;
adjList[A[i]].push_back(B[i]);
adjList[B[i]].push_back(A[i]);
}
for (ll k = 0; k < N; k++) {
for (ll i = 0; i < N; i++) {
for (ll j = 0; j < N; j++) {
adjMat[i][j] = min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]);
}
}
}
vector<ll> ends;
for (ll i = 0; i < N; i++) {
if (adjList[i].size() == 1) ends.push_back(i);
}
ll hasMnDist = -1;
for (ll i = 0; i < N; i++) {
if (adjMat[ends[0]][i] == N/2 && adjMat[ends[1]][i] == N/2) {
hasMnDist = i;
break;
}
if (adjMat[ends[0]][i] == N/2 - 1 && adjMat[ends[1]][i] == N/2) {
hasMnDist = i;
break;
}
}
ll currNode = S;
ll currDist = adjMat[currNode][hasMnDist];
ll numIter = 0;
vector<ll> currPath;
currPath.push_back(currNode);
while (currDist > 0) {
numIter++;
if (numIter == CONST) {
for (ll i = 0; i < CONST; i++) currPath.push_back(currNode);
}
for (ll i = 0; i < N; i++) {
if (adjMat[currNode][i] > 1) continue;
if (adjMat[i][hasMnDist] == currDist - 1) {
currNode = i;
currDist--;
currPath.push_back(i);
break;
}
}
}
while (currPath.size() <= N/2 + 1 + CONST) {
currPath.push_back(hasMnDist);
}
hasMnDist = ends[1];
currDist = adjMat[currNode][hasMnDist];
for (ll i = 0; i < N; i++) {
if (adjMat[currNode][i] > 1) continue;
if (adjMat[i][hasMnDist] == currDist - 1) {
currNode = i;
currDist--;
currPath.push_back(i);
break;
}
}
while (currPath.size() <= 10*N) {
currPath.push_back(currNode);
}
return currPath;
}
vector<int> Bruno(int N, vector<int> A, vector<int> B, int S, int subtask) {
ll CONST = min(31, N);
vector<vector<ll> > adjMat(N, vector<ll>(N, INF));
vector<vector<ll> > adjList(N);
for (ll i = 0; i < N; i++) {
adjMat[i][i] = 0;
}
for (ll i = 0; i < N - 1; i++) {
adjMat[A[i]][B[i]] = adjMat[B[i]][A[i]] = 1;
adjList[A[i]].push_back(B[i]);
adjList[B[i]].push_back(A[i]);
}
for (ll k = 0; k < N; k++) {
for (ll i = 0; i < N; i++) {
for (ll j = 0; j < N; j++) {
adjMat[i][j] = min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]);
}
}
}
vector<ll> ends;
for (ll i = 0; i < N; i++) {
if (adjList[i].size() == 1) ends.push_back(i);
}
ll hasMnDist = -1;
for (ll i = 0; i < N; i++) {
if (adjMat[ends[0]][i] == N/2 && adjMat[ends[1]][i] == N/2) {
hasMnDist = i;
break;
}
if (adjMat[ends[0]][i] == N/2 - 1 && adjMat[ends[1]][i] == N/2) {
hasMnDist = i;
break;
}
}
ll currNode = S;
ll currDist = adjMat[currNode][hasMnDist];
vector<ll> currPath;
currPath.push_back(currNode);
for (ll i = 0; i < CONST; i++) currPath.push_back(currNode);
while (currDist > 0) {
for (ll i = 0; i < N; i++) {
if (adjMat[currNode][i] > 1) continue;
if (adjMat[i][hasMnDist] == currDist - 1) {
currNode = i;
currDist--;
currPath.push_back(i);
break;
}
}
}
while (currPath.size() <= 10*N) {
currPath.push_back(hasMnDist);
}
return currPath;
}
