#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<vector<int>> adj;
vector<int> dfsOrder;
void dfs(int u, int p = -1){
dfsOrder.push_back(u);
for (int v: adj[u]){
if (v == p) continue;
dfs(v, u);
}
}
int ask(int l, int r){
vector<int> askVector;
for (int i = l; i <= r; i++){
askVector.push_back(dfsOrder[i]);
}
return query(askVector);
}
int findEgg (int N, vector<pair<int, int>> bridges)
{
// create dfs order
int n = N;
adj.assign(n+1, vector<int>());
for (auto &pa: bridges){
int u = pa.first;
int v = pa.second;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfsOrder.push_back(-1);
dfs(1);
int l = 1, r = n;
while(l < r){
int mid = (l + r + 1)/2;
if (ask(1, mid)){
r = mid;
}
else{
l = mid + 1;
}
}
return dfsOrder[r];
}
