#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg(int N, vector<pair<int, int>> bridges){
vector<vector<int>> adj(N+1);
for (auto [a, b] : bridges){
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<int> order, seen(N+1, 0);
queue<int> q;
q.push(1);
while (!q.empty()){
int n = q.front();
q.pop();
order.push_back(n);
seen[n] = 1;
for (int x : adj[n]){
if (!seen[x]){
q.push(x);
}
}
}
int ans;
int lo = -1, hi = N-1, mid;
while (lo + 1 < hi){
mid = (lo + hi) / 2;
vector<int> s;
for (int i = 0; i <= mid; i++){
s.push_back(order[i]);
}
if (query(s)){
hi = mid;
} else {
lo = mid;
}
}
return order[hi];
}
