#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define SZ(x) ((int)(x).size())
//binaria
vector<int>adj[100000];
int tin[100000], node[100000];
int t = 0;
void dfs(int u, int p){
tin[u]= ++t;
node[t] = u;
for(auto v: adj[u])
if(v!= p)
dfs(v, u);
}
int findEgg(int N,vector<pair<int, int>>bridges){
for(auto x: bridges){
adj[x.first].push_back(x.second);
adj[x.second].push_back(x.first);
}
//tour
dfs(1,-1); //xdddddddddd
vector<int>islands;
int l = 1, r = N; int ans = 0;
while(l <= r){
int m = (l+r)/2;
while(SZ(islands) < m) islands.push_back(node[SZ(islands) + 1]);
while(SZ(islands) > m) islands.pop_back();
if(query(islands) ==1){
ans = node[m];
r = m-1;
}else{
l = m+1;
}
}
for(int i=1;i<=N;i++) adj[i].clear();
return ans;
}
