#include <bits/stdc++.h>
#include "grader.h"
// #define int long long
// #define fi first
// #define se second
//
// #define sz(a) (int)((a).size())
// #define all(a) (a).begin(), (a).end()
//
// #define lsb(x) (x & (-x))
// #define vi vector<int>
// #define YES { cout << "YES" << endl; return; }
// #define NO { cout << "NO" << endl; return; }
//
// using ll = long long;
// using pii = std::pair<int, int>;
const int NMAX = 512;
using namespace std;
vector<int> T[NMAX + 5];
vector<int> ord;
void dfs(int nod, int p = -1) {
ord.push_back(nod);
for (auto &son : T[nod]) {
if (son == p) continue;
dfs(son, nod);
}
}
int findEgg(int N, vector<pair<int, int>> bridges) {
fill(T + 1, T + N + 1, vector<int>());
ord.clear();
for (auto &[u, v] : bridges) {
T[u].push_back(v);
T[v].push_back(u);
}
dfs(1);
int lo = 1, hi = N, ans = -1;
while (lo <= hi) {
auto mid = (lo + hi) >> 1;
auto qry = vector<int>(ord.begin(), ord.begin() + mid);
if (query(qry)) {
ans = mid;
hi = mid - 1;
}
else
lo = mid + 1;
}
assert(ans != -1);
return ord[ans - 1];
}
#ifndef EVAL
#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
static int N, X, cntQ;
static vector < int > v[1009];
int query (vector < int > h) {
cntQ ++;
int ap[1009];
if (h.empty ()) return 0;
for (int i=1; i<=N; i++)
ap[i] = 0;
for (auto it = h.begin (); it != h.end (); it ++)
ap[*it] = 1;
queue < int > cc;
cc.push (h[0]), ap[h[0]] = 2;
while (!cc.empty ())
{
int nod = cc.front ();
cc.pop ();
for (auto it = v[nod].begin (); it != v[nod].end (); it ++)
if (ap[*it] == 1)
ap[*it] = 2, cc.push (*it);
}
for (int i=1; i<=N; i++)
if (ap[i] == 1) return -1;
for (auto it = h.begin (); it != h.end (); it ++)
if (*it == X) return 1;
return 0;
}
int main () {
cin >> N;
int Queries;
vector < pair < int, int > > param;
for (int i=1; i<N; i++)
{
int x, y;
cin >> x >> y;
v[x].push_back (y);
v[y].push_back (x);
param.push_back ({x, y});
}
cin >> Queries;
while (Queries --)
{
cin >> X;
int cntQ = 0;
int Y = findEgg (N, param);
if (X != Y)
{
printf ("WA %d instead of %d\n", Y, X);
return 0;
}
printf ("OK %d\n", cntQ);
}
return 0;
}
#endif
