#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define pb push_back
#define ff first
#define ss second
const int sz = 512 + 5 ;
vector<int>adj[sz] ;
vector<int>a ;
vector<bool>vis(sz) ;
void dfs(int node) {
a.push_back(node);
vis[node] = 1 ;
for(int i : adj[node]) {
if(vis[i] == 0) {
dfs(i) ;
}
}
}
/*
5
1 2
1 3
1 4
1 5
*/
int findEgg (int N, vector < pair < int, int > > bridges)
{
int n = N ;
for(int i = 1 ; i <= n ; i ++) {
adj[i].clear() ;
vis[i] = 0 ;
}
a.clear() ;
for(int i = 0 ; i < bridges.size() ; i ++) {
int u = bridges[i].ff ;
int v = bridges[i].ss ;
adj[u].pb(v) ;
adj[v].pb(u) ;
}
dfs(1) ;
int l = 0 ;
int r = a.size() - 2 ;
int best = a.size()-1;
while(l <= r) {
int mid = (l + r) >> 1 ;
vector<int>midl ;
for(int i = 0 ; i <= mid ; i ++) {
midl.pb(a[i]) ;
}
if(query(midl) == 1) {
r = mid - 1 ;
best = mid ;
}
else {
l = mid + 1 ;
}
}
return a[best] ;
}
