Not Splitting
Contest: Codeforces Round 766 (Div. 2)
Difficulty rating: 2700
Tags: geometry, graphs, greedy, implementation, shortest paths

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.

Input format:
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$$$.

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

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
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

Example output:
7
4
1

Editorial:
Claim. Any cut that splits the square into two congruent parts is rotationally symmetric about the center by $$$180^{\circ}$$$.
Proof. It is a special case when the cut is a vertical or horizontal line. Assume otherwise. Then:
• One piece has a row containing more than $$$\frac{k}{2}$$$, but less than $$$k$$$ squares.
• One piece has a column containing more than $$$\frac{k}{2}$$$, but less than $$$k$$$ squares.
• Both exactly pieces contain two of the corners of the grid.
Now consider the isometry of the plane bringing one piece to the other. Then the corners of the grid of one piece must map to the corners of the grid of the other piece, since there has to be a straight edge connecting them with length $$$k$$$, which only exists between two corners. There are precisely two such isometries that fit within the bounds of the square: a reflection and a $$$180^{\circ}$$$ rotation, pictured below, respectively.
However if one piece has a row containing more than $$$\frac{k}{2}$$$ but less than $$$k$$$ squares, then in the first case the number of squares in that row is greater than $$$k$$$. The same holds in the case of a vertical reflection. Hence the cut must be rotationally symmetric.
Now we can turn the problem into a graph problem. Consider the graph whose vertices are vertices of the grid and whose edges are edges of the grid. We need to minimize the number of pairs of squares that we "split up" in our cut. Note that each pair of squares shares an edge. Thus, we want to minimize the number of these edges we pass through. Let's initially weight all edges with $$$0$$$, and increase the weight by $$$1$$$ for each edge given.
Since each cut is rotationally symmetric about the center, we can just consider finding a minimal-weight path from the boundary to the center, and then rotating this path $$$180^{\circ}$$$ to find a valid cut. However, there are three details we need to iron out:
1. The cut may pass through other weighted edges when rotated.
2. We need to find an efficient way to find the shortest path from each boundary point to the center.
3. The cut may be self-intersecting.
The second point can be accounted for by noticing that the boundary of the square has all edges of weight $$$0$$$, so we can just run single source shortest paths from any single point on the boundary.
For the third point, consider some path that intersects itself when rotated. Suppose we build the path edge-by-edge, along with its mirror copy. At some point we will hit the mirror copy. But that means that there is a way with strictly fewer edges to reach the same point: just take the path from this intersection to the start of the mirror copy. See the image below.
So now all our details are successfully ironed out. We can just run Dijkstra's algorithm from any vertex and find the length of the shortest path, solving the problem in $$$\mathcal{O}(n + k^2 \log k)$$$.