#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
void dfs (int i, int j, vector<vector<int>> &adj, vector<int> &order){
order.push_back(i);
for (int k : adj[i])
if (k != j)
dfs(k, i, adj, order);
}
bool _query (int k, vector<int> &vt){
vector<int> vt2;
for (int i = 0; i < k; i++)
vt2.push_back(vt[i]+1);
return query(vt2);
}
int findEgg (int n, vector<pair<int, int>> edges){
vector<vector<int>> adj(n);
for (auto i : edges){
adj[i.f-1].push_back(i.s-1);
adj[i.s-1].push_back(i.f-1);
}
vector<int> ord;
int ans = 0;
dfs(0, -1, adj, ord);
for (int i = n <= 16 ? 4 : 9; i--;)
if (ans+(1<<i) <= n && !_query(ans+(1<<i), ord))
ans += 1<<i;
return ord[ans]+1;
}
