#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()
const int NM = 512;
int N;
vector <int> adj[NM+5];
vector <int> arr;
void dfs(int u, int p){
arr.push_back(u);
for (int v : adj[u]){
if (v == p) continue;
dfs(v, u);
}
}
int findEgg(int _N, vector <pii> bridges){
N = _N;
for (int i = 1; i <= N; i++) adj[i].clear();
for (pii p : bridges){
adj[p.fi].push_back(p.se);
adj[p.se].push_back(p.fi);
}
arr.clear();
dfs(1, -1);
int l = 0, r = N-2, res = N-1;
while (l <= r){
int mid = (l+r)/2;
vector <int> h = {};
for (int j = 0; j <= mid; j++) h.push_back(arr[j]);
if (query(h)){
res = mid;
r = mid-1;
}
else l = mid+1;
}
return arr[res];
}
