#include "grader.h"
#include<bits/stdc++.h>
#define endl '\n'
#define ff first
#define ss second
using namespace std;
const int maxn = 5e5 + 5;
vector<int> s;
vector<int> adj[maxn];
vector<int> all;
void dfs(int u, int p){
all.push_back(u);
for(auto v : adj[u]){
if(v == p) continue;
dfs(v, u);
}
}
int findEgg(int N, vector<pair<int, int>> bridges){
all.clear();
for(int i = 1; i <= N; i++){
adj[i].clear();
}
for(int i = 0; i < bridges.size(); i++){
adj[bridges[i].ff].push_back(bridges[i].ss);
adj[bridges[i].ss].push_back(bridges[i].ff);
}
dfs(1, - 1);
vector<int> st;
int L = 0, R = N;
while(L + 1 < R){
int mid = (L + R) / 2;
if(query({all.begin(), all.begin() + mid})){
R = mid;
}
else{
L = mid;
}
}
return all[L];
}
