CF1627F.Not Splitting

There is a $k \times k$ grid, where $k$ is even. The square in row $r$ and column $c$ is denoted by $(r,c)$. Two squares $(r_1, c_1)$ and $(r_2, c_2)$ are considered adjacent if $\lvert r_1 - r_2 \rvert + \lvert c_1 - c_2 \rvert = 1$.

An array of adjacent pairs of squares is called strong if it is possible to cut the grid along grid lines into two connected, congruent pieces so that each pair is part of the same piece. Two pieces are congruent if one can be matched with the other by translation, rotation, and reflection, or a combination of these.

The picture above represents the first test case. Arrows indicate pairs of squares, and the thick black line represents the cut.

You are given an array $a$ of $n$ pairs of adjacent squares. Find the size of the largest strong subsequence of $a$. An array $p$ is a subsequence of an array $q$ if $p$ can be obtained from $q$ by deletion of several (possibly, zero or all) elements.

有一个 $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$，则称它们相邻。

一个由相邻方格对组成的数组称为强数组（strong），如果可以沿着网格线将整个网格切割成两个**连通的、全等的**部分，使得该数组中的每一对方格都落在同一部分中。两个部分称为全等，是指其中一个可通过平移、旋转、反射或其组合与另一个完全重合。

上图表示第一个测试用例。箭头表示方格对，粗黑线表示切割线。

给定一个包含 $n$ 个相邻方格对的数组 $a$，求 $a$ 的最长强子序列的长度。数组 $p$ 是数组 $q$ 的子序列，当且仅当 $p$ 可通过从 $q$ 中删除若干（可能为零个或全部）元素得到。

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 100$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two space-separated integers $n$ and $k$ ($1 \leq n \leq 10^5$; $2 \leq k \leq 500$, $k$ is even) — the length of $a$ and the size of the grid, respectively.

Then $n$ lines follow. The $i$-th of these lines contains four space-separated integers $r_{i,1}$, $c_{i,1}$, $r_{i,2}$, and $c_{i,2}$ ($1 \leq r_{i,1}, c_{i,1}, r_{i,2}, c_{i,2} \leq k$) — the $i$-th element of $a$, represented by the row and column of the first square $(r_{i,1}, c_{i,1})$ and the row and column of the second square $(r_{i,2}, c_{i,2})$. These squares are adjacent.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$, and the sum of $k$ over all test cases does not exceed $500$.

输入包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output a single integer — the size of the largest strong subsequence of $a$.

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

In the first test case, the array $a$ is not good, but if we take the subsequence $[a_1, a_2, a_3, a_4, a_5, a_6, a_8]$, then the square can be split as shown in the statement.

In the second test case, we can take the subsequence consisting of the last four elements of $a$ and cut the square with a horizontal line through its center.

在第一个测试用例中，数组 $a$ 不是“好”的，但如果我们取子序列 $[a_1, a_2, a_3, a_4, a_5, a_6, a_8]$，则正方形可以按题目描述所示方式分割。

在第二个测试用例中，我们可以取数组 $a$ 的最后四个元素构成子序列，并通过正方形中心作一条水平直线将其切割。