±1
Contest: Codeforces Round 944 (Div. 4)
Difficulty rating: 2100
Tags: 2-sat, dfs and similar, graphs

Bob has a grid with $$$3$$$ rows and $$$n$$$ columns, each of which contains either $$$a_i$$$ or $$$-a_i$$$ for some integer $$$1 \leq i \leq n$$$. For example, one possible grid for $$$n=4$$$ is shown below:

$$$$$$\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 and Bob play a game as follows:

- Bob shows Alice his grid.
- Alice gives Bob an array $$$a_1, a_2, \dots, a_n$$$ of her choosing, whose elements are all $$$\mathbf{-1}$$$ or $$$\mathbf{1}$$$.
- Bob substitutes these values into his grid to make a grid of $$$-1$$$s and $$$1$$$s.
- Bob sorts the elements of each column in non-decreasing order.
- Alice wins if all the elements in the middle row are $$$1$$$; otherwise, Bob wins.

For example, suppose Alice gives Bob the array $$$[1, -1, -1, 1]$$$ for the grid above. Then the following will happen (colors are added for clarity):

$$$$$$\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{sort each column}} \begin{bmatrix} -1 & -1 & -1 & 1 \\ \mathbf{1} & \mathbf{1} & \mathbf{1} & \mathbf{1} \\ 1 & 1 & 1 & 1 \\ \end{bmatrix}\,. $$$$$$ Since the middle row is all $$$1$$$, Alice wins.

Given Bob's grid, determine whether or not Alice can choose the array $$$a$$$ to win the game.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 500$$$) — the number of columns of Bob's grid.

The next three lines each contain $$$n$$$ integers, the $$$i$$$-th of which contains $$$g_{i,1}, g_{i,2}, \dots, g_{i,n}$$$ ($$$-n \leq g_{i,j} \leq n$$$, $$$g_{i,j} \neq 0$$$), representing Bob's grid.

If cell $$$x > 0$$$ is in the input, that cell in Bob's grid should contain $$$a_x$$$; if $$$x < 0$$$ is in the input, that cell in Bob's grid should contain $$$-a_{-x}$$$. See the sample input and notes for a better understanding.

Output format:
For each test case, output "YES" (without quotes) if Alice can win, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes", and "Yes" will be recognized as a positive response).

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

Note:
The first test case is described in the statement.

In the second test case, Bob's grid is as follows:

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

For the last column to have $$$1$$$ in the middle row when sorted, Alice must pick $$$a_2 = -1$$$. However, it is then impossible to choose $$$a_1$$$ such that the first column has $$$1$$$ in the middle when sorted. Thus, Alice cannot win.

In the third test case, Alice can pick $$$a = [1,1,1,1,1]$$$.

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

Example output:
YES
NO
YES
NO

Editorial:
The problem statement is somewhat reminiscent of SAT. Indeed, treating $$$+1$$$ as true and $$$-1$$$ as false, we have clauses of length $$$3$$$, and we need at least $$$2$$$ of the variables to be true.
We can reduce this to 2-SAT with the following observation: at least $$$2$$$ of $$$(x,y,z)$$$ are true $$$\iff$$$ at least one of $$$(x,y)$$$ is true, at least one of $$$(y,z)$$$ is true, and at least one of $$$(z,x)$$$ is true. That is, for each column of the grid, we make three 2-SAT clauses. Then we just run 2-SAT on these clauses, and output if there is a solution. The time complexity is $$$\mathcal{O}(n)$$$ per test case.
It might be time-consuming to code 2-SAT during the contest, so we recommend using some standard library (for example, our solution uses AtCoder library).