#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include "grader.h"
#define endl '\n'
using namespace std;
int query(vector < int > islands);
vector <int> v1[600], v2;
int n;
int used[600];
void dfs(int beg)
{
v2.push_back(beg);
used[beg] = 1;
for(int i = 0; i < v1[beg].size(); i++)
{
if(!used[v1[beg][i]])
dfs(v1[beg][i]);
}
}
void fill_v1(int N, vector <pair <int, int> > bridges)
{
n = N;
for(int i = 1; i <= n; i++)
{
v1[i].clear();
}
for(int i = 0; i < bridges.size(); i++)
{
v1[bridges[i].first].push_back(bridges[i].second);
v1[bridges[i].second].push_back(bridges[i].first);
}
}
bool check(int mid)
{
vector <int> q;
for(int i = 0; i <= mid; i++)
q.push_back(v2[i]);
return query(q);
}
int bin_search()
{
int l = 0, r = v2.size()-1;
while(l < r)
{
int mid = (l+r)/2;
///cout << mid << " " << l << " " << r << endl;
if(check(mid) == 1)
r = mid;
else
l = mid+1;
}
return v2[l];
}
int findEgg(int N, vector < pair < int, int > > bridges)
{
fill_v1(N, bridges);
memset(used, 0, sizeof(used));
v2.clear();
dfs(1);
/*for(int i = 0; i < v2.size(); i++)
{
cout << v2[i] << " ";
}
cout << endl;*/
return bin_search();
}
