#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int NMAX = 515;
vector<int> G[NMAX], dfs_pref;
void dfs(int u, int parent) {
dfs_pref.emplace_back(u);
for(const int &v : G[u])
if(v != parent)
dfs(v, u);
}
void Clear(int N) {
for(int u = 1; u <= N; ++u)
G[u].clear();
dfs_pref.clear();
dfs_pref.emplace_back(0);
}
bool check(int poz) {
vector<int> ask;
for(int i = 1; i <= poz; ++i)
ask.emplace_back(dfs_pref[i]);
return query(ask);
}
int findEgg(int N, vector<pair<int,int>> bridges) {
Clear(N);
for(int i = 0; i < N - 1; ++i) {
int u, v;
tie(u, v) = bridges[i];
G[u].emplace_back(v);
G[v].emplace_back(u);
}
dfs(1, 0);
int st = 1, dr = N - 1, ans = N;
while(st <= dr) {
int mid = (st + dr) >> 1;
if(check(mid)) {
ans = mid;
dr = mid - 1;
}
else
st = mid + 1;
}
return dfs_pref[ans];
}
