#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int n;
vector<int> sz;
vector<vector<int>> g;
void dfs_sz(int u, int p) {
sz[u] = 1;
for (auto v : g[u]) {
if (v != p) {
dfs_sz(v, u);
sz[u] += sz[v];
}
}
}
int centroid(int u, int p) {
for (auto v : g[u]) {
if (v != p && sz[v] * 2 > n) {
return centroid(v, u);
}
}
return u;
}
vector<int> sub;
void subtree(int u, int p) {
sub.push_back(u);
for (auto v : g[u]) {
if (v != p) {
subtree(v, u);
}
}
}
int dfs(int u, int p) {
for (auto v : g[u]) {
if (v == p) continue;
subtree(v, u);
int res = query(sub);
sub.clear();
if (res) {
return dfs(v, u);
}
}
return u;
}
int findEgg (int N, vector<pair<int, int>> bridges) {
n = N;
g.assign(n + 1, vector<int>());
sz.assign(n + 1, 0);
for (auto [u, v] : bridges) {
g[u].push_back(v);
g[v].push_back(u);
}
dfs_sz(1, 0);
int c = centroid(1, 0);
return dfs(centroid(1, 0), 0);
}
