#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using namespace std;
vector<int> euler;
vector<vector<int>> adj;
void dfs(int n, int p=-1) {
euler.push_back(n);
for (auto x : adj[n]) {
if (x==p) continue;
dfs(x, n);
}
euler.push_back(n);
}
int findEgg (int N, vector < pair < int, int > > bridges) {
adj.resize(N);
for (int i=0; i<N-1; i++) {
int a = bridges[i].first;
int b = bridges[i].second;
a--; b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(0);
int n = euler.size();
int l = 0, r = n-1;
int ans;
while (l <= r) {
int m = (l+r)/2;
vector<int> ask;
for (int i=0; i<n; i++) {
if (i >= m) ask.push_back(euler[i]+1);
}
int q = query(ask);
if (q == 1) {
l = m+1;
ans = m;
}
else {
r = m-1;
}
}
int anss = euler[ans]+1;
euler.clear();
for (int i=0; i<N; i++) {
adj[i].clear();
}
adj.clear();
return anss;
}
