#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int>dfsorder;
vector<int>g[600];
void dfs(int source,int p)
{
dfsorder.push_back(source);
for(int go:g[source])
if(go!=p)dfs(go,source);
}
int findEgg (int N,vector<pair<int,int> >bridges)
{
for(int i=1;i<=N;i++) g[i].clear();
for(int i=0;i<N-1;i++)
{
g[bridges[i].first].push_back(bridges[i].second);
g[bridges[i].second].push_back(bridges[i].first);
}
dfs(1,0);
int l=0,r=N-2;
int mid;
while(l<=r)
{
mid=(l+r)/2;
if(query(vector<int>(dfsorder.begin(),dfsorder.begin()+mid+1)))
r=mid-1;
else l=mid+1;
}
return dfsorder[l];
}
