#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int maxn = 512 + 10;
vector<int> g[maxn];
vector<int> order;
void dfs(int v = 1, int p = -1) {
for (int u : g[v]) {
if (u != p) {
dfs(u, v);
}
}
order.push_back(v);
}
int findEgg (int n, vector<pair<int, int>> bridges) {
for (int v = 1; v <= n; ++v) {
g[v].clear();
}
for (auto [v, u] : bridges) {
g[v].push_back(u);
g[u].push_back(v);
}
dfs();
reverse(order.begin(), order.end());
auto f = [&](int x) {
vector<int> temp;
for (int i = 0; i <= x; ++i) {
temp.push_back(order[i]);
}
return query(temp);
};
int l = -1, r = n - 1;
while (r - l > 1) {
int m = (l + r) / 2;
if (f(m)) {
r = m;
} else {
l = m;
}
}
return order[r];
}
