#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<vector<int>> g;
vector<int> order;
void dfs(int v, int prev, vector<int> &order, vector<vector<int>> &g)
{
order.push_back(v);
for(int i : g[v])
{
if(i == prev)continue;
dfs(i, v, order, g);
}
}
int query(vector < int > islands);
int findEgg(int n, vector<pair<int, int>> bridges)
{
g.clear();
order.clear();
g.resize(n+1);
for(auto &[u, v] : bridges)
{
g[u].push_back(v);
g[v].push_back(u);
}
order.push_back(0);
dfs(1, 0, order, g);
int l = 1, r = n;
while(l < r)
{
int mid = (l + r) >> 1;
if(query(vector<int> (order.begin()+1, order.begin() + mid + 1)))
r = mid;
else
l = mid + 1;
}
return order[l];
}
