#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))
int findEgg (int N, vector < pair < int, int > > bridges)
{
int n=N;
vii a(n);
REP(i,0,n-1){
a[bridges[i].F-1].PB(bridges[i].S-1);
a[bridges[i].S-1].PB(bridges[i].F-1);
}
vi vis(n,0);
vi arr;
queue<int> pq;
pq.push(0);
while(!pq.empty()){
int x=pq.front();
pq.pop();
if(vis[x])continue;
vis[x]=1;
arr.PB(x);
for(auto u:a[x])pq.push(u);
}
int l=0,r=n-1;
while(l<r){
int m=(l+r)/2;
vi b;
REP(i,0,m+1)b.PB(arr[i]+1);
if(!query(b))l=m+1;
else r=m;
}
return arr[l]+1;
}
