#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg (int N, vector<pair<int, int>> bridges) {
vector<vector<int>> adj(N);
for (auto [u, v]: bridges) {
adj[u - 1].push_back(v - 1);
adj[v - 1].push_back(u - 1);
}
vector<int> order;
auto dfs = [&](auto &&dfs, int node, int par = -1) -> void {
order.push_back(node + 1);
for (auto x: adj[node])
if (x != par)
dfs(dfs, x, node);
};
dfs(dfs, 0);
int l = 0, r = N;
while (r - l > 1) {
int m = (l + r) / 2;
bool ans = query(vector<int>(order.begin(), order.begin() + m));
if (ans) r = m;
else l = m;
}
return order[l];
}
