#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[1005], path;
void dfs(int u, int p)
{
path.push_back(u);
for (auto v : adj[u])
{
if (v == p)
{
continue;
}
dfs(v, u);
}
}
int findEgg(int N, vector<pair<int, int>> bridges)
{
path.clear();
for (int i = 0; i <= N; i++)
adj[i].clear();
for (auto [u, v] : bridges)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 1);
int l = 0, r = N - 1;
while (l < r)
{
int m = (l + r) / 2;
vector<int> tmp;
for (int i = 0; i <= m; i++)
{
tmp.push_back(path[i]);
}
if (query(tmp))
{
r = m;
}
else
{
l = m + 1;
}
}
return path[l];
}
