#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << " ----> " << x << endl;
#include "grader.h"
const int mxN = 1e6 + 5;
ll n;
vector<ll> v1[mxN],vv;
void dfs(ll at, ll par){
vv.pb(at);
for(auto it : v1[at]){
if(it == par) continue;
dfs(it, at);
}
}
int findEgg (int N, vector < pair < int, int > > bridges){
n = N;
for(int i = 1; i <= n; i++) v1[i].clear();
for(auto it : bridges){
v1[it.ff].pb(it.sd);
v1[it.sd].pb(it.ff);
}
vv.clear();
dfs(1, 1);
ll l = -1,r = n - 1;
while(r > l + 1){
ll mid = l + (r - l) / 2;
vector<int> q;
for(int i = 0; i <= mid; i++) q.pb(vv[i]);
if(!query(q)) l = mid;
else r = mid;
}
int ans = vv[r];
return ans;
}
