#include <bits/stdc++.h>
#include "grader.h"
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
const int MAXN = 515;
vector<int> edges[MAXN];
int n;
int sz[MAXN];
bool used[MAXN];
void recalc_size(int u, int p=-1){
sz[u] = 1;
for(auto v : edges[u]){
if(v == p || used[v])continue;
recalc_size(v,u);
sz[u] += sz[v];
}
}
int nn;
int find_centroid(int u, int p=-1){
for(auto v : edges[u]){
if(!used[v] && v != p && sz[v] > nn/2)return find_centroid(v,u);
}return u;
}
vector<int> ttt;
void dfs(int u,int p){
ttt.push_back(u);
for(auto v : edges[u]){
if(v == p || used[v])continue;
dfs(v,u);
}
}
int findEgg(int N, vector<pair<int,int>> bridges){
n = N;
for(auto [u, v] : bridges){
edges[u].push_back(v);
edges[v].push_back(u);
}
int now = 1;
while(true){
recalc_size(now);
nn = sz[now];
int u = find_centroid(now);
if(nn == 2){
if(query({now}) == 0){
int x = -1;
for(auto v : edges[now])if(!used[v])x=v;
assert(~x);
now = x;
}break;
}else if(nn == 1){
break;
}int sc=0;
now = u;
int x = -1;
for(auto v : edges[now])if(!used[v])x=v;
if(x==-1){return 0;assert(~x);}
sc = x;
//~ ttt.clear();
//~ dfs(now,now);
//~ for(auto x : ttt){
//~ cout << x << ' ';}cout << '\n';
vector<int> f, s;
ttt.clear();
dfs(now,sc);
f = ttt;
ttt.clear();
dfs(sc,now);
s = ttt;
if(query(f) == 1){
used[sc] = true;
}else {
used[now] = true;
now = sc;
}
}
for(int i=1;i<=n;i++){
edges[i].clear();
}memset(used,0,sizeof used);
return now;
}
