#include<bits/stdc++.h>
using namespace std;
#define int signed
#define i32 signed
#define X first
#define Y second
#define pb push_back
using pii = pair<int,int>;
#define vt vector
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define f0r(i,a,b) for(auto i = (a); i != (b); i++)
#define r0f(i,a,b) for(auto i = (a); i >= (b); i--)
#define debug(x) {auto _x=x;cerr<<#x<<": "<<_x<<'\n';};
vt<vt<int>> tr;
vt<int> ord;
int n;
//dfs to get ord array
i32 query(vt<int> islands);
void dfs(int u,int par = -1) {
ord.pb(u);
for(int v : tr[u]) if(v != par) {
dfs(v,u);
}
}
int findEgg(i32 N, vt<pair<i32,i32>> bridges) {
n = N;
tr = vt<vt<int>> (N+1);
for(auto [u,v] : bridges) {
tr[u].pb(v);
tr[v].pb(u);
}
ord.clear();
dfs(1);
int lo = 1, hi = N;
while(lo < hi) {
int mid = (lo+hi)/2;
vt<int> eggs;
f0r(i,0,mid) {
eggs.pb(ord[i]);
}
if(query(eggs)) {
hi = mid;
} else {
lo = mid+1;
}
}
//narrowed it down to 1? no need to check anymore.
return ord[lo-1];
}
