#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define sp " "
//#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define M 600
vector<int> adj[M];
bitset<M> vis, done;
int query (vector < int > h);
int ask(bitset<M> curr)
{
vector<int> v;
for (int i = 0; i < M; i++)
if (curr[i]) v.pb(i);
return query(v);
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
done.set();
for (int i = 1; i <= N; i++)
adj[i].clear();
for (auto i : bridges)
{
int u = i.st, v = i.nd;
adj[u].pb(v);
adj[v].pb(u);
}
int sz = N / 2, last = N;
while(last > 1)
{
vis.reset();
queue<int> q;
int sum = 0;
q.push(1);
while(!q.empty() && sum < sz)
{
int top = q.front();
q.pop();
if (vis[top]) continue;
vis[top] = 1;
sum += done[top];
for (auto i : adj[top])
{
if (vis[i] == 0) q.push(i);
}
}
/*
cout<<last<<sp<<sz<<endl;
for (int i = 1; i <= N; i++) cout<<vis[i];
cout<<endl;
*/
int res = ask(vis);
if (res == 1)
{
done &= vis;
last = sz;
sz /= 2;
}
else
{
vis.flip();
done &= vis;
last -= sz;
sz = last / 2;
}
/*
for (int i = 1; i <= N; i++) cout<<done[i];
cout<<endl<<endl;*/
}
for (int i = 1; i <= N; i++)
if (done[i]) return i;
return 0;
}
