#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define pb push_back
const int mxN = 513;
vector<vector<int>> graph(mxN);
vector<int> wtf;
void dfs(int node, int parent) {
wtf.pb(node);
for(auto u : graph[node]) {
if(u != parent) {
dfs(u, node);
}
}
}
int findEgg (int N, vector<pair <int,int>>bridges) {
graph.resize(N + 1);
for(int i = 1; i <= N; i++) {
graph[i].clear();
}
for(int i = 0; i < N - 1; i++) {
graph[bridges[i].first].pb(bridges[i].second);
graph[bridges[i].second].pb(bridges[i].first);
}
dfs(1, 1);
// for(int i : wtf) cout << i << " ";
// cout << endl;
// baxaciqki ilk 1..mid araligindadi mi bizim easter egg
int ans = wtf[N-1], l = 0, r = N - 2;
while(l <= r) {
int mid = (l + r) / 2;
vector<int> ask;
for(int i = 0; i <= mid; i++) {
ask.pb(wtf[i]);
}
int elemi_olub = query(ask);
if(elemi_olub) {
ans = ask[(int)ask.size() - 1];
r = mid - 1;
} else {
l = mid + 1;
}
}
wtf.clear();
return ans;
}
