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 |