#include<iostream>
#include<vector>
#include"grader.h"
using namespace std;
vector<int> euler1;
vector<int> adj[513];
vector<int> cur;
void DFS(int cur, int prev, vector<int> &euler)
{
euler.push_back(cur);
for(int next : adj[cur])
{
if(next != prev) DFS(next, cur, euler);
}
}
int findEgg(int N, vector<pair<int, int>> bridges)
{
euler1.reserve(N+1);
cur.reserve(N+1);
for(pair<int, int> edge : bridges)
{
adj[edge.first].push_back(edge.second);
adj[edge.second].push_back(edge.first);
}
DFS(1, 0, euler1);
int l = 0, r = N-1;
while(l < r)
{
int m = (l+r+1)/2;
for(int i = 0; i < m; i++)
{
cur.push_back(euler1[i]);
}
if(query(cur)) r = m-1;
else l = m;
for(int i = 0; i < m; i++) cur.pop_back();
}
return euler1[l];
}
