#include "grader.h"
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
#define endl '\n'
const int maxv = 1e3;
vector<int> edges[maxv];
vector<int> in;
bool visited[maxv];
bool check(int mid) {
vector<int> p;
for (int i = 0; i <= mid; i++)
p.push_back(in[i]);
return query(p);
}
void dfs(int start) {
in.push_back(start);
visited[start] = true;
for (int next : edges[start])
if (!visited[next])
dfs(next);
}
int bin_search() {
dfs(1);
int l = 0, r = in.size() - 1;
int mid;
while (l < r) {
mid = (l + r) / 2;
if (check(mid))
r = mid;
else
l = mid + 1;
}
return in[r];
}
void clear() {
for (int i = 0; i < maxv; i++)
edges[i].clear();
memset(visited, false, sizeof(visited));
in = {};
}
int findEgg(int n, vector<pair<int, int>> bridges) {
clear();
for (auto &[u, v] : bridges) {
edges[u].push_back(v);
edges[v].push_back(u);
}
return bin_search();
}
