#include <bits/stdc++.h>
#include "grader.h"
#define MAX 512
using namespace std;
vector <int> graph[MAX + 10];
vector <int> nodes;
void dfs(int node, int parent)
{
nodes.push_back(node);
for (auto next : graph[node])
if (next != parent)
dfs(next, node);
}
int check(int pos)
{
vector <int> nodesQuery;
for (int i = 0; i < pos; i++)
nodesQuery.push_back(nodes[i]);
return query(nodesQuery);
}
int findEgg (int N, vector <pair <int, int>> bridges)
{
for (int i = 1; i <= N; i++)
graph[i].clear();
nodes.clear();
for (auto it : bridges)
{
graph[it.first].push_back(it.second);
graph[it.second].push_back(it.first);
}
dfs(1, -1);
int left = 0;
int right = nodes.size();
while (left + 1 < right)
{
int mid = (left + right) / 2;
if (check(mid) == 1)
right = mid;
else
left = mid;
}
return nodes[right - 1];
}
