#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg (int numar_noduri , vector < pair <int, int> > muchii)
{
vector <int> adiacenta[513];
int moment[513] = { } , masca[513] = { };
for (auto& muchie : muchii)
{
adiacenta[muchie.first].push_back(muchie.second);
adiacenta[muchie.second].push_back(muchie.first);
}
int ramas = numar_noduri , __masca = 0;
while (ramas > 1)
{
moment[0]++;
queue <int> candidati;
vector <int> gasit , total;
for (candidati.push(1) , moment[1] = moment[0] ; true ; candidati.pop())
{
int& nod = candidati.front();
if ((masca[nod] & __masca) == __masca)
{
total.push_back(nod);
if (masca[nod] == __masca)
{ gasit.push_back(nod); }
if ((int)gasit.size() == ramas / 2)
{ break; }
for (auto& vecin : adiacenta[nod]) {
if (moment[vecin] != moment[0])
{
moment[vecin] = moment[0];
candidati.push(vecin);
}
}
}
}
const int putere = (1 << (moment[0] - 1));
for (auto& nod : total)
{ masca[nod] |= putere; }
if (query(total))
{ __masca |= putere; ramas = (int)gasit.size(); }
else
{ ramas -= (int)gasit.size(); }
}
int nod = 1;
while (masca[nod] != __masca)
{ nod++; }
return nod;
}
