#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg(int N, vector<pair<int, int>> bridges) {
int n = N;
vector<vector<int>> tree(n);
vector<int> lb(n), ub(n);
function<void(int,int,int&)> Euler_tour = [&](int u, int pred, int & id) {
lb[u] = id++;
for (int v : tree[u])
if (v != pred)
Euler_tour(v, u, id);
ub[u] = id - 1;
};
for(auto [u, v] : bridges) {
u--, v--; // assuming input is 1-based
tree[u].push_back(v);
tree[v].push_back(u);
}
int root = 0, id = 0;
Euler_tour(root, -1, id);
vector<int> v(n);
for (int i = 0; i < n; i++) v[lb[i]] = i + 1;
int l = 0, r = n - 1;
while (l < r) {
int m = (r - l) / 2;
int up = (l + m + 1);
vector<int> ask;
for (int i = 0; i < up; i++) {
ask.push_back(v[i]);
}
bool b = query(ask); // call the function that answers
if (b)
r = up - 1;
else
l = up;
}
return v[l];
}
