#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define pb push_back
vector<int> adj[512 + 5];
vector<int> x;
void dfs(int node, int par){
x.pb(node);
for(int to : adj[node]){
if(to != par){
dfs(to, node);
}
}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
for(int i = 1; i <= N; i++){
adj[i].clear();
}
x.clear();
for(auto i : bridges){
adj[i.first].pb(i.second);
adj[i.second].pb(i.first);
}
dfs(1, 0);
int best = N;
int l = 1, r = N;
while(l <= r){
int mid = (l + r) / 2;
bool b = query(vector<int>(x.begin(), x.begin() + mid));
if(b){
r = mid - 1;
}else{
best = mid;
l = mid + 1;
}
}
return best;
}
