#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 tin[MAXN];
int timer;
void dfs(int u, int p)
{
tin[u] = ++timer;
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 = 0; i < n - 1; i++)
{
adj[edges[i].first].push_back(edges[i].second);
adj[edges[i].second].push_back(edges[i].first);
}
dfs(1, 1);
int left = 0;
int right = timer + 1;
int mid;
while(right - left > 1)
{
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;
else
left = mid;
}
for(int i = 1; i <= n; i++)
{
adj[i].clear();
}
timer = 0;
return ord[right];
}
