#include "bits/stdc++.h"
using namespace std;
#include "grader.h"
#ifdef duc_debug
#include "bits/debug.h"
#endif
const int maxn = 550;
int n;
vector<int> g[maxn];
int timer, tin[maxn], et[maxn];
void pre_dfs(int u, int prev) {
tin[u] = ++timer;
et[timer] = u;
for(auto v:g[u]) {
if(v == prev) continue;
pre_dfs(v, u);
}
}
int findEgg(int n, vector<pair<int, int>> edges) {
for(int i = 1; i <= n; ++i) {
g[i].clear();
}
for(auto i:edges) {
int u = i.first, v = i.second;
g[u].push_back(v);
g[v].push_back(u);
}
timer = 0;
pre_dfs(1, 0);
int l = 1, r = n - 1, res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
vector<int> v;
for(int i = 1; i <= mid; ++i) {
v.push_back(et[i]);
}
if(query(v)) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if(res == -1) res = n;
return et[res];
}
