#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
using pii = pair<int, int>;
bool my_query(const set<int> &s) {
if (s.empty()) return 0;
vector<int> v;
for (auto &it : s)
v.push_back(it);
return query(v);
}
int findEgg(int n, vector<pii> bridges) {
vector<vector<int>> g(n + 1);
vector<bool> vis(n + 1);
vector<int> euler;
for (auto [ x, y ] : bridges) {
g[x].push_back(y);
g[y].push_back(x);
}
function<void(int)> dfs = [&](int x) {
vis[x] = true;
euler.push_back(x);
for (auto u : g[x]) {
if (!vis[u]) {
dfs(u);
euler.push_back(x);
}
}
};
dfs(1);
function<bool(int)> check = [&](int mid) {
set<int> s;
for (int i = 0; i < mid; i++)
s.insert(euler[i]);
return my_query(s);
};
int mask = 0;
for (int i = log2(euler.size()); i >= 0; i--) {
mask |= 1 << i;
if (mask >= int(euler.size()) - 1 || check(mask)) mask ^= 1 << i;
}
return euler[mask];
}
