#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<vector<int>> v;
vector<int> ord;
int n, t;
void dfs(int node) {
ord[node] = ++t;
for(int son : v[node]) {
if(!ord[son]) {
dfs(son);
}
}
}
int check(int cnt) {
vector<int> q;
for(int i=1; i<=cnt; ++i) {
q.push_back(ord[i]);
}
return query(q);
}
int findEgg(int N, vector<pair<int, int>> bridges) {
n = N;
v.assign(n+1, vector<int>());
ord.assign(n+1, 0);
t = 0;
for(auto [a, b] : bridges) {
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1);
int st = 1, dr = n, mij;
while(st <= dr) {
mij = (st+dr>>1);
if(check(mij)) {
dr = mij - 1;
} else {
st = mij + 1;
}
}
return ord[dr+1];
}
