#include <vector>
#include "grader.h"
using namespace std;
typedef pair < int, int > PII;
const int NMAX = ((1 << 9) + 5);
vector < int > G[NMAX];
vector < int > List;
inline void Reset (int n)
{
for(int i = 1; i <= n; ++i)
if(!G[i].empty())
G[i].clear();
if(!List.empty())
List.clear();
return;
}
inline void Add_Edge (int X, int Y)
{
G[X].push_back(Y), G[Y].push_back(X);
return;
}
inline void DFS (int Node, int Father)
{
List.push_back(Node);
for(auto it : G[Node])
if(it != Father)
DFS(it, Node);
return;
}
inline bool Ok (int pos)
{
vector < int > qq;
for(int i = 0; i <= (pos - 1); ++i)
qq.push_back(List[i]);
return query(qq);
}
int findEgg (int n, vector < PII > edges)
{
Reset(n);
for(auto it : edges)
Add_Edge(it.first, it.second);
int root = edges[0].first;
DFS(root, -1);
int Left = 1, Right = n;
while(Left < Right)
{
int Mid = (Left + Right) >> 1;
if(Ok(Mid))
Right = Mid;
else
Left = Mid + 1;
}
return List[Left - 1];
}
