| Fișierul intrare/ieșire | diametru.in, diametru.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | din folclor | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
| Timp de execuție pe test | 0.33 sec | Limită de memorie | 16384 KB |
| Scorul tău | N/A | Dificultate |
  3
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile 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.in | diametru.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.
