#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<vector<int>> v;
vector<int> ord, vis;
int n, t;
void dfs(int node) {
ord[++t] = node;
vis[node] = 1;
for(int son : v[node]) {
if(!vis[son]) {
dfs(son);
}
}
}
int check(int cnt) {
if(cnt > n) {
return 1;
}
vector<int> q;
for(int i=1; i<=cnt; ++i) {
q.push_back(ord[i]);
}
return query(q);
}
int findEgg(int N, vector<pair<int, int>> bridges) {
n = N;
v.assign(n+1, vector<int>());
ord.assign(n+1, 0);
vis.assign(n+1, 0);
t = 0;
for(auto [a, b] : bridges) {
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1);
int ans = 0;
for(int bit = 30 - __builtin_clz(n); bit >= 0; --bit) {
if(!check(ans + (1<<bit))) {
ans |= (1<<bit);
}
}
return ord[ans+1];
}
