#include <bits/stdc++.h>
#include "grader.h"
#define pb push_back
using namespace std;
vector <int> v[605];
int dp[605],mx,l,f[605];
priority_queue <pair<int,int> > pq;
void dfs(int x,int par){
for (int j=0;j<v[x].size();j++){
int to = v[x][j];
if (to == par) continue;
dp[to] = dp[x] + 1;
dfs(to,x);
}
if (dp[x] > mx)
mx=dp[x],l = x;
}
void clear(int n){
while(pq.size())
pq.pop();
for (int i = 1; i <= n; i++)
v[i].clear(),dp[i] = 0,f[i] = 0;
}
int go(int n, vector < pair < int, int > > vec,vector <int> vert){
if (vert.size() == 1) return vert[0];
for (int i = 0; i < n - 1; i++){
int a = vec[i].first,b = vec[i].second;
v[a].pb(b),v[b].pb(a);
}
dp[vert[0]] = 1,mx = 1,l = vert[0];
dfs(vert[0],vert[0]);
vector <int> q; q.clear();
pq.push({mx,l});
while(q.size() < (n + 1)/2){
int x = pq.top().second;
pq.pop();
f[x] = 1,q.pb(x);
for (int j = v[x].size() - 1; j>=0; j--){
int to = v[x][j];
if (!f[to]) {pq.push({dp[to],to}); break;}
}
}
if (query(q) == 1){
int m=0,raod=0;
vector <pair<int,int> > edges; edges.clear();
for (int i=0;i<vec.size();i++){
int a = vec[i].first,b = vec[i].second;
if (f[a] && f[b]) edges.pb({a,b});
}
vector <int> newv; newv.clear();
for (int i = 0; i < vert.size(); i++)
if (f[vert[i]]) newv.pb(vert[i]);
clear(n);
return go(newv.size(), edges, newv);
}
else{
vector <pair<int,int> > edges; edges.clear();
int m = 0,raod=0;
for (int i=0;i<vec.size();i++){
int a = vec[i].first,b = vec[i].second;
if (!f[a] && !f[b]) edges.pb({a,b});
}
vector <int> newv; newv.clear();
for (int i = 0; i < vert.size(); i++)
if (!f[vert[i]]) newv.pb(vert[i]);
clear(n);
return go(newv.size(), edges, newv);
}
return -1;
}
int findEgg (int n, vector < pair < int, int > > vec){
vector <int> vert; vert.clear();
for (int i=1;i<=n;i++)
vert.pb(i);
return go(n,vec,vert);
}
