#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 (int i = 0; i < N-1; i++){
adj[bridges[i].first].push_back(bridges[i].second);
adj[bridges[i].second].push_back(bridges[i].second);
}
vector<int> order, seen(N+1, 0);
queue<int> q;
q.push(1);
while (!q.empty()){
int n = q.front();
order.push_back(n);
seen[n] = 1;
for (int x : adj[n]){
if (!seen[x]){
q.push(x);
}
}
}
int ans;
int lo = 0, 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];
}
