#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
int findEgg (int N, vector < pair < int, int > > bridges)
{
vector<vector<int>> a(N);
for (auto &[x, y] : bridges) --x, --y, a[x].emplace_back(y), a[y].emplace_back(x);
vector<int> g;
auto dfs = [&](auto &dfs, int v, int p) -> void{
g.emplace_back(v);
for (int u : a[v]) if (u != p) dfs(dfs, u, v);
};
dfs(dfs, 0, -1);
int l = 0, r = g.size() - 1, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (query(vector<int>(g.begin(), g.begin() + mid))) ans = mid, r = mid - 1;
else l = mid + 1;
}
return g[ans];
}
