#include <vector>
#include <utility>
#include "grader.h"
const int MAX_N = 512;
std::vector<int> adj[MAX_N];
int ptr, order[MAX_N];
void clear_adj(int n) {
for(int i = 0; i < n; i++) {
adj[i].clear();
}
}
void dfs(int u, int prev = -1) {
order[ptr++] = u;
for(int v : adj[u]) {
if(v != prev) {
dfs(v, u);
}
}
}
bool found_egg(int pref) {
std::vector<int> q;
for(int i = 0; i <= pref; i++) {
q.push_back(order[i] + 1);
}
return query(q);
}
int findEgg(int n, std::vector<std::pair<int, int>> bridges) {
clear_adj(n);
for(std::pair<int, int> x : bridges) {
adj[x.first - 1].push_back(x.second - 1);
adj[x.second - 1].push_back(x.first - 1);
}
ptr = 0;
dfs(0);
int st = -1;
int dr = n - 1;
while(dr - st > 1) {
int mij = (st + dr) / 2;
if(found_egg(mij)) {
dr = mij;
} else {
st = mij;
}
}
return order[dr] + 1;
}
