#include <bits/stdc++.h>
#include "grader.h"
#define range(it, a, b) for (ll it = a; it < b; it++)
#define invr(it, a, b) for (ll it = a; it >= b; it--)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define ld long double
#define INF64 ((ll) 1 << 62)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
#define ptr(A) shared_ptr<A>
#define v(x) vector<x>
using namespace std;
int n;
v(v(int)) adj;
v(int) stree;
v(bool) blocked;
void get_subtree(int i, int p) {
stree[i] = 1;
for (int k : adj[i]) {
if (k == p || blocked[k])
continue;
get_subtree(k, i);
stree[i] += stree[k];
}
}
ll get_centroid(int i, int p, int& m) {
for (ll k : adj[i]) {
if (k == p || blocked[k])
continue;
if (stree[k] > m/2)
return get_centroid(k, i, m);
}
return i;
}
void fill_set (v(int)& st, int i, int p) {
st.push_back(i+1);
for (int k : adj[i]) {
if (k == p || blocked[k])
continue;
fill_set(st, k, i);
}
}
int find(int rt) {
// printf("---STEP [%d]---\n", rt);
get_subtree(rt, -1);
int m = stree[rt];
if (m == 1)
return rt;
if (m == 2) {
if (query({rt+1}))
return rt;
for (int it : adj[rt]) {
if (!blocked[it])
return it;
}
}
int c = get_centroid(rt, -1, m);
// printf("[Centroid]: %d\n", c+1);
get_subtree(c, -1);
vector<pair<int, int>> cent_adj;
for (ll k : adj[c]) {
if (blocked[k])
continue;
cent_adj.push_back({stree[k], k});
}
sort(all(cent_adj));
v(int) q = {c+1}, used, nused;
ll aux = m/2;
for (auto& it : cent_adj) {
if (it.first <= aux) {
aux -= it.first;
used.push_back(it.second);
fill_set(q, it.second, c);
}
else nused.push_back(it.second);
}
// printf("[Set]: ");
// for (int it : q)
// printf("%d ", it);
// printf("\n");
int ans = query(q);
// printf("[Query]: %d\n", ans);
// printf("[Deleted]: ");
if (ans) {
for (int& it : nused) {
blocked[it] = 1;
// printf("%d ", it+1);
}
}
else {
for (int& it : used) {
blocked[it] = 1;
// printf("%d ", it+1);
}
}
// printf("\n");
return find(c);
}
int findEgg (int N, vector < pair < int, int > > bridges) {
adj.clear();
adj.resize(N);
stree.resize(N);
blocked.clear();
blocked.resize(N);
n = N;
for (auto& it : bridges) {
adj[it.first-1].push_back(it.second-1);
adj[it.second-1].push_back(it.first-1);
}
return find(0)+1;
}
