#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define fi first
#define se second
#define ll long long
vector< vector<int> > g;
vector<int> thutu;
void dfs(int u, int t)
{
thutu.push_back(u);
for(int i = 0; i < int(g[u].size()); ++i)
{
int v = g[u][i];
if(v == t) continue;
dfs(v, u);
}
}
int findEgg (int n, vector < pair < int, int > > bridges)
{
g.clear();
thutu.clear();
g.resize(n+1);
for(int i = 0; i < int(bridges.size()); ++i)
{
g[bridges[i].fi].push_back(bridges[i].se);
g[bridges[i].se].push_back(bridges[i].fi);
}
dfs(1, 0);
int l = 0; int r = n-1;
while(l < r)
{
int mid = (l+r+1)/2;
if(query(vector<int>(thutu.begin(), thutu.begin()+mid)))
r = mid-1;
else l = mid;
}
return thutu[l];
return 0;
}
