← 返回题目列表

Codeforces · 1627/F

F. 不分裂

中文机器翻译题面 查看原题

有一个 $$$k \times k$$$ 网格,其中 $$$k$$$ 是偶数。 $$$r$$$ 行和$$$c$$$ 列中的正方形由$$$(r,c)$$$ 表示。如果 $$$\lvert r_1 - r_2 \rvert + \lvert c_1 - c_2 \rvert = 1$$$,则两个正方形 $$$(r_1, c_1)$$$ 和 $$$(r_2, c_2)$$$ 被视为相邻。

如果可以沿着网格线将网格切割成两个相连的、全等的块,使得每对都是同一块的一部分,则相邻的成对的正方形阵列被称为强阵列。如果两个部分可以通过平移、旋转和反射或这些的组合与另一部分匹配,则两个部分是一致的。

上图代表第一个测试用例。箭头表示成对的方块,粗黑线表示切割。

给你一个数组 $$$a$$$,由 $$$n$$$ 相邻方块对组成。求 $$$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$$$ 行。这些行的第 $$$i$$$ 包含四个空格分隔的整数 $$$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$$$) — $$$a$$$ 的第 $$$i$$$ 个元素,由第一个正方形 $$$(r_{i,1}, c_{i,1})$$$ 的行和列以及第二个正方形 $$$(r_{i,2}, c_{i,2})$$$ 的行和列表示。这些正方形是相邻的。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$,所有测试用例的$$$k$$$总和不超过$$$500$$$。

输出

对于每个测试用例,输出一个整数 - $$$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

输出 #1

7
4
1

注意

在第一个测试用例中,数组 $$$a$$$ 不好,但是如果我们取子序列 $$$[a_1, a_2, a_3, a_4, a_5, a_6, a_8]$$$,则可以如语句所示分割正方形。

在第二个测试用例中,我们可以采用 $$$a$$$ 的最后四个元素组成的子序列,并用穿过其中心的水平线切割正方形。