#include <iostream>
#include <vector>
#include <bitset>
#include "grader.h"
using namespace std;
const int MAX = 514;
vector<int> adj[ MAX ];
vector<int> island;
vector<int> parc;
bitset<MAX + 2> ok;
void dfs( int nod = 1 ) {
ok[ nod ] = 1;
parc.push_back( nod );
for( const int nxt : adj[ nod ] )
if( !ok[ nxt ] )
dfs( nxt );
}
int findEgg( int n, vector<pair<int, int>> bridges ) {
for( const auto muchie : bridges ) {
adj[ muchie.first ].push_back( muchie.second );
adj[ muchie.second ].push_back( muchie.first );
}
dfs();
int left = 0;
int right = parc.size() - 1;
while( left < right ) {
int med = ( left + right ) / 2;
island.clear();
for( int i = left; i <= med; i++ )
island.push_back( parc[ i ] );
if( query( island ) )
right = med;
else left = med + 1;
}
return right;
}
