#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];
}
}
vector < int > cut(vector < int > v, int j){
vector < int > rs;
for(int i = 0; i <= j; i++)
rs.push_back(v[i]);
return rs;
}
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);
}
dfs(1, 0);
int l = 0, r = n - 1;
int best = -1;
while(r >= l){
int mid = (l + r) >> 1;
if(query(cut(x, mid))){
best = mid;
r = mid - 1;
}
else l = mid + 1;
}
return x[best];
}
/*
7
1 2
1 3
1 4
1 5
1 6
1 7
*/
