#include <iostream>
#include <vector>
using namespace std;
#include "grader.h"
vector<vector<int>> adj;
vector<int> couldBe;
vector<int> dfs(int st, int par, int targ){
vector<int> ans;
if(couldBe[st]) ans.push_back(st);
for(auto i : adj[st]){
if(i == par) continue;
if(targ == ans.size()) continue;
vector<int> v = dfs(i, st, targ - ans.size());
for(auto j : v) ans.push_back(j);
}
return ans;
}
int findEgg(int N, vector<pair<int, int>> bridges){
couldBe.assign(N, 1);
adj.assign(N, {});
for(auto i : bridges){
adj[i.first-1].push_back(i.second-1);
adj[i.second-1].push_back(i.first-1);
}
int pos = 1;
while(pos > 1){
vector<int> v = dfs(0, 0, pos/2);
for(int i = 0; i<v.size(); i++) v[i]--;
int a = query(v);
if(a){
couldBe.assign(N, 0);
for(auto i : v) couldBe[i-1] = 1;
}
else{
for(auto i : v) couldBe[i-1] = 0;
}
pos = 0;
for(auto i : couldBe) pos += i;
}
int ans = 0;
for(int i = 0; i<N; i++) if(couldBe[i]) ans = i+1;
return ans;
}
