19 · Not Splitting · GESP考级

题目描述

有一个 $k \times k$ 的网格，其中 $k$ 是偶数。第 $r$ 行第 $c$ 列的格子记作 $(r, c)$。如果两个格子 $(r_1, c_1)$ 和 $(r_2, c_2)$ 满足 $|r_1 - r_2| + |c_1 - c_2| = 1$，则它们被认为是相邻的。 如果一组相邻格子的数组可以通过沿网格线切割，将网格分成两个连通且全等的部分，并且每一对格子都属于同一部分，则称该数组是“强”的。两个部分如果可以通过平移、旋转、翻转或它们的组合互相重合，则称为全等。 上图表示第一个测试用例。箭头表示格子的配对，粗黑线表示切割线。你将得到一个长度为 $n$ 的相邻格子对数组 $a$。请你求出 $a$ 的最大强子序列的长度。若数组 $p$ 可以通过从数组 $q$ 中删除若干（可能为零或全部）元素得到，则称 $p$ 是 $q$ 的一个子序列。

输入包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。 每个测试用例的第一行包含两个用空格分隔的整数 $n$ 和 $k$（$1 \leq n \leq 10^5$；$2 \leq k \leq 500$，且 $k$ 为偶数），分别表示数组 $a$ 的长度和网格的大小。 接下来 $n$ 行，每行包含四个用空格分隔的整数 $r_{i,1}$、$c_{i,1}$、$r_{i,2}$ 和 $c_{i,2}$（$1 \leq r_{i,1}, c_{i,1}, r_{i,2}, c_{i,2} \leq k$），表示第 $i$ 个元素，即第一个格子的行列 $(r_{i,1}, c_{i,1})$ 和第二个格子的行列 $(r_{i,2}, c_{i,2})$。这两个格子是相邻的。 保证所有测试用例中 $n$ 的总和不超过 $10^5$，$k$ 的总和不超过 $500$。

对于每个测试用例，输出一个整数，表示 $a$ 的最大强子序列的长度。

输入 #1

输出 #1

7
4
1