Модуль: B27 (C4) - анализ пар


Задача

14 /23


Домино

Задача

На столе выложили цепочку из N костяшек по принципу домино. Под костяшкой понимается пара любых неотрицательных чисел, каждое не превышает 100. В наборе нет двух одинаковых костяшек (как в домино). Переставлять местами костяшки нельзя, но можно поворачивать любую костяшку, получая из костяшки 1-2 костяшку 2-1. 
Определите максимально длинную цепочку костяшек домино, которую можно получить. Под цепочкой следует понимать последовательность костяшек, у которой второе число первой костяшки равно первому числу второй.

Входные данные
в первой строке задается число N – количество выложенных костяшек (\(0<N<10000\)). Далее следуют N пар чисел по два в строке.

Выходные данные
Программа должна вывести одно число – максимальную длину цепочки.
 
Примеры
Входные данные Выходные данные
1 5
1 2
2 3
5 4
5 5
5 1
3

Пояснение: если перевернуть третью костяшку, то образуется цепочка: 4-5 5-5 5-1.