#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
typedef long long lli;
typedef vector<lli> vi;
typedef pair<lli, lli> ii;
typedef vector<ii> vii;
#define f first
#define s second
#define pb push_back
#define sz(v) (v).size()
#define all(v) (v).begin(), (v).end()
#define SL '\n'
#define fore(a,b,c) for(lli a = (b), fgh = (c); a < fgh; a ++)
#define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void dfs(int pos, int par, vector<set<int>> &adj, vector<int> &tam){
tam[pos] = 1;
for(auto &i: adj[pos]){
if(i == par) continue;
dfs(i, pos, adj, tam);
tam[pos] += tam[i];
}
}
void subar(int pos, int par, vector<set<int>> &adj, vector<int> &q){
q.pb(pos+1);
for(auto &i: adj[pos]){
if(i == par) continue;
subar(i, pos, adj, q);
}
}
int findEgg(int N, vector<pair<int, int>> bridges){
int root = 0;
vector<set<int>> adj(N);
for(auto &i: bridges){
i.f --, i.s --;
adj[i.f].insert(i.s);
adj[i.s].insert(i.f);
}
vector<int> tam(N);
dfs(root, root, adj, tam);
while(tam[root] != 1){
int cent = root, par = root, sub, mx;
while(true){
sub = -1, mx = 0;
for(auto &i: adj[cent]){
if(i == par) continue;
if(tam[i] > mx){
mx = tam[i], sub = i;
}
}
if(sub == -1 or mx <= tam[root]/2) break;
par = cent, cent = sub;
}
vector<int> q;
subar(sub, cent, adj, q);
if(query(q)){
auto o = adj[sub].lower_bound(cent);
adj[sub].erase(o);
root = sub;
} else {
auto o = adj[cent].lower_bound(sub);
adj[cent].erase(o);
}
dfs(root, root, adj, tam);
}
return root+1;
}
