#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int MAXN = 550;
vector<int> adj[MAXN];
int pre[MAXN], cur;
vector<int> sorted_vtx;
bool make_query(int pos) {
vector<int> to_query;
for (int i = 0; i < pos; i++) {
to_query.push_back(sorted_vtx[i]);
}
return (bool) query(to_query);
}
void dfs(int v, int p) {
pre[v] = cur++;
sorted_vtx.push_back(v);
for (int w: adj[v]) {
if (w == p) continue;
dfs(w, v);
}
}
int findEgg(int N, vector<pair<int,int>> bridges) {
for (int i = 1; i <= N; i++) {
adj[i].clear();
pre[i] = -1;
}
sorted_vtx.clear();
cur = 0;
for (auto [a, b]: bridges) {
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, 0);
int l = 1, r = N;
while (l < r) {
int m = (l + r) / 2;
if (make_query(m)) r = m;
else l = m + 1;
}
return sorted_vtx[r - 1];
}
