На столе выложили цепочку из 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.