Great Grids
Contest: Codeforces Round 884 (Div. 1 + Div. 2)
Difficulty rating: 2400
Tags: 2-sat, constructive algorithms, dfs and similar, dsu, graphs

An $$$n \times m$$$ grid of characters is called great if it satisfies these three conditions:

- Each character is either 'A', 'B', or 'C'.
- Every $$$2 \times 2$$$ contiguous subgrid contains all three different letters.
- Any two cells that share a common edge contain different letters.

Let $$$(x,y)$$$ denote the cell in the $$$x$$$-th row from the top and $$$y$$$-th column from the left.

You want to construct a great grid that satisfies $$$k$$$ constraints. Each constraint consists of two cells, $$$(x_{i,1},y_{i,1})$$$ and $$$(x_{i,2},y_{i,2})$$$, that share exactly one corner. You want your great grid to have the same letter in cells $$$(x_{i,1},y_{i,1})$$$ and $$$(x_{i,2},y_{i,2})$$$.

Determine whether there exists a great grid satisfying all the constraints.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each test case contains three integers, $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \le n,m \le 2 \cdot 10^3$$$, $$$1 \le k \le 4 \cdot 10^3$$$).

Each of the next $$$k$$$ lines contains four integers, $$$x_{i,1}$$$, $$$y_{i,1}$$$, $$$x_{i,2}$$$, and $$$y_{i,2}$$$ ($$$1 \le x_{i,1} < x_{i,2} \le n$$$, $$$1 \le y_{i,1},y_{i,2} \le m$$$). It is guaranteed that either $$$(x_{i,2},y_{i,2}) = (x_{i,1}+1,y_{i,1}+1)$$$ or $$$(x_{i,2},y_{i,2}) = (x_{i,1}+1,y_{i,1}-1)$$$.

The pairs of cells are pairwise distinct, i.e. for all $$$1 \le i < j \le k$$$, it is not true that $$$x_{i,1} = x_{j,1}$$$, $$$y_{i,1} = y_{j,1}$$$, $$$x_{i,2} = x_{j,2}$$$, and $$$y_{i,2} = y_{j,2}$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^3$$$.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^3$$$.

It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$4 \cdot 10^3$$$.

Output format:
For each test case, output "YES" if a great grid satisfying all the constraints exists and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the following great grid satisfies all the constraints: BABCCBCAACAB

In the second test case, the two constraints imply that cells $$$(1,1)$$$ and $$$(2,2)$$$ have the same letter and cells $$$(1,2)$$$ and $$$(2,1)$$$ have the same letter, which makes it impossible for the only $$$2 \times 2$$$ subgrid to contain all three different letters.

Example input:
4
3 4 4
1 1 2 2
2 1 3 2
1 4 2 3
2 3 3 2
2 7 2
1 1 2 2
1 2 2 1
8 5 4
1 2 2 1
1 5 2 4
7 1 8 2
7 4 8 5
8 5 4
1 2 2 1
1 5 2 4
7 1 8 2
7 5 8 4

Example output:
YES
NO
YES
NO

Editorial:
We present two approaches.
Approach 1
Let the letters 'A', 'B', and 'C' correspond to the numbers $$$0$$$, $$$1$$$, and $$$2$$$ modulo $$$3$$$ respectively. Consider drawing an arrow between any two adjacent cells in a great grid pointing to the right or down, and label this arrow with the difference of the two cells modulo $$$3$$$.
The conditions imply that all labels are $$$1$$$ or $$$2$$$, and in each contiguous $$$2 \times 2$$$ subgrid, the top arrow has the same label as the bottom arrow, and the left arrow has the same label as the right arrow. Hence we can associate a type to each of $$$n-1$$$ rows and $$$m-1$$$ columns which is its label. A constraint for cells $$$(x,y)$$$ and $$$(x+1,y+1)$$$ means that row $$$x$$$ and column $$$y$$$ must have different labels, and a constraint for cells $$$(x,y+1)$$$ and $$$(x+1,y)$$$ means that row $$$x$$$ and $$$y$$$ must have the same label.
These relations form a graph, and the problem reduces to a variant of $$$2$$$-colourability, which can be checked using DFS or a DSU.
Approach 2
In a great grid, draw a '/' or '\' for each $$$2 \times 2$$$ subgrid connecting the equal letters.
We can observe that these grids have a simple pattern: every two rows are either the same or opposite. Furthermore, any such pattern corresponds to a great grid (this can be proven with the idea in approach 1). We can associate a type to each row and column, a boolean variable $$$0$$$ or $$$1$$$, such that an entry is '/' or '\' depending on whether the labels are the same or different.
The constraints correspond to entries needing to be '/' or '\', forming a graph of pairs of labels that must be the same or different. Thus the problem reduces to a variant of $$$2$$$-colourability, which can be checked using DFS or a DSU.
The intended time complexity is $$$\mathcal{O}(n+m+k)$$$, although slower implementations with complexities like $$$\mathcal{O}(nm+k)$$$ or $$$\mathcal{O}(k(n+m))$$$ can also pass.