#include "grader.h"
#include<bits/stdc++.h>
using namespace std;
void atac(int sum, vector<bool> &pos, vector<vector<int>> &adj) {
//cout << "sum: " << sum << endl;
//for (auto ab: pos) {
// cout << ab << " ";
//}
//cout << endl;
int ya = 0;
vector<int> isla;
vector<bool> visi(pos.size(), 0);
queue<int> bfs;
visi[0] = 1;
isla.push_back(1);
for (auto to: adj[0]) {
bfs.push(to);
//cout << to << ".push ";
}
//cout << endl;
ya += pos[0];
while (ya != sum) {
int act = bfs.front();
bfs.pop();
visi[act] = 1;
ya += pos[act];
isla.push_back(act + 1);
for (auto to: adj[act]) {
if (!visi[to]) {
bfs.push(to);
}
}
}
if (query(isla)) {
vector<bool> sal(pos.size(), 0);
for (auto to: isla) {
to --;
sal[to] = 1;
}
for (int t1 = 0; t1 < pos.size(); t1 ++) {
if (!sal[t1]) {
pos[t1] = 0;
}
}
} else {
for (auto to: isla) {
to --;
pos[to] = 0;
}
}
return ;
}
int sump(vector<bool> pos) {
int sum = 0;
for (bool po: pos) {
sum += po;
}
return sum;
}
int findEgg (int n, vector<pair<int, int>> in) {
int a, b;
vector<vector<int>> adj(n);
vector<bool> pos(n, 1);
for (int t1 = 0; t1 < n-1; t1++) {
a = in[t1].first - 1;
b = in[t1].second - 1;
adj[a].push_back(b);
adj[b].push_back(a);
}
while (sump(pos) != 1) {
atac(sump(pos) / 2, pos, adj);
}
int re = 0;
for (int t1 = 0; t1 < n; t1 ++) {
//cout << pos[t1] << " ";
if (pos[t1]) {
re = t1 + 1;
}
}
//cout << endl;
return re;
}
