#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int> tour, vis(550);
vector<vector<int>> graph;
void euler(int node) {
vis[node] = true;
tour.push_back(node);
for (auto e: graph[node]) {
if (!vis[e]) {
euler(e);
}
}
}
int findEgg(int N, vector<pair<int, int>> bridges) {
graph.resize(N + 1);
for (auto e : bridges) {
graph[e.first].push_back(e.second);
graph[e.second].push_back(e.first);
}
euler(1);
int l = 0, r = N - 1;
while (l < r) {
int m = (l + r + 1) / 2;
if (query(vector<int>(tour.begin(), tour.begin() + m))) {
r = m - 1;
} else {
l = m;
}
}
return tour[r];
}
