#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define pb push_back
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
#define dl(x) cout<<#x<<" is "<<endl; for(auto i:x) cout<<i<<' '; cout<<endl;
#define fi first
typedef pair<int,int> pii;
vector<int>adj[600];
int par[600],dis[600],a[600];
int cnt;
void dfs(int x, int p){
par[x] = p;
a[cnt] = x; cnt++;
for(auto i:adj[x]){
if(i==p)continue;
dis[i]=dis[x]+1;
dfs(i,x);
}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
//if (query ({1})) return 1;
cnt=1;
int n = N;
for(int i=1; i<=n; i++){
adj[i].clear();
}
memset(par,0,sizeof(par));
memset(dis,0,sizeof(dis));
for(int i=0; i<n-1; i++){
auto[u,v] = bridges[i];
adj[u].pb(v);
adj[v].pb(u);
}
dfs(1,-1);
int l=0, h=n; //if contain we move high down if not we move low up
while(h-l > 1){
int mid = (h+l)/2;
vector<int>v;
for(int i=1; i<=mid; i++) v.pb(a[i]);
if(query(v)) h = mid;
else l = mid;
}
return a[h];
}
