У вас есть квадрат \(k \times k\), причем \(k\) четно. Клетка в строке \(r\) и столбце \(c\) обозначается \((r,c)\). Две клетки \((r_1, c_1)\) и \((r_2, c_2)\) называются соседними, если \(\lvert r_1 - r_2 \rvert + \lvert c_1 - c_2 \rvert = 1\).
Массив пар соседних клеток называется прочным, если существует способ разрезать квадрат на две связных конгруэнтных части таким образом, что в каждой данной паре клеток обе клетки принадлежат одной части. Две части конгруэнтны, если одну можно наложить на другую с помощью переноса, вращения и/или зеркального отражения, а также их комбинаций.
Рисунок выше демонстрирует первый пример. Стрелки показывают пары клеток, а жирная линия показывает разрез на две части. Вам дан массив \(a\) из \(n\) пар соседних клеток. Найдите размер наибольшей прочной подпоследовательности \(a\). Массив \(p\) является подпоследовательностью \(q\), если \(p\) может быть получен из \(q\) удалением нескольких (возможно, ни одного или всех) элементов.
Выходные данные
Для каждого набора входных данных выведите одно целое число — размер наибольшей прочной подподпоследовательности \(a\).
Примечание
В первом примере \(a\) не является прочным, но подпоследовательность \([a_1, a_2, a_3, a_4, a_5, a_6, a_8]\) является, т. к. квадрат может быть разрезан способом, показанным в условии.
Во втором примере подпоследовательность из четырех последних элементов \(a\) является прочным, т. к. квадрат можно разрезать с помощью горизонтальной прямой через центр.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
8 4
1 2 1 3
2 2 2 3
3 2 3 3
4 2 4 3
1 4 2 4
2 1 3 1
2 2 3 2
4 1 4 2
7 2
1 1 1 2
2 1 2 2
1 1 1 2
1 1 2 1
1 2 2 2
1 1 2 1
1 2 2 2
1 6
3 3 3 4
|
7
4
1
|