Dominó
A feladat szövege
Dominóval sokféle játékot lehet játszami. Mohó Marci kedvenc dominós játéka a következő. Először véletlenszerűen sorba rakja a felhasználható dominókat. A játék célja az, hogy a lehető leghosszabb illeszkedő sorozatot képezzen a felhasználható dominókból. A játékszabály szerint minden lépésben csak a felhasználható dominósor első (bal oldali) elemét veheti és vagy elveti (félrerakja, de később nem veheti), vagy a már illeszkedő sorozat bal vagy jobb végéhez teszi, feltéve, hogy az adott oldalával illeszkedik (megegyezik a pöttyök száma a két dominó érintkező oldalán). Az aktuális dominót mindkét oldalával próbálja illeszteni. A játék úgy kezdődik, hogy az első dominót ki kell raknia.
Feladat:
Készíts programot, amely meghatározza a kirakható leghosszabb illeszkedő dominósor hosszát.
Bemenet:
A DOMINO.BE állomány első sorában a felhasználható dominók száma (1<=N<=100000) van. A következő N sor mindegyikében egy dominó leírása, azaz két szám, X Y (0<=X, Y<=9) van egy szóközzel elválasztva. Bármely dominó (számpár) többször is szerepelhet az állományban, és az állomány nem feltétlenül tartalmaz minden lehetséges dominót.
Kimenet:
A DOMINO.KI állományba egyetlen számot kell írni, a kirakható leghosszabb illeszkedő dominósor hosszát.
Példa:
| DOMINO.BE | DOMINO.KI |
| 6
1 2
1 6
2 3
1 4
2 3
4 3 | 5 |
Tesztadatok
