Fişierul intrare/ieşire:diametru.in, diametru.outSursăad-hoc
AutorDin FolclorAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.33 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Diametru (clasele 11-12)

Se dă un arbore neorientat cu N noduri numerotate de la 1 la N. Să se găsească un diametru al arborelui, adică o cale care nu conţine niciun nod de două ori şi care are lungimea maximă (exprimată în număr de muchii).

Date de intrare

Fişierul de intrare diametru.in conţine pe prima linie numărul de noduri, N. Pe următoarele N - 1 linii se află câte o pereche de noduri u v indicând că între nodurile u şi v există o muchie.

Date de ieşire

În fişierul de ieşire diametru.out se va tipări, pe prima linie, diametrul D. Pe a doua linie se vor tipări D + 1 noduri distincte care, parcurse în ordine, formează o cale de D muchii. Dacă există mai multe soluţii, oricare este acceptabilă.

Restricţii

  • 2 ≤ N ≤ 100.000

Exemplu

diametru.indiametru.out
7
3 1
1 5
1 2
2 7
2 6
7 4
4
3 1 2 7 4

Explicaţie

Alte răspunsuri acceptabile ar fi fost (4 7 2 1 3), (5 1 2 7 4) sau (4 7 2 1 5), toate de 4 muchii.

Trebuie sa te autentifici pentru a trimite solutii. Click aici