#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int n, sz;
vector<int> g[520];
int in[520], out[520];
int ti;
vector<pair<int,int>> col;
void dfs(int v, int p = -1)
{
in[v] = ti++;
for (int x : g[v]) if (x != p){
dfs(x, v);
}
out[v] = ti++;
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
n = N;
for (auto x : bridges){
g[x.first].push_back(x.second);
g[x.second].push_back(x.first);
}
ti = 0;
dfs(1);
col.clear();
for (int i = 1; i <= n; i++){
col.push_back({in[i], i});
}
sort(col.begin(), col.end());
//for (auto x : col) cout << x.second << " "; cout << "\n";
int l = 1, r = n;
while (l < r){
int mid = (l+r)/2;
vector<int> ask;
for (int i = l; i <= mid; i++){
ask.push_back(col[i-1].second);
}
//cout << l << " " << r << " : "; for (int x : ask) cout << x << " "; cout << " - ";
int res = query(ask);
//cout << res << " : ";
if (res){
r = mid;
}
else {
l = mid+1;
}
//cout << l << " " << r << "\n";
}
for (int i = 1; i <= n; i++){
in[i] = 0;
out[i] = 0;
g[i].clear();
}
return col[l-1].second;
}
