#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg (int N, vector < pair < int, int > > bridges)
{
vector<int> g[N];
for (auto [a, b] : bridges) {
g[--a].push_back(--b);
g[b].push_back(a);
}
vector<int> A;
function<void(int,int)> dfs = [&](int u, int pu) {
A.push_back(u+1);
for (int v : g[u]) if (v != pu) dfs(v, u);
};
dfs(0,0);
int lo = 0, hi = N-1;
while (lo < hi) {
int mid = (lo + hi)/2;
if (query(vector<int>(A.begin(), A.begin()+mid+1))) hi = mid;
else lo = mid+1;
}
return A[hi];
}
