#include <vector>
#include <algorithm>
using namespace std;
// query funksiyasi tashqarida e'lon qilingan deb hisoblaymiz
int query(vector<int> islands);
vector<int> adj[513];
vector<int> dfs_order;
// Daraxtni aylanish va tartibni saqlash
void dfs(int u, int p) {
dfs_order.push_back(u);
for (int v : adj[u]) {
if (v != p) {
dfs(v, u);
}
}
}
int findEgg(int N, vector<pair<int, int>> bridges) {
// Har bir chaqiriqdan oldin ma'lumotlarni tozalash
for (int i = 1; i <= N; i++) adj[i].clear();
dfs_order.clear();
// Grafni qurish
for (auto edge : bridges) {
adj[edge.first].push_back(edge.second);
adj[edge.second].push_back(edge.first);
}
// DFS tartibini olish (1-tugundan boshlab)
dfs(1, 0);
// DFS ro'yxati bo'yicha Binary Search
int low = 0, high = N - 1;
int ans = dfs_order[0];
while (low <= high) {
int mid = low + (high - low) / 2;
// Dastlabki 'mid + 1' ta elementni to'plamga olish
vector<int> current_set;
for (int i = 0; i <= mid; i++) {
current_set.push_back(dfs_order[i]);
}
if (query(current_set)) {
ans = dfs_order[mid]; // Tuxum shu oraliqda bo'lishi mumkin
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans;
}
