Leghosszabb dominósor

Dominóval sokféle játékot lehet játszani. 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:

 

 

(Nemes Tihamér döntő 2000)