#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define fi first
#define se second
vector <int> adj[513];
vector <int> tour;
void dfs(int node, int parent){
tour.push_back(node);
for (auto child : adj[node]){
if (child!=parent){
dfs(child,node);
}
}
}
int findEgg(int n, vector<pair<int,int>> bridges){
tour.clear();
for (int i=0; i<=n; i++){
adj[i].clear();
}
for (int i=0; i<n-1; i++){
adj[bridges[i].fi].push_back(bridges[i].se);
adj[bridges[i].se].push_back(bridges[i].fi);
}
dfs(1,0);
int l=0;
int r=n-1;
vector <int> v;
while (l<r){
v.clear();
int m = (l+r)/2;
for (int i=0; i<=m; i++){
v.push_back(tour[i]);
}
int q = query(v);
if (q){r=m;}
else{l=m+1;}
}
return tour[l];
}
