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
Tesztadatok
