Statement is not available in English language
H. Трофейная дорога Эдгара
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эдгар решил собрать максимальную трофейную дорогу в Brawl Stars! У него есть $$$n$$$ специальных карточек с наградами. Каждая карточка имеет два значения: количество трофеев слева $$$l_i$$$ и количество трофеев справа $$$r_i$$$ (каждое значение от $$$1$$$ до $$$6$$$).

Эдгар может выкладывать карточки в цепочку по особым правилам: следующую карточку можно положить рядом с предыдущей только если соседние значения совпадают. Например, если у первой карточки правое значение равно $$$3$$$, то левое значение следующей карточки тоже должно быть равно $$$3$$$. Также карточки можно переворачивать, то есть менять местами значения $$$l_i$$$ и $$$r_i$$$.

Формально, цепочка карточек с индексами $$$i_1, i_2, \ldots, i_k$$$ является корректной, если:

  • Все карточки различны (каждая карточка используется не более одного раза)
  • Для каждой пары соседних карточек выполнено: $$$r_{i_j} = l_{i_{j+1}}$$$ для всех $$$1 \le j \lt k$$$

Помогите Эдгару найти максимальную длину цепочки, которую он может собрать!

Входные данные

В первой строке вводится целое число $$$n$$$ — количество карточек ($$$1 \le n \le 10^5$$$).

В следующих $$$n$$$ строках вводится по два целых числа $$$l_i$$$ и $$$r_i$$$ — значения на левой и правой части $$$i$$$-й карточки ($$$1 \le l_i, r_i \le 6$$$).

Выходные данные

Выведите одно целое число — максимальную длину цепочки карточек, которую можно собрать.

Примеры
Входные данные
3
1 2
2 3
3 4
Выходные данные
3
Входные данные
4
1 2
2 3
2 3
5 6
Выходные данные
3
Входные данные
4
1 1
1 1
1 1
1 1
Выходные данные
4
Примечание

В первом примере можно выложить цепочку: карточка 1 (1-2), карточка 2 (2-3), карточка 3 (3-4). Длина цепочки равна 3.

Во втором примере можно выложить цепочку: карточка 2 (2-3), карточка 3 (3-2), карточка 1 (2-1). Длина цепочки равна 3.

В третьем примере все карточки одинаковые (1-1), поэтому можно выложить их все подряд. Длина цепочки равна 4.