#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<vector<int>> at_depth, adj;
vector<int> from, dist;
void dfs(int v, int p, bool save) {
if (save) at_depth[dist[v]].push_back(v);
for (auto u: adj[v]) if (u!=p) {
dist[u] = dist[v]+1;
from[u] = v;
dfs(u, v, save);
}
}
int findEgg(int N, vector <pair<int, int>> bridges) {
from.assign(N, 0);
dist = from;
adj.assign(N, {});
at_depth = adj;
for (int i=0; i<N-1; i++) {
auto [u, v] = bridges[i];
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
/*
dfs(0, -1, 0);
int s = 0;
for (int i=0; i<N; i++) if (dist[i]>dist[s]) s = i;
dist[s] = 0;
dfs(s, -1, 0);
int e = s;
for (int i=0; i<N; i++) if (dist[i]>dist[e]) e = i;
for (int i=0; i<dist[e]/2; i++) {
e = from[e];
} */
int e = 0;
dist[e] = 0;
dfs(e, -1, 1);
int r = N-1;
int l = -1;
while (r-l>1) {
int m = (r+l)/2;
vector<int> st;
for (int i=0; i<=m; i++) for (auto v: at_depth[i]) st.push_back(v+1);
if (query(st)) r = m;
else l = m;
}
vector<int> a;
if (a.size()==0) return N;
for (auto v: at_depth[r]) a.push_back(v+1);
while (a.size()>1) {
vector<int> b;
while (a.size()>b.size()) {
b.push_back(a.back());
a.pop_back();
}
if (query(b)) a = b;
}
return a[0];
}
