/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include <iostream>
#include <chrono>
#include <vector>
#include "grader.h"
#define maxn 1000005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;
#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")
using namespace std;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;
typedef pair <ll, int> pli;
typedef long double pd;
vector <int> v[maxn];
vector <int> tour;
void gen(int node , int par)
{
tour.pb(node);
for(auto& e : v[node])
{
if(e == par)
continue;
gen(e , node);
}
}
vector <int> pom;
bool check(int x)
{
pom.clear();
for(int i = 0; i <= x; i++)
pom.pb(tour[i]);
return query(pom);
}
int n;
int findEgg(int N , vector <pii> bridges)
{
for(int i = 1; i <= n; i++)
v[i].clear();
tour.clear();
n = N;
for(auto& e : bridges)
{
v[e.X].pb(e.Y);
v[e.Y].pb(e.X);
}
//gen(1 , -1);
int node = 1;
while(v[node].size() == 0)
node++;
tour.pb(node);
tour.pb(v[node][0]);
for(int i = 1; i <= n; i++)
tour.pb(i);
int l = 0 , r = tour.size() - 1;
int mid;
while(r > l)
{
mid = (l + r) / 2;
if(check(mid) == true)
r = mid;
else
l = mid + 1;
}
return tour[l];
}
/**int main()
{
#ifdef ONLINE_JUDGE /// promeni
freopen("taxi.in", "r", stdin);
freopen("taxi.out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
///startT = std::chrono::high_resolution_clock::now();
return 0;
}*/
