// #include "telepathy.h"
#include<vector>
#include<iostream>
using namespace std;
// std::vector<int> Aitana(int N, std::vector<int> A, std::vector<int> B, int S,
// int subtask) {
// vector<int> ans;
// while(ans.size()<=10*N)
// {
// ans.push_back(ans.back());
// }
// return ans;
// }
const int TPL=500;
vector<int> ma[TPL],ord;
int h[TPL],par[TPL];
void dfs(int x,int p=-1)
{
ord.push_back(x);
par[x]=p;
for(auto y:ma[x])
{
if(y!=p)
{
h[y]=h[x]+1;
dfs(y,x);
ord.push_back(x);
}
}
}
std::vector<int> Bruno(int N, std::vector<int> C, std::vector<int> D, int T,
int subtask) {
for(int i=0;i<=N;i++)ma[i].clear();
for(int i=0;i<N-1;i++)
{
ma[C[i]].push_back(D[i]);
ma[D[i]].push_back(C[i]);
}
ord.clear();
int xas=N/2;
h[xas]=1;
dfs(xas); // only works for this P = Q shit subtask = 1
vector<int> ans;
ans.push_back(T);
for(int i=1+((N+1)/2);i>=1;i--)
{
int sp=ans.size();
while(h[T]>i){
T=par[T];
ans.push_back(T);
}
if(sp==ans.size())ans.push_back(T);
// cout<<T<<' ';
}
// cout<<endl;
// for(auto x:ord)
// {
// ans.push_back(x);
// }
while(ans.size()<=10*N)
{
ans.push_back(ans.back());
}
return ans;
}
std::vector<int> Aitana(int N, std::vector<int> C, std::vector<int> D, int T,
int subtask) {
for(int i=0;i<=N;i++)ma[i].clear();
for(int i=0;i<N-1;i++)
{
ma[C[i]].push_back(D[i]);
ma[D[i]].push_back(C[i]);
}
ord.clear();
int xas=N/2;
h[xas]=1;
dfs(xas); // only works for this P = Q shit subtask = 1
vector<int> ans;
// cout<<"Aitana: ";
ans.push_back(T);
for(int i=1+((N+1)/2);i>=1;i--)
{
int sp=ans.size();
while(h[T]>i){
T=par[T];
ans.push_back(T);
}
if(sp==ans.size())ans.push_back(T);
// cout<<T<<' ';
}
// cout<<endl;
while(ans.size()<=10*N)
{
ans.push_back(ans.back());
}
return ans;
}
