#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int timer = 0;
vector<int> inat, tour;
vector<vector<int>> graph;
void euler(int at, int prev) {
tour.push_back(at);
inat[at] = timer++;
for (auto v : graph[at]) {
if (v != prev) euler(v, at);
}
}
int findEgg(int N, vector<pair<int, int>> bridges) {
inat.resize(N + 1);
graph.resize(N + 1);
for (auto e : bridges) {
graph[e.first].push_back(e.second);
graph[e.second].push_back(e.first);
}
euler(1, -1);
int l = 0, r = N - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (query(vector<int>(tour.begin(), tour.begin() + mid)) == 1) {
r = mid - 1;
} else {
l = mid;
}
}
return tour[r];
}
