#include <bits/stdc++.h>
#include "grader.h"
// #include "grader.cpp"
using namespace std;
#define ll long long
#define N 6005
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sz(p) (int)p.size()
int m, l, r, a[N], vis[N], cnt;
vector <int> f[N], p;
void solve(int x) {
vis[x] = 1;
a[cnt] = x;
cnt++;
for(auto i : f[x]) {
if(vis[i]) continue;
solve(i);
}
}
int findEgg (int n, vector < pair < int, int > > bridges)
{
for(int i=1;i<=n;i++) {
vis[i] = a[i] = 0;
f[i].clear();
}
cnt = 1;
for(auto i:bridges) {
f[i.ff].pb(i.ss);
f[i.ss].pb(i.ff);
}
solve(1);
l = 1;
r = n;
int jog = 1;
while(l < r) {
int md = (l + r) / 2;
p.clear();
for(int i = 1; i <= md; i++) {
p.pb(a[i]);
}
int tt = query(p);
if(tt == 1){
r = md;
}
else l = md + 1;
}
// if(query({a[l]})) return a[l];
return a[l];
}
