#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<vector<int>> adj;
int findEgg(int N, vector <pair<int, int>> bridges) {
adj.assign(N, {});
for (int i=0; i<N-1; i++) {
auto [u, v] = bridges[i];
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<array<int, 2>> q; // (v, p
q.push_back({0, -1});
for (int i=0; i<q.size(); i++) {
auto [v, p] = q[i];
for (auto u: adj[v]) if (u!=p) q.push_back({u, v});
}
int l = -1, r= N-1;
while (r-l>1) {
int m = (r+l)/2;
vector<int> a;
for (int i=0; i<=m; i++) a.push_back(q[i][0]+1);
if (query(a)) r = m;
else l = m;
}
return q[r][0]+1;
}
