NézetNyomtat

Városnézés
Címkék > Feladat

Városnézés

A nyári utazás alkalmával különböző európai nagyvárosokat látogatunk meg. Ezek a városok - valamilyen rejtélyes okból - a következő módon épültek: először elkészült három nevezetes pont (a továbbiakban látnivaló), melyeket kétirányú utakkal kötöttek össze. Ezután minden újabb látnivalót a korábbiak közül pontosan kettővel kötöttek össze, amelyek már közvetlenül össze voltak kötve.

Feladat

Tervezzünk egy olyan körutazást a városban, ami a lehető legtöbb látnivalót érinti, de minden úton legfeljebb egyszer halad át, és minden látnivalót legfeljebb egyszer érint.

Bemenet

Az első sor a tesztesetek száma, ez legfeljebb 50. Minden teszteset első sora a látnivalók N száma, ez 4 és 15, illetve 4 és 1000 közé esik (kis teszt/nagy teszt). Ezután N-3 sor következik, mindegyikben egy számpár. Ezek a sorok a 4., 5., ..., N. látnivalóhoz megadják, hogy melyik korábbi látnivalókkal köti össze út.

Kimenet

Minden tesztesethez egyetlen sort kell megadni, azt, hogy legfeljebb hány látnivalót tudunk érinteni egy körutazás során.

Példa

Bemenet

 
2
5
1 2
2 1
6
1 2
1 4
4 5

Kimenet

 
Case #1: 4
Case #2: 6

Tesztadatok