#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define a(k) begin(k), begin(k)
void dfs(int c, int par, vector<int>& p, vector<vector<int>>& adj){
p.push_back(c);
for (auto &e: adj[c])
if (e != par) dfs(e, c, p, adj);
}
int findEgg (int N, vector<pair<int, int>> bridges){
vector<vector<int>> adj(N+1);
for (auto &e: bridges){
adj[e.first].push_back(e.second);
adj[e.second].push_back(e.first);
}
vector<int> p;
dfs(1, 0, p, adj);
int l = 0, r = N-1;
while (l <= r){
int mid = (l+r)/2;
if (query(vector<int>(a(p) + mid))) r = mid - 1;
else l = mid + 1;
}
return p[l - 1];
}
