#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int n, cnt = 1, f, vis[1000], frr = 1;
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};
can.clear();
n = N;
if(frr){
for(auto [u, v] : e){
g[u].push_back(v);
g[v].push_back(u);
}
}
frr = 0;
for(int i = 1;i<=n;i++) can.insert(i);
int l = 1, r = n;
bool in = false;
int fr = 1;
while(can.size() != 1){
if(!in){
f = (l + r) / 2;
for(auto x : ask){
can.erase(x);
}
for(auto x : ask){
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 && ask.size() > 1) 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.empty()) return 1;
return (int)(*can.begin());
}
