#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int MAXN = (1 << 9) + 10;
int n;
vector < int > adj[MAXN];
int ord[MAXN];
int timer;
void dfs(int u, int p)
{
ord[++timer] = u;
for(int& v : adj[u])
{
if(v == p)
continue;
dfs(v, u);
}
}
int findEgg (int N, vector < pair < int, int > > edges)
{
n = N;
for(int i = 1; i <= n; i++)
{
adj[i].clear();
}
for(int i = 0; i < n - 1; i++)
{
adj[edges[i].first].push_back(edges[i].second);
adj[edges[i].second].push_back(edges[i].first);
}
timer = 0;
dfs(1, 1);
int left = 1;
int right = n - 1;
int mid;
int ans = -1;
while(left <= right)
{
mid = left + (right - left) / 2;
vector < int > p;
for(int i = 1; i <= mid; i++)
{
p.push_back(ord[i]);
}
if(query(p))
{
right = mid - 1;
ans = mid;
}
else
{
left = mid + 1;
}
}
if(ans == -1)
ans = n;
return ord[ans];
}
