#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int n, cnt = 1, f, vis[1000];
vector<int> g[1000], ask = {1};
set<int> can;
void dfs(int u){
if(u != 1 && !vis[u]){
ask.push_back(u);
//cout << u << ' ';
}
vis[u] = 1;
for(auto v : g[u]){
if(!vis[v] && cnt != f && can.find(v) != can.end()){
++cnt;
dfs(v);
}
}
}
int findEgg (int N, vector < pair < int, int > > e){
memset(vis, 0, sizeof vis);
cnt = 1;
ask = {1};
for(int i = 0;i<1000;i++){
g[i].clear();
}
n = N;
for(auto [u, v] : e){
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 1;i<=n;i++) can.insert(i);
int l = 1, r = n;
bool in = false;
int fr = 1;
while(1){
if(!in){
f = (l + r) / 2;
for(auto x : ask){
can.erase(x);
dfs(x);
}
if(fr) can.insert(1);
in = query(ask);
fr = 0;
if(!in){
l = f + 1;
}
}else{
r = f;
f = (l + r) / 2;
//cout << l << ' ' << r << '\n';
cnt = f;
for(int i = 1;i<=n;i++){
bool g = 0;
for(auto x : ask) if(x == i) g = 1;
if(!g) can.erase(i);
}
while(ask.size() > f) vis[ask.back()] = 0, ask.pop_back();
in = query(ask);
}
// for(auto x : ask) cout << x << ' ';
// cout << '\n';
// for(auto x : can) cout << x << ' ';
// cout << '\n';
if(can.size() == 1) return *can.begin();
}
return 0;
}
