#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int n=5e3+50;
#define ii pair<int,int>
#define fr first
#define sr second
#define pb push_back
int tt,pth[n],cnt;
vector<int> adj[n];
void dfs(int u,int p){
pth[++cnt]=u;
for (auto x:adj[u]){
if (x==p) continue;
dfs(x,u);
}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
cnt=0;
memset(pth,0,sizeof pth);
for (int i=1;i<=N;i++) adj[i].clear();
for (auto &[x,y]:bridges){
adj[x].pb(y);
adj[y].pb(x);
}
int l=1,r=N;
dfs(1,0);
while (l<r){
int mid=(l+r)>>1;
vector<int> v;
for (int i=1;i<=mid;i++) v.pb(pth[i]);
if (query(v)) r=mid;
else l=mid+1;
}
return pth[l];
}
