#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int> v;
vector<int> adj[600];
void dfs(int x, int par){
v.push_back(x);
for (auto it : adj[x]){
if (it != par) dfs(it, x);
}
}
int findEgg(int N, vector<pair<int, int>> bridges){
v.clear();
for (int i=1; i<=N; i++) adj[i].clear();
for (auto [x, y] : bridges) adj[x].push_back(y), adj[y].push_back(x);
v.push_back(1e9);
dfs(1, -1);
int lo = 1, hi = N, ans = N+1;
while (lo <= hi){
int mid = (lo+hi)>>1;
if (lo == hi) return v[mid];
vector<int> isl;
for (int i=1; i<=mid; i++) isl.push_back(v[i]);
int res = query(isl);
if (res == 0) lo = mid+1;
else hi = mid-1, ans = v[mid];
}
return ans;
}
