#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int nax = 513;
vector<int>g[nax];
vector<int>order;
void dfs(int v, int p = 0) {
order.push_back(v);
for(int u : g[v]) if(u!=p) {
dfs(u, v);
}
}
int findEgg (int N, vector<pair<int,int>>bridges) {
for(int i=1; i<=N; ++i) {
g[i].clear();
}
order.clear();
for(int i=1; i<N; ++i) {
auto [u, v] = bridges[i-1];
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
int lo = 0, hi = N;
while(lo<hi-1) {
int mid = (lo+hi)/2;
vector<int>Qset = vector<int>(order.begin(), order.begin()+mid);
if(query(Qset)) {
hi = mid;
} else {
lo = mid;
}
}
return order[lo];
}
