#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int MAXN = 520;
vector<int> adj[MAXN];
int state[MAXN]; // 0 still possible, 1 top out, 2 bottom out
vector<int> test;
int target;
void dfs(int x, int par){
if (state[x] == 2) return;
test.push_back(x);
if (state[x] == 0) target--;
for (int nxt : adj[x]){
if (target == 0) break;
if (nxt == par) continue;
dfs(nxt, x);
}
}
int findEgg (int N, vector<pair<int, int>> edges){
for (int i = 1; i <= N; i++){
adj[i].clear();
state[i] = 0;
}
for(auto e : edges){
int a, b; tie(a, b) = e;
adj[a].push_back(b);
adj[b].push_back(a);
}
int poss = N;
while (poss > 1){
target = poss / 2;
test.clear();
dfs(1, -1);
vector<bool> tested(N + 1, 0);
for (int x : test) tested[x] = 1;
if (query(test)){
for (int i = 1; i <= N; i++)
if (state[i] == 0 && !tested[i]){
state[i] = 2;
poss--;
}
}
else{
for (int i = 1; i <= N; i++)
if (state[i] == 0 && tested[i]){
state[i] = 1;
poss--;
}
}
}
for (int i = 1; i <= N; i++)
if (state[i] == 0)
return i;
return -1;
}
