#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 517;
vector<int> g[maxn], f;
void dfs(int u, int pre){
f.push_back(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;
f.clear();
for(auto [u, v]: bridges){
g[u].push_back(v);
g[v].push_back(u);
}
f.push_back(0);
dfs(1, 0);
for(int i = 1; i <= n; i++) g[i].clear();
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);
}*/
