#include <bits/stdc++.h>
#include "grader.h"
// #include "grader.cpp"
using namespace std;
const int AN=530;
vector<int> adj[AN];
vector<int> cur;
int n;
void dfs(int x,int p=-1)
{
cur.push_back(x);
for(auto y:adj[x])
{
if(y==p)continue;
dfs(y,x);
}
}
bool check(int len)
{
vector<int> tp(begin(cur),begin(cur)+len+1);
// cout<<"Asking tp: ";for(auto x:tp)cout<<x<<' ';
// cout<<endl;
bool r=query(tp);
// cout<<"Result r: "<<r<<endl;
return r;
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
n=N;
for(int i=0;i<n-1;i++)
{
adj[bridges[i].first].push_back(bridges[i].second);
adj[bridges[i].second].push_back(bridges[i].first);
}
dfs(1);
int l=-1,r=cur.size()-1;
while(l+1<r)
{
int mid=(l+r)/2;
if(check(mid))
{
// cout<<"ASKED ";
// for(int j=0;j<=mid;j++)
// {
// cout<<cur[j]<<' ';
// }
// cout<<endl;
r=mid;
}
else
{
l=mid;
}
}
// cout<<l<<' '<<r<<endl;
return cur[r];
}
