#include "grader.h"
#include <algorithm>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
vector<vector<int>> g(515);
vector<int> e;
void dfs(int v, int p) {
e.push_back(v);
for (int u : g[v]) {
if (u != p) {
dfs(u, v);
}
}
}
int findEgg(int N, vector<pair<int, int>> bridges) {
int n = N;
for (int i = 0; i < n; i++) {
g[i].clear();
}
e.clear();
for (int i = 0; i < n - 1; i++) {
g[bridges[i].second - 1].push_back(bridges[i].first - 1);
g[bridges[i].first - 1].push_back(bridges[i].second - 1);
}
dfs(0, 0);
int l = 0, r = n;
while (r - l > 1) {
int m = (l + r) / 2;
vector<int> q;
for (int i = 0; i <= m; i++) {
q.push_back(e[i] + 1);
}
if (query(q)) {
r = m;
}
else {
l = m;
}
}
return e[r] + 1;
}
