#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int i, cur[1005];
vector<int> result[1005];
void DFS(int res, int ans){
cur[++i] = res;
for(auto to : result[res]){
if(to == ans) continue;
DFS(to, res);
}
}
int Query(int res){
vector<int> v;
for(int i = 1; i <= res; i++) v.push_back(cur[i]);
return query(v);
}
int findEgg(int n, vector<pair<int, int>> bridges){
for(int i = 1; i <= n; i++) result[i].clear();
for(auto e: bridges){
result[e.first].push_back(e.second);
result[e.second].push_back(e.first);
} i = 0; DFS(1, 0);
int l = 1, r = n;
while(l < r){
int m = l + (r - l) / 2;
if(Query(m)) r = m;
else l = m + 1;
} return cur[l];
}
