#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include "grader.h"
// #include <bits/stdc++.h>
#define in cin
#define out cout
using namespace std;
// int care;
// int query(vector<int> h){
// for(const int &x : h){
// if(x == care) return 1;
// }
// return 0; // check pe foaie daca e conex
// }
int add[520]; // intr-un fel ce 'pondere' au (1 - > nou, 0 - > incercat)
int ramase;
vector<int> guess;
vector<int> g[520];
int news = 0;
void dfs(int nod, int f){
guess.push_back(nod);
news += add[nod];
if(news == (ramase + 1) / 2) return;
for(const int &x : g[nod]){
if(x == f) continue;
dfs(x, nod);
if(news == (ramase + 1) / 2) return;
}
}
int findEgg(int n, vector < pair < int, int > > bridges){
for(int i = 0; i <= n; i++) add[i] = 1;
ramase = n;
for(const pair<int, int> &x : bridges){
g[x.first].push_back(x.second);
g[x.second].push_back(x.first);
}
while(ramase > 1){
dfs(1, -1);
// cerr << "guess : ";
// for(const int &x : guess) cerr << x << " ";
// cerr << '\n';
bool x = query(guess);
// cerr << " -- > x = " << x << " ramase = " << ramase << '\n';
if(x == 0){
for(const int &x : guess){
if(add[x]) ramase--;
add[x] = 0;
}
}else{
sort(guess.begin(), guess.end());
int it = 0;
for(int i = 1; i <= n; i++){
if(it < guess.size() && guess[it] == i){
it++; continue;
}
if(add[i]) ramase--;
add[i] = 0;
}
}
guess.clear();
news = 0;
}
int x = 0;
for(int i = 1; i <= n; i++){
if(add[i]) x = i;
}
return x;
}
