#include "grader.h"
#include <bits/stdc++.h>
#define ii pair <int, int>
#define ll long long
#define llll pair <ll, ll>
#define ld long double
#define el "\n"
#define sp " "
#define fi first
#define se second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define __lcm(a, b) (a / __gcd(a, b) * b)
#define sq(x) (x) * (x)
#define sz(a) (int)(a.size())
using namespace std;
const int INFI = 1e9 + 7; const ll INFL = 2e18 + 7;
vector <int> g[515], tour;
void DFS(int node, int pre)
{
tour.pub(node);
for (int i : g[node])
{
if (i != pre) DFS(i, node);
}
}
int findEgg(int N, vector <pair <int, int>> bridges)
{
for (int i = 1; i <= N; i++) g[i].clear();
tour.clear();
for (int i = 0; i < N - 1; i++)
{
g[bridges[i].fi].pub(bridges[i].se);
g[bridges[i].se].pub(bridges[i].fi);
}
DFS(1, 1);
int le = 1, ri = N;
while (le <= ri)
{
int mi = le + ri >> 1;
if (query(vector <int>(tour.begin(), tour.begin() + mi))) ri = mi - 1;
else le = mi;
}
return tour[le - 2];
}
//coded by icyalmond
