#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
using pii = pair<int, int>;
const int N = 600;
int n;
bool mark[N];
vector<int> adj[N];
void dfs(int u, int p, int &m, vector<int> &islands) {
if (m == 0) return;
islands.push_back(u);
if (!mark[u]) m--;
for (int v : adj[u]) {
if (v == p) continue;
dfs(v, u, m, islands);
}
}
int findEgg (int N, vector<pair<int, int>> bridges) {
n = N;
for (int i = 1; i <= n; i++) mark[i] = false;
for (int i = 1; i <= n; i++) adj[i].clear();
for (auto [u, v] : bridges) {
adj[u].push_back(v);
adj[v].push_back(u);
}
int unknown = n;
while (unknown > 1) {
int mid = unknown / 2;
vector<int> islands;
dfs(1, -1, mid, islands);
vector<bool> isquery(n + 1);
for (int island : islands) {
isquery[island] = true;
}
if (query(islands)) {
for (int i = 1; i <= n; i++) {
if (!isquery[i]) {
if (!mark[i]) unknown--;
mark[i] = true;
}
}
}
else {
for (int i = 1; i <= n; i++) {
if (isquery[i]) {
if (!mark[i]) unknown--;
mark[i] = true;
}
}
}
}
for (int i = 1; i <= n; i++) {
if (!mark[i]) return i;
}
return -1;
}
