#include <bits/stdc++.h>
#include "grader.h"
#define f first
#define s second
using namespace std;
int n;
vector<int> preord;
vector<int> grph[690];
void dfs(int x, int lst=-1) {
preord.push_back(x);
for (int i : grph[x]) if (i!=lst) {
dfs(i,x);
}
}
bool test(int x) {
vector<int> t;
for (int i=0; i<x; i++) {
t.push_back(preord[i]+1);
}
return query(t);
}
int findEgg (int N, vector<pair<int,int>> bridges) {
n=N;
for (auto i:bridges) {
i.f--;i.s--;
grph[i.f].push_back(i.s);
grph[i.s].push_back(i.f);
}
dfs(0);
int s=0,e=n;
while(s+1!=e) {
int m=(s+e)/2;
(test(m)?e:s)=m;
}
return preord[s]+1;
}
