题目描述

Bob 有一个 $3$ 行 $n$ 列的网格，每个格子中包含 $a_i$ 或 $-a_i$，其中 $1 \leq i \leq n$，$a_i$ 是某个整数。例如，当 $n=4$ 时，可能的一个网格如下：

$$\begin{bmatrix} a_1 & -a_2 & -a_3 & -a_2 \\ -a_4 & a_4 & -a_1 & -a_3 \\ a_1 & a_2 & -a_2 & a_4 \end{bmatrix}$$

Alice 和 Bob 玩如下的游戏：

• Bob 向 Alice 展示他的网格。
• Alice 给 Bob 一个数组 $a_1, a_2, \cdots, a_n$，其中每个元素都是 $-1$ 或 $1$。
• Bob 用这些值替换网格中的 $a_i$，使得网格中的每个元素都变为 $-1$ 或 $1$。
• Bob 对每一列的元素进行非递减排序。
• 如果排序后中间一行的所有元素都是 $1$，则 Alice 获胜；否则 Bob 获胜。

例如，对于上面的网格，假设 Alice 给出数组 $[1, -1, -1, 1]$，则过程如下（为便于理解添加了颜色）：

$$\begin{bmatrix} \color{red}{a_1} & \color{green}{-a_2} & \color{blue}{-a_3} & \color{green}{-a_2} \\ -a_4 & a_4 & \color{red}{-a_1} & \color{blue}{-a_3} \\ \color{red}{a_1} & \color{green}{a_2} & \color{green}{-a_2} & a_4 \end{bmatrix} \xrightarrow{[\color{red}{1},\color{green}{-1},\color{blue}{-1},1]} \begin{bmatrix} \color{red}{1} & \color{green}{1} & \color{blue}{1} & \color{green}{1} \\ -1 & 1 & \color{red}{-1} & \color{blue}{1} \\ \color{red}{1} & \color{green}{-1} & \color{green}{1} & 1 \end{bmatrix} \xrightarrow{\text{对每一列排序}} \begin{bmatrix} -1 & -1 & -1 & 1 \\ \mathbf{1} & \mathbf{1} & \mathbf{1} & \mathbf{1} \\ 1 & 1 & 1 & 1 \\ \end{bmatrix}$$

由于中间一行全为 $1$，所以 Alice 获胜。给定 Bob 的网格，判断 Alice 是否可以选择数组 $a$ 使自己获胜。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 500$），表示 Bob 的网格的列数。

接下来的三行，每行包含 $n$ 个整数，第 $i$ 个分别为 $g_{i,1}, g_{i,2}, \dots, g_{i,n}$（$-n \leq g_{i,j} \leq n$，$g_{i,j} \neq 0$），表示 Bob 的网格。

如果输入中的某个格子为 $x>0$，则该格子应填入 $a_x$；如果为 $x<0$，则该格子应填入 $-a_{-x}$。具体可参考样例输入和说明。

输出格式

对于每个测试用例，如果 Alice 能获胜，输出 YES，否则输出 NO。

你可以用任意大小写输出 YES 和 NO（例如 yEs、yes、Yes 都视为肯定回答）。

样例

4
4
1 -2 -3 -2
-4 4 -1 -3
1 2 -2 4
2
1 2
-1 -2
2 -2
5
1 2 3 4 5
-2 3 -4 -5 -1
3 -5 1 2 2
6
1 3 -6 2 5 2
1 3 -2 -3 -6 -5
-2 -1 -3 2 3 1

YES
NO
YES
NO

样例说明

第一个测试用例已在题目描述中给出。

第二个测试用例中，Bob 的网格如下：

$$\begin{bmatrix} a_1 & a_2 \\ -a_1 & -a_2 \\ a_2 & -a_2 \end{bmatrix}$$

要使最后一列排序后中间一行为 $1$，Alice 必须选择 $a_2 = -1$。但此时无法选择 $a_1$ 使得第一列排序后中间一行为 $1$，因此 Alice 无法获胜。

第三个测试用例中，Alice 可以选择 $a = [1,1,1,1,1]$。

由 ChatGPT 4.1 翻译

来源

Codeforces 1971H，英文题名 ±1。