//#include "grader.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <set>
//#define int long long
#define ff first
#define ss second
#define pb push_back
#define pp pop_back
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define r0 return 0
using namespace std;
const int N = 5 * 1e5 + 5, M = 55, MOD = 998244353;
int x,y,xx,yy,n,m,k,l,ans,tm;
vector <int> g[N],rd;
int fix[N],tc[N];
void dfs (int x) {
fix[++tm] = x;
tc[x] = 1;
for (auto to : g[x]) {
if (tc[to] == 1) continue;
rd.pb(to);
dfs(to);
}
}
int query (vector <int> islands);
int check (int mid) {
vector <int> h;
for (int i = 1; i <= mid; i++) {
h.pb(fix[i]);
}
return query(h);
}
int findEgg(int N, vector <pii> bridges){
n = N;
for (int i = 1; i <= n; i++) {
g[i].clear();
fix[i] = 0;
tc[i] = 0;
}
for (pii to : bridges) {
g[to.ff].pb(to.ss);
g[to.ss].pb(to.ff);
}
tm = 0;
dfs(1);
int l = 1,r = n - 1, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (ans == -1) {
return fix[n];
} else {
return fix[ans];
}
return ans;
}
