#include <bits/stdc++.h>
#include "grader.h"
#define range(it, a, b) for (ll it = a; it < b; it++)
#define invr(it, a, b) for (ll it = a; it >= b; it--)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define ld long double
#define INF64 ((ll) 1 << 62)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
#define ptr(A) shared_ptr<A>
#define v(x) vector<x>
using namespace std;
v(v(int)) adj;
v(int) euler;
void euler_tour(ll i, ll p) {
euler.push_back(i);
for (int k : adj[i]) {
if (k == p)
continue;
euler_tour(k, i);
}
}
int findEgg (int N, vector < pair < int, int > > bridges) {
adj.clear();
adj.resize(N+1);
for (auto it : bridges) {
adj[it.first].push_back(it.second);
adj[it.second].push_back(it.first);
}
euler.clear();
euler_tour(1, 0);
int l = 0, r = N-1;
while (l < r) {
int m = (l + r) / 2;
v(int) st;
range(j, 0, m+1)
st.push_back(euler[j]);
if (query(st))
r = m;
else l = m+1;
}
return euler[l];
}
