#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg (int n, vector < pair < int, int > > bridges){
int x = n;
int can[n + 1] = {}, in[n + 1] = {};
vector < int > ver;
vector < int > g[n + 1];
fill(can, can + n + 1, 1);
for(auto [x, y] : bridges) g[x].push_back(y), g[y].push_back(x);
function < void(int, int) > dfs = [&](int v, int p){
if(!x) return;
ver.push_back(v);
if(can[v]) in[v] = 1, x--;
for(int u : g[v])
if(u != p)
dfs(u, v);
};
while(x > 1){
int val = x; ver.clear();
for(int i = 1; i <= n; i++) in[i] = 0;
x >>= 1, dfs(1, -1);
// cout << "ver ";
// for(int v : ver) cout << v << ' ';
// cout << "<--- " << query(ver) << '\n';
if(query(ver)){
for(int i = 1; i <= n; i++) can[i] &= in[i];
x = val / 2;
}
else{
for(int i = 1; i <= n; i++) can[i] &= (in[i] ^ 1);
x = val - val / 2;
}
// cout << "case " << val << ' ' << x << '\n';
// for(int i = 1; i <= n; i++) cout << can[i] << ' ';
// cout << '\n';
}
for(int i = 1; i <= n; i++)
if(can[i])
return i;
return -1;
}
