Fişierul intrare/ieşire:	apdm.in, apdm.out	Sursă	Algoritmus
Autor	Cosmin Silvestru Negruseri	Adăugată de
Timp execuţie pe test	0.05 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

APDM

Vom considera un graf conex, neorientat, cu N varfuri si M muchii. Fie D(i, j) distanta minima dintre varfurile i si j. Prin diametrul grafului vom defini valoarea Max { D(i,j) (1 ≤ i < j ≤ N) }.

Cerinta

Sa se determine arborele partial de diametru minim al grafului dat!

Date de Intrare

Pe prima linie a fisierului apdm.in se afla N si M. Pe fiecare din urmatoarele M linii se afla cate doua numere intregi sub forma x y, indicand prezenta unei muchii intre varfurile x si y.

Date de Iesire

Pe prima linie a fisierului apdm.out se va afisa diametrul arborelui obtinut.

Restrictii

• 3 ≤ N ≤ 150
• N ≤ M ≤ 5000

Exemplu

apdm.in	apdm.out	Explicatie
8 13 1 2 1 5 2 4 1 7 2 3 3 4 3 8 4 5 4 6 5 6 5 7 6 7 6 8	4	In desen observam colorate cu verde muchiile unui arbore partial de diametru 4, acestea sunt: (1, 5), (2, 4), (3, 4), (4, 5), (4, 6), (5, 7), (6, 8)

Cum se trimit solutii?