#include <bits/stdc++.h>
#include "grader.h"
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
constexpr int MAX = 2e+5 + 1, INF = 2e+9, MOD = 1e+9 + 7, K = 31;
int n, m;
vector <int> g[MAX+2], v;
bool is = 0;
void dfs(int u, int c=-1) {
if (v.size() == m) return;
v.pb(u);
if (v.size() == m) return;
for (int &i : g[u]) {
if (i == c) continue;
dfs(i, u);
}
}
int findEgg (int N, vector < pair < int, int > > e) {
if (!is) {
n = N;
for (auto &i : e) g[i.ff].pb(i.ss), g[i.ss].pb(i.ff);
is = 1;
}
int l = 1, r = n;
while (l < r) {
m = (l + r) / 2;
v.clear();
dfs(1);
if (query(v) == 1) {
r = m;
}
else l = m + 1;
}
m = r;
v.clear();
dfs(1);
return v.back();
}
