#include "telepathy.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
vector<int> P;
int d1, d2;
void read(int N, vector<int> &a, vector<int> &b) {
for(int i=0; i<N-1; i++) {
G[a[i]].push_back(b[i]);
G[b[i]].push_back(a[i]);
}
}
void findd(int N) {
d1 = -1;
d2 = -1;
int M = 0;
vector<int> d(N);
vector<int> from(N);
auto dfs = [&](int n, int f, auto &&dfs) -> void {
if(n == -1) return;
from[n] = f;
for(int n2: G[n]) {
if(n2 == f) continue;
d[n2] = d[n]+1;
if(d[n2] >= d[M]) M = n2;
dfs(n2, n, dfs);
}
};
dfs(0, -1, dfs);
d[M] = 0;
dfs(M, -1, dfs);
d1 = M;
for(int i=0; i<d[M]/2; i++) {
d1 = from[d1];
}
if(d[M]%2) d2 = from[d1];
P.resize(N);
auto dfs2 = [&](int n, int f, auto &&dfs2) -> void {
if(n == -1) return;
for(int n2: G[n]) {
if(n2 == f) continue;
P[n2] = n;
dfs2(n2, n, dfs2);
}
};
dfs2(d1, d2, dfs2);
dfs2(d2, d1, dfs2);
P[d1] = d1;
if(d2 != -1) {
P[d2] = d1;
P[d1] = d2;
}
fprintf(stderr, "d1 = %d d2 = %d \n", d1, d2);
}
std::vector<int> Aitana(int N, std::vector<int> A, std::vector<int> B, int S, int subtask) {
G = vector(N, vector<int>());
read(N, A, B);
findd(N);
vector<int> opp = {3, -2, 0, 11, 37, -23, 0, 20};
stack<int> st;
vector<int> ans = {S};
int n = S;
for(int i=0; i<opp.size() && ans.size() < N*10; i++) {
int x = opp[i];
if(x > 0) {
for(int j=0; j<x; j++) {
ans.push_back(P[n]);
if(ans.size() == N*10) break;
st.push(n);
n = P[n];
}
}
else if(x < 0) {
for(int j=0; j<-x; j++) {
ans.push_back(st.top());
if(ans.size() == N*10) break;
n = st.top();
st.pop();
}
}
else {
i++;
x = opp[i];
for(int j=0; j<x; j++) {
ans.push_back(n);
if(ans.size() == N*10) break;
}
}
}
while(n != d1 && n != d2 && ans.size() <= 10*N) {
ans.push_back(P[n]);
n = P[n];
}
while(ans.size() <= 10*N) {
ans.push_back(n);
}
return ans;
}
std::vector<int> Bruno(int N, std::vector<int> C, std::vector<int> D, int T, int subtask) {
G = vector(N, vector<int>());
read(N, C, D);
findd(N);
vector<int> opp = {1, 0, 2, 12, -8, 0, 29, 43};
stack<int> st;
vector<int> ans = {T};
int n = T;
for(int i=0; i<opp.size() && ans.size() < N*10; i++) {
int x = opp[i];
if(x > 0) {
for(int j=0; j<x; j++) {
ans.push_back(P[n]);
if(ans.size() == N*10) break;
st.push(n);
n = P[n];
}
}
else if(x < 0) {
for(int j=0; j<-x; j++) {
ans.push_back(st.top());
if(ans.size() == N*10) break;
n = st.top();
st.pop();
}
}
else {
i++;
x = opp[i];
for(int j=0; j<x; j++) {
ans.push_back(n);
if(ans.size() == N*10) break;
}
}
}
while(n != d1 && n != d2 && ans.size() <= 10*N) {
ans.push_back(P[n]);
n = P[n];
}
while(ans.size() <= 10*N) {
if(d2 == -1 || n == d2) {
ans.push_back(d1);
n = d1;
}
else {
ans.push_back(d2);
n = d2;
}
}
return ans;
}
#ifdef MARCO
signed main() {
int qq; cin >> qq; cin >> qq;
int N; cin >> N;
vector<int> a(N), b(N);
for(int i=0; i<N-1; i++) {
cin >> a[i] >> b[i];
}
vector<int> p(N), q(N);
for(auto &i: p) cin >> i;
for(auto &i: q) cin >> i;
int A, B; cin >> A >> B;
vector<int> AA = Aitana(N, a, b, A, 0);
vector<int> BB = Bruno(N, a, b, B, 0);
cout << "AA:\n";
for(int i: AA) cout << i << " "; cout << "\n";
cout << "BB:\n";
for(int i: BB) cout << i << " "; cout << "\n";
for(int i=0; i<10*N; i++) {
if(AA[i] == BB[i]) {
cout << "answer = " << i << "\n";
return 0;
}
}
}
#endif
