#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
int vis[515];
vector<int> v[515], et;
void dfs(int nod){
vis[nod] = 1;
et.push_back(nod);
for (int i = 0; i < v[nod].size(); i++){
int sig = v[nod][i];
if (vis[sig] == 0){
dfs(sig);
}
}
}
int findEgg(int N, vector<pair<int,int>> bridges){
for (int i = 0; i < bridges.size(); i++){
v[bridges[i].first].push_back(bridges[i].second);
v[bridges[i].second].push_back(bridges[i].first);
}
dfs(1);
int l = 0, r = N-1;
while(l != r){
int m = (l+r+1)/2;
if (query(vector<int>(et.begin(), et.begin()+m)) == 1){
r = m-1;
} else {
l = m;
}
}
return et[l];
}
