#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int sz = 200000;
vector<int> g[sz];
int tin[sz], timer = 0;
void dfs(int u, int p) {
tin[++timer] = u;
for (auto &v : g[u]) {
if (v != p) {
dfs(v, u);
}
}
}
int findEgg (int N, vector<pair<int, int>> bridges)
{
timer = 0;
for (int i = 1; i <= N; i++) g[i].clear();
for (auto [x, y] : bridges) {
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, -1);
int low = 1, high = N - 1, best = N; // not my idea :(
while (low <= high) {
int mid = (low + high) >> 1;
vector<int> nodes;
for (int i = 1; i <= mid; i++) nodes.push_back(tin[i]);
if (query(nodes) == 1) {
high = mid - 1;
best = mid;
} else {
low = mid + 1;
}
}
return tin[best];
}
