#include <bits/stdc++.h>
#include "grader.h"
#define MAXN 513
using namespace std;
vector<int> adj_lst[MAXN];
vector<int> dfsOrder;
int it = 0;
void dfs(int i, int p){
if( it ) return;
dfsOrder.push_back(i);
for( int j : adj_lst[i] ){
if( j == p ) continue;
dfs(j, i);
}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
//for( int i{1} ; i <= N ; ++i ) adj_lst[i].clear();
for( auto e : bridges ){
if( it ) break;
adj_lst[e.first].push_back(e.second);
adj_lst[e.second].push_back(e.first);
}
//dfsOrder.clear();
dfs(1, 0);
it = 1;
int l = 0, r = N-1;
int m; vector<int> q;
//for( int x : dfsOrder ) cout<<x<<" "; cout<<'\n';
while( l < r ){
m = (l+r)/2;
q.clear(); q.assign(dfsOrder.begin(), dfsOrder.begin()+m+1);
if(query(q)) r = m;
else l = m+1;
}
//cout<<l<<'\n';
return dfsOrder[l];
}
