#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 cur = 1, parent = -1;
while(true){
bool moved = false;
for(int v: adj[cur]){
if(v == parent) continue;
vector<int> ask;
for(int i = st[v]; i <= en[v]; i++)
ask.push_back(tour[i]);
if(query(ask)){
parent = cur;
cur = v;
moved = true;
break;
}
}
if(!moved) return cur;
}
}
