#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<vector<int>> adjL;
vector<int> path;
void dfs(int u,int p=-1){
path.push_back(u);
for(int v:adjL[u]){
if(v==p)continue;
dfs(v,u);
}
}
bool cando(int x){
vector<int> ans;
for(int i=0;i<=x;i++)ans.push_back(path[i]);
return query(ans);
}
int findEgg (int N, vector < pair < int, int > > bridges){
path.clear();
adjL.clear();
adjL.resize(N+1);
//cout<<"HEY\n";
for(const auto &[u,v]:bridges){
adjL[u].push_back(v);
adjL[v].push_back(u);
}
dfs(1);
int l=0,r = path.size()-1;
for(int b=(r>1?r/2:1);b>0;b>>=1ll){
while(r-b>=l && cando(r-b))r-=b;
}
return path[r];
}
