#include <iostream>
#include <algorithm>
#include <vector>
const int MAXN = 512 + 1;
using namespace std;
int n;
std::vector<int> tree[MAXN];
std::vector<int> order;
void dfs(int node, int par)
{
order.push_back(node);
for(int to : tree[node])
{
if(to == par) continue;
dfs(to, node);
}
}
int query(vector<int> islands);
bool f(int idx)
{
std::vector<int> prefix;
for(int i = 0 ; i <= idx ; ++i)
{
prefix.push_back(order[i]);
}
return (bool)query(prefix);
}
int findEgg(int N, vector<pair<int,int>> bridges)
{
n = N;
for(int i = 1 ; i <= n ; ++i)
{
tree[i].clear();
}
order.clear();
for(auto &[a, b] : bridges)
{
tree[a].push_back(b);
tree[b].push_back(a);
}
dfs(1, -1);
int l = -1, r = n;
while(l + 1 < r)
{
int mid = (l + r) / 2;
if(f(mid)) r = mid;
else l = mid;
}
return order[r];
}
