#include<iostream>
#include<vector>
#include"grader.h"
using namespace std;
int euler[1000];
vector<int> adj[1000];
vector<int> cur;
int timer = 0;
void DFS(int cur, int prev)
{
euler[timer] = cur;
timer++;
for(int next : adj[cur])
{
if(next != prev) DFS(next, cur);
}
}
int findEgg(int N, vector<pair<int, int>> bridges)
{
for(int i = 1; i <= N; i++) adj[i].clear();
cur.clear();
fill(euler, euler+999, 0);
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;
while(!cur.empty()) cur.pop_back();
}
return euler[l];
}
