#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int> g[600];
int t[600];
int idx=0;
void dfs(int now,int p){
t[++idx]=now;
for(auto x:g[now]){
if(x==p)continue;
dfs(x,now);
}
}
vector<int> bs;
int findEgg (int N, vector < pair < int, int > > bridges)
{
idx=0;
memset(t,0,sizeof t);
for(auto x:bridges){
g[x.first].push_back(x.second);
g[x.second].push_back(x.first);
}
dfs(1,1);
int l=1,r=idx;
while(l<r){
int mid=(l+r)/2;
bs.clear();
for(int i=1;i<=mid;i++)bs.push_back(t[i]);
if(query(bs))r=mid;
else l=mid+1;
}
for(int i=1;i<=N;i++)g[i].clear();
return t[l];
}
