#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <iomanip>
#include "grader.h"
#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
#define upmin(a, b) a = min(a, b)
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
const ll INF = 2e18;
const ll MOD = 1e9 + 7;
vvll tree;
vll pref;
void dfs(ll node, ll papa) {
pref.push_back(node);
for (auto& nei : tree[node]) {
if (nei == papa) continue;
dfs(nei, node);
}
}
int findEgg(int N, vector < pair < int, int > > bridges) {
ll n = N;
tree.clear(), tree.resize(n);
rep(i, 0, n - 1) {
tree[bridges[i].first - 1].push_back(bridges[i].second - 1);
tree[bridges[i].second - 1].push_back(bridges[i].first - 1);
}
dfs(0, -1);
ll f = 0, t = n - 1, mid;
ll ans = -1;
while (f != t) {
mid = (f + t + 1) / 2;
vector<int> ask;
rep(i, 0, mid + 1) {
ask.push_back(pref[i] + 1);
}
if (query(ask)) {
t = mid - 1;
ans = mid;
}
else {
f = mid;
ans = mid;
}
}
return pref[ans] + 1;
}
