CF1844E.Great Grids

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.

一个 $n \times m$ 的字符网格被称为“优秀网格”，当且仅当它满足以下三个条件：

• 每个字符均为 'A'、'B' 或 'C' 之一；
• 每个 $2 \times 2$ 的连续子网格都包含全部三种不同的字母；
• 任意两个共享一条公共边的格子中，字符互不相同。

记 $(x,y)$ 表示从上往下第 $x$ 行、从左往右第 $y$ 列的格子。

你需要构造一个满足 $k$ 个约束条件的优秀网格。每个约束条件由两个恰好共享一个顶点（即对角相邻）的格子 $(x_{i,1},y_{i,1})$ 和 $(x_{i,2},y_{i,2})$ 组成；你要求在这两个格子中填入相同的字母。

判断是否存在一个满足所有约束条件的优秀网格。

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} \lt 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 \lt 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$.

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^3$）。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n,m \le 2 \cdot 10^3$，$1 \le k \le 4 \cdot 10^3$）。

接下来的 $k$ 行中，每行包含四个整数 $x_{i,1}$、$y_{i,1}$、$x_{i,2}$ 和 $y_{i,2}$（$1 \le x_{i,1} \lt x_{i,2} \le n$，$1 \le y_{i,1},y_{i,2} \le m$）。保证对每个 $i$，要么 $(x_{i,2},y_{i,2}) = (x_{i,1}+1,y_{i,1}+1)$，要么 $(x_{i,2},y_{i,2}) = (x_{i,1}+1,y_{i,1}-1)$。

这些单元格对两两互异，即对所有 $1 \le i \lt j \le k$，不同时满足 $x_{i,1} = x_{j,1}$、$y_{i,1} = y_{j,1}$、$x_{i,2} = x_{j,2}$ 且 $y_{i,2} = y_{j,2}$。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^3$。

保证所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^3$。

保证所有测试用例中 $k$ 的总和不超过 $4 \cdot 10^3$。

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.

对于每个测试用例，如果存在满足所有约束条件的优秀网格，则输出 “YES”，否则输出 “NO”。

你可以以任意大小写形式输出答案（大写或小写）。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被识别为肯定回答。

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

B

A

B

C

C

B

C

A

A

C

A

B

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.

在第一个测试用例中，以下优秀的网格满足所有约束条件：

B

A

B

C

C

B

C

A

A

C

A

B

在第二个测试用例中，两条约束意味着单元格 $(1,1)$ 与 $(2,2)$ 具有相同的字母，且单元格 $(1,2)$ 与 $(2,1)$ 具有相同的字母，这使得唯一的 $2 \times 2$ 子网格无法包含全部三种不同的字母。