#include <vector>
#include <algorithm>
using namespace std;
// Khai báo hàm query từ hệ thống
int query(vector<int> islands);
vector<int> adj[513];
vector<int> order;
// Hàm DFS để lấy thứ tự các nút
void dfs(int u, int p) {
order.push_back(u);
for (int v : adj[u]) {
if (v != p) {
dfs(v, u);
}
}
}
int findEgg(int N, vector<pair<int, int>> bridges) {
// Reset dữ liệu cho mỗi lần gọi findEgg
for (int i = 1; i <= N; i++) adj[i].clear();
order.clear();
// Xây dựng đồ thị
for (auto edge : bridges) {
adj[edge.first].push_back(edge.second);
adj[edge.second].push_back(edge.first);
}
// Bước 1: Duyệt DFS để có thứ tự tuyến tính
dfs(1, 0);
// Bước 2: Tìm kiếm nhị phân
int low = 0, high = N - 1, ans = order[N - 1];
while (low <= high) {
int mid = (low + high) / 2;
// Lấy các đảo từ order[0...mid]
vector<int> current_query;
for (int i = 0; i <= mid; i++) {
current_query.push_back(order[i]);
}
if (query(current_query)) {
ans = order[mid]; // Có thể là quả trứng này
high = mid - 1; // Thử tìm ở vị trí thấp hơn
} else {
low = mid + 1; // Trứng nằm ở phần còn lại
}
}
return ans;
}
