#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;
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 K = log2(n * 2 - 1);
int k = 0;
int res=-1;
for (int i = K-1; i >= 0; i--) {
int nk = k + (1LL << i);
m = nk;
v.clear();
dfs(1);
if (query(v)) {
res = v.back();
}
else k = nk;
}
m = k;
v.clear();
dfs(1);
return (res == -1 ? v.back() : res);
}
