#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> a;
vector<vector<int>> g;
void dfs(int node, int par){
a.push_back(node);
for(auto i: g[node]){
if(i!=par){
dfs(i, node);
}
}
}
int findEgg(int n, vector<pair<int, int>> bridges){
g.assign(n+1, {});
a.clear();
for(auto [u, v]: bridges){
g[u].push_back(v);
g[v].push_back(u);
}dfs(1, 0);
int l = 0, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (query({a.begin(), a.begin() + mid})) {
r = mid;
} else {
l = mid;
}
}return a[l];
}
