#include <vector>
#include <algorithm>
using namespace std;
int query(vector<int> islands);
vector<int> adj[513];
vector<int> order;
bool visited[513];
// DFS để tạo thứ tự đảm bảo tính liên thông cho mọi tiền tố
void dfs(int u) {
visited[u] = true;
order.push_back(u);
for (int v : adj[u]) {
if (!visited[v]) {
dfs(v);
}
}
}
int findEgg(int N, vector<pair<int, int>> bridges) {
// Reset dữ liệu sạch sẽ cho mỗi test case (quan trọng vì có tối đa 60 findEgg)
for (int i = 1; i <= N; i++) {
adj[i].clear();
visited[i] = false;
}
order.clear();
for (auto edge : bridges) {
adj[edge.first].push_back(edge.second);
adj[edge.second].push_back(edge.first);
}
dfs(1);
// Chặt nhị phân trên số lượng phần tử của mảng order
// Chúng ta biết trứng chắc chắn nằm trong [0, N-1]
int low = 0, high = N - 2; // Chỉ cần check đến N-2
int ans = N - 1; // Mặc định là phần tử cuối cùng
while (low <= high) {
int mid = (low + high) / 2;
vector<int> current_query;
for (int i = 0; i <= mid; i++) {
current_query.push_back(order[i]);
}
if (query(current_query)) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return order[ans];
}
