#include "grader.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<string>
#include<math.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pair<ll, ll>>;
using vvpll = vector<vpll>;
/*int query(vector<int> t) {
for (auto i : t) {
if (i == 5) {
return 1;
}
}
return 0;
}*/
int query(vector < int > islands);
vector<vector<int>> g;
vector<int> nodes;
vector<bool> vis;
int n;
void dfs(ll start) {
nodes.push_back(start);
vis[start] = true;
for (auto i : g[start]) {
if (!vis[i]) {
dfs(i);
}
}
}
int findEgg(int N, vector < pair < int, int > > bridges) {
n = N;
g.resize(n);
vis.resize(n);
for (ll i = 0; i < n - 1; i++) {
g[--bridges[i].first].push_back(--bridges[i].second);
g[bridges[i].second].push_back(bridges[i].first);
}
vector<int> ask, prev_ask;
dfs(0);
ll start = 0, end = n - 1;
while (start < end) {
ll mid = (start + end) / 2;
for (ll i = start; i <= mid; i++) {
ask.push_back(nodes[i] + 1);
}
int answer = query(ask);
if (answer == 0) {
prev_ask = ask;
start = mid + 1;
}
else {
ask = prev_ask;
end = mid;
}
}
return nodes[end] + 1;
}
/*
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int s;
cin >> s;
vector<pair<int, int>> bridges(s-1);
for (ll i = 0; i < s- 1; i++) {
cin >> bridges[i].first >> bridges[i].second;
}
cout << findEgg(s, bridges);
}*/
