#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int mxN = 512 + 10;
vector<int> adj[mxN];
vector<int> lt;
void reset(int n){
lt.clear();
for(int i = 1; i <= n; ++i) adj[i].clear();
}
void dfs(int u = 1, int par = 0){
lt.push_back(u);
for(auto it : adj[u]){
if(it ^ par){
dfs(it, u);
}
}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
reset(N);
for(auto [u, v] : bridges){
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs();
int st = 0, en = N - 1, ans = 0;
while(st <= en){
int mid = (st + en) / 2;
vector<int> ltc;
for(int j = 0; j <= mid; ++j) ltc.push_back(lt[j]);
if(query(ltc)) ans = ltc.back(), en = mid - 1;
else st = mid + 1;
}
return ans;
}
