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