#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector < int > x;
map < int , int > sub, par;
map < int , set < int > > adj;
void dfs(int u, int p){
sub[u] = 1;
par[u] = p;
x.push_back(u);
for(auto v : adj[u]){
if(v == p)
continue;
dfs(v, u);
sub[u] += sub[v];
}
}
int findEgg(int n, vector < pair < int, int > > bridges){
for(auto e : bridges){
int u = e.first;
int v = e.second;
adj[u].insert(v);
adj[v].insert(u);
}
set < int > nodes;
for(int i = 1; i <= n; i++)
nodes.insert(i);
int tt = 10;
while((int)nodes.size() > 1){
// tt--;
// if(!tt)break;
sub.clear();
par.clear();
int U = *nodes.begin();
dfs(U, 0);
int nn = nodes.size(), mx = 0, cen;
for(auto i : nodes){
int up = nn - sub[i];
int dw = sub[i];
if(up * dw > mx){
mx = up * dw;
cen = i;
}
}
x.clear();
// cout << cen << endl;
dfs(cen, par[cen]);
// for(auto i : x)
// cout << i << ' ';
// cout << endl;
if(query(x)){
vector < int > xx;
for(auto i : nodes){
if(count(x.begin(), x.end(), i) == 0)
xx.push_back(i);
}
x = xx;
}
for(auto i : x)nodes.erase(i);
for(int i = 0; i <= n; i++)adj[i].clear();
for(auto e : bridges){
int u = e.first;
int v = e.second;
if(!nodes.count(u) || !nodes.count(v))
continue;
adj[u].insert(v);
adj[v].insert(u);
}
}
return *nodes.begin();
}
/*
5
1 2
1 3
2 4
4 5
*/
