#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int N = 2000005;
vector<int> vec[N], ans;
int fix[N];
vector<int> ask(int r) {
return vector<int>(ans.begin(), ans.begin() + r + 1);
}
void dfs(int node, int par) {
if (fix[node]) return;
fix[node] = 1;
ans.push_back(node);
for (int to : vec[node]) {
if (to != par) {
dfs(to, node);
}
}
}
int findEgg(int N, vector<pair<int, int>> bridges) {
ans.clear();
for (int i = 0; i <= N; ++i) {
vec[i].clear();
fix[i] = 0;
}
for (auto [u, v] : bridges) {
vec[u].push_back(v);
vec[v].push_back(u);
}
dfs(1, 0);
int l = 0, r = ans.size() - 1, pas = 0;
while (l <= r) {
int mid = (l + r) / 2;
vector<int> que = ask(mid);
int egg = query(que);
if (egg == 1) {
pas = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return pas;
}
