#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
#define all(a) a.begin(), a.end()
vector<int> G[N];
int aS[N];
vector<pair<int, int>> inS;
int tim = 0;
void dfs(int u, int p) {
inS.push_back({++tim, u});
for (auto v : G[u]) {
if (v == p) continue;
dfs(v, u);
}
}
int findEgg(int n, vector<pair<int, int>> bridges) {
for (int i = 0; i < N; ++i) G[i].clear();
for (auto [u, v] : bridges) G[u].push_back(v), G[v].push_back(u);
dfs(1, -1);
// cerr << "DFSED\n";
sort(all(inS));
int l = 0, r = n - 1, ans, mid = (l + r) / 2;
// cerr << l << " " << r << endl;
for (; l <= r; mid = (l + r) / 2) {
vector<int> q;
for (int i = 0; i <= mid; ++i) { q.push_back(i); }
if (query(q)) l = mid + 1, ans = mid;
else r = mid - 1;
}
// made a array of the vertecies sorted in in/out
// binary search of prefixes
return ans;
}
