#include "grader.h"
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=1000;
int used[maxn];
vector<int> v1,v[maxn];
void dfs(int a)
{
used[a]=1;
for(int i=0;i<v[a].size();i++)
{
int nb=v[a][i];
if(!used[nb])
{
v1.push_back(nb);
dfs(nb);
}
}
}
int findEgg(int N, vector < pair < int, int > > bridges)
{
int n=N;
for(int i=0;i<bridges.size();i++)
{
v[bridges[i].first].push_back(bridges[i].second);
v[bridges[i].second].push_back(bridges[i].first);
}
dfs(1);
int l=0,r=v1.size();
while(l<=r)
{
vector<int> v2;
int m=(l+r)/2;
for(int i=0;i<m;i++) v2.push_back(v1[i]);
if(query(v2)) r=m-1;
else l=m+1;
}
return r-1;
}
