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