Programozás‎ > ‎Feladatok‎ > ‎

Vasút

Bergengócia vasúthálózata olyan, hogy bármely városból bármely másik városba csak egyféleképpen lehet eljutni. Minden vonat a fővárosból (1-es sorszámú város) indul és valamely olyan városig megy, ahonnan már nincs tovább vasúti pálya. Két város között a vonatút hossza a köztük levő vasútállomások száma+1!

Feladat

Készíts programot, amely megadja a leghosszabb vonatút hosszát, ahol a vasút nem ágazik el!

Bemenet

A vasut.be állomány első sorában a városok száma van (2<=N<=10 000), a következő N-1 sorban pedig az egyes vasútszakaszok leírása (1<=Ai ,Bi <=N), ami azt jelenti, hogy van Ai -ből Bi-be menő közvetlen vasúti összeköttetés. A vasúti pálya bármely városból legfeljebb 10-felé ágazhat.

Kimenet

A vasut.ki állomány első sorába a leghosszabb vonatút hosszát kell írni, ahol a vasút nem ágazik el!

Példa

Bemenet  Kimenet
11
1 2
1 3
2 4
2 5
1 9
3 6
5 7
7 8
8 10
8 11
3



Tesztadatok

Címkék

A feladat forrása: NTOITV 2015 2. forduló, 11-13. évfolyam
Algoritmusok: fagráf bejárása, leghosszabb út

megoldás