#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000;
void dfs(int u, int p, int &timer, vector<int> &sp, const vector<vector<int>> &G){
sp[u] = timer++;
for(int c: G[u]){
if(c != p){
dfs(c, u, timer, sp, G);
}
}
}
int findEgg(int N, vector<pair<int,int>> bridges){
vector<vector<int>> G(N+1);
for(pair<int,int> e: bridges){
int u = e.first, v = e.second;
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> sp(N + 1);
int timer = 1;
dfs(1, 0, timer, sp, G);
vector<int> perm(N);
iota(perm.begin(), perm.end(), 1);
sort(perm.begin(), perm.end(), [&](int u, int v){
return sp[u] < sp[v];
});
// for(int item: perm) cout << item << '\n';
int L = 0, R = N - 1;
while(L < R){
int mid = (L + R) / 2;
vector<int> ques(perm.begin(), perm.begin() + mid + 1);
if(query(ques)) R = mid;
else L = mid + 1;
}
return perm[L];
}
