Курс: Подготовка к ЕГЭ

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

Задачи

Задача

14/22

Домино

Ограничение по времени: 125 ms
Ограничение по памяти: 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Теория

Задача

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