#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int MAXN = (1 << 9) + 3;
int del[MAXN], sz[MAXN], dp[MAXN], p1, p2, diff;
vector < int > g[MAXN], part[MAXN];
void calc(int v, int p = -1){
sz[v] = 1;
for(int u : g[v])
if(u != p && !del[u])
calc(u, v), sz[v] += sz[u];
}
void upd(int v, int p, int s){
for(int u : g[v]){
if(!del[u] && u != p){
upd(u, v, s);
if(abs(sz[u] * 2 - s) < diff){
diff = abs(sz[u] * 2 - s);
p1 = v, p2 = u;
}
}
}
}
void add(int v, int p, vector < int > &x){
x.push_back(v);
for(int u : g[v])
if(u != p && !del[u])
add(u, v, x);
}
int centroid(int v){
calc(v);
if(sz[v] == 1) return v;
diff = sz[v], p1 = p2 = 0;
upd(v, -1, sz[v]);
vector < int > v1, v2;
add(p1, p2, v1);
add(p2, p1, v2);
if(query(v1)){
for(int x : v2) del[x] = 1;
return centroid(v1.back());
}
else{
for(int x : v1) del[x] = 1;
return centroid(v2.back());
}
}
int findEgg (int n, vector < pair < int, int > > bridges){
for(int i = 1; i <= n; i++) g[i].clear(), part[i].clear(), sz[i] = del[i] = 0, dp[i] = -1;
for(auto [x, y] : bridges) g[x].push_back(y), g[y].push_back(x);
return centroid(1);
}
