== include(page="template/taskheader" task_id="diametru") ==
Stelica, student eminent la Liceul International al Structurilor de date se pregateste de Bacalaureat si, ca orice alt elev de varsta lui, atunci cand gaseste ceva interesant fara nicio legatura cu Bacalaureatul amana tot ce are de facut ca sa studieze ce a gasit.

Astazi el a descoperit algoritmul pentru determinarea diametrului unui arbore (diametrul unui graf este definit ca maximul distantei minime intre $2$ noduri). Este un algoritm foarte simplu si usor de implementat asa ca evident l-a facut sa se gandeasca la tot felul de aplicatii. Algoritmul este urmatorul (descris in pseudocod):

Astazi el a descoperit algoritmul pentru determinarea diametrului unui graf (diametrul unui graf este definit ca maximul distantei minime intre $2$ noduri). Este un algoritm foarte simplu si usor de implementat asa ca evident l-a facut sa se gandeasca la tot felul de aplicatii. Algoritmul este urmatorul (descris in pseudocod):

==code(python) |
 INTRARE: un graf neorientat conex G(V, E) cu nodurile etichetate de la 1 la |V| (cardinal de V)

 raspuns <- 0
 pentru K pasi executa
   afla distanta de la nod_current la toate celelalte (de exemplu printr-un bfs http://infoarena.ro/problema/bfs )

   next <- nodul cel mai indepartat de nod_curent astfel incat niciunea din perechile (next, nod_curent) si (nod_curent, next) sa mai fi fost aleasa

   next <- nodul cel mai indepartat de nod_curent astfel incat niciunea din perechile (next, nod_curent) si (nod_curent, next) sa nu mai fi fost aleasa

           in caz de egalitate se alege next la distanta maxima de nod_curent

           in caz de egalitate si dupa criteriulde  mai sus se alege next valoare minima

           in caz de egalitate si dupa criteriul de  mai sus se alege next de valoare minima

   raspuns <- max(raspuns, distanta dintre nod_curent si next)
   nod_curent <- next
==

Acest algoritm, are o proprietate foarte interesanta: cand graful $G$ e arbore se poate alege $K = 2$ si sigur raspuns va contine la final diametrul arborelui. Pentru grafuri lucrurile nu stau chiar asa. Chiar si-asa Stelica este foarte concentrat pe acest algoritm si nu mai invata nimic pentru bacalaureat asa ca parintii lui v-au rugat sa gasiti un graf $G$ astfel incat sa trebuiasca un K cat mai mare pentru ca algoritmul sa determine raspunsul. Va vor puncta in functie de cat de mare veti reusi sa faceti $K$-ul pentru a-i arata lui Stelica ca nu este un algoritm bun si sa nu-si mai piarda timpul cu el.

Acest algoritm, are o proprietate foarte interesanta: cand graful $G$ e arbore se poate alege $K = 2$ si sigur variabila $raspuns$ va contine la final diametrul arborelui. Pentru grafuri lucrurile nu stau chiar asa. Chiar si-asa Stelica este foarte concentrat pe acest algoritm si nu mai invata nimic pentru bacalaureat asa ca parintii lui v-au rugat sa gasiti un graf $G$ astfel incat sa fie nevoie de un $K$ cat mai mare pentru ca algoritmul sa determine raspunsul. Va vor puncta in functie de cat de mare veti reusi sa faceti $K$-ul pentru a-i arata lui Stelica ca nu este un algoritm bun si sa nu-si mai piarda timpul cu el.

Astfel daca veti reusi sa faceti K-ul sa fie cel putin:

Astfel daca veti reusi sa faceti $K$-ul sa fie cel putin:

* $10$ - veti primi 30 de puncte
* $450$ - veti primi 50 de puncte

h3. Explicaţie
Pentru acest output veti lua $0$ puncte dar este un exemplu de graf unde nu se gaseste diametrul cu K = 2, trebuie K >= 3.

Algoritml va functiona asa:

Algoritmul va functiona asa:

* Din nodul $1$ se merge in nodul $2$ care e la distanta $1$ (toate sunt egal departate de $1$ dar $2$ are valoarea ea mai mica)
* Din nodul $2$ se merge in nodul $3$ care e la distanta $1$ (toate sunt egal departate de $2$ dar perechea $(1, 2)$ a fost deja aleasa iar dintre $3$ si $4$, $3$ are valoarea mai mica)