#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define pb push_back
constexpr int MAX = 569;
bool dead[MAX] = {};
vector<int> adj[MAX], order;
void dfs(int node, int par)
{
order.pb(node);
for (int to : adj[node])
if (to != par)
dfs(to, node);
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
order.clear();
for (int i = 1; i <= N; ++i)
adj[i].clear(), dead[i] = false;
for (auto &[u, v] : bridges)
adj[u].pb(v), adj[v].pb(u);
dfs(1, -1);
while (N > 1)
{
int mid = N >> 1;
int ctr = 0;
vector<int> v;
for (int x : order)
{
ctr += !dead[x];
v.pb(x);
if (ctr == mid)
break;
}
if (query(v))
{
bool ok = false;
for (int x : order)
{
if (ok)
dead[x] = true;
if (x == v.back())
ok = true;
}
N = mid;
}
else
{
for (int x : v)
dead[x] = true;
N -= mid;
}
}
for (int x : order)
if (!dead[x])
return x;
return -1;
}
