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