#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int n;
vector<int> adj[555], arr;
void dfs(int i, int p) {
arr.push_back(i);
for (int j : adj[i]) {
if (j == p) {
continue;
}
dfs(j, i);
}
}
int findEgg (int N, vector<pair<int, int>> bridges) {
int n = N;
for (int i = 1; i <= n; i++) {
adj[i].clear();
}
arr.clear();
for (auto [a, b] : bridges) {
adj[a].push_back(b);
adj[b].push_back(a);
}
int l = 1, r = n;
dfs(1, -1);
while(l < r) {
int m = (l+r)/2;
vector<int> b;
for (int i = 0; i < m; i++) {
b.push_back(arr[i]);
}
if (query(b)) {
r = m;
} else {
l = m+1;
}
}
return arr[l-1];
}
