#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e2 + 5;
int tin[maxn], f[maxn], timeDfs;
vector<int> g[maxn];
void dfs(int u, int pre){
tin[u] = ++timeDfs;
f[timeDfs] = u;
for(int v: g[u]){
if(v != pre) dfs(v, u);
}
}
/*int query(vector<int> x){
for(int v: x) cout << v << " ";
cout << '\n';
int k; cin >> k;
return k;
}
*/
int findEgg(int N, vector <pair<int, int>> bridges){
int n = N;
for(int i = 0; i < n - 1; i++){
int u = bridges[i].first, v = bridges[i].second;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
int l = 1, r = n, ans = -1;
while(l <= r){
int mid = (l + r) / 2;
vector<int> v;
for(int i = 1; i <= mid; i++) v.push_back(f[i]);
if(query(v) == 1){
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return f[ans];
}
/*signed main(){
int n = 5;
vector<pair<int, int>> k;
k.push_back({1, 2});
k.push_back({1, 3});
k.push_back({2, 4});
k.push_back({4, 5});
cout << findEgg(n, k);
}*/
