#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
const int maxn = 1e5 + 1;
#define pii pair<int, int>
#define ll long long
#define pq priority_queue
#define se second
#define fi first
int query(vector<int> dao);
vector<int> adj[maxn];
int tour[maxn], st[maxn], en[maxn];
int m = 0;
int root = 1;
vector<int> ask;
void dfs(int u, int p) {
tour[++m] = u;
st[u] = m;
en[u] = m;
for(int v : adj[u]) {
if(v != p){
dfs(v, u);
}
}
en[u] = m;
}
int findEgg(int n, vector<pii> g) {
for(auto [u, v] : g) {
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, -1);
int l = 1, r = n;
while(l < r) {
int mid = (l + r)/2;
ask.clear();
for(int i = l; i <= mid; i++) {
ask.push_back(tour[i]);
}
int ok = query(ask);
if(ok) r = mid;
else l = mid + 1;
}
return tour[l];
}
