Background

Description

B stands on an $n \times n$ chessboard. At the beginning, B is at $(1,1)$ and wants to go to $(n,n)$.

Each second, B can move one cell in one of the four directions: up, down, left, or right. However, C plans to stop B.

At the end of each second, C will place a roadblock at $(x,y)$. B cannot step on a roadblock.

B knows in advance where C will place the roadblocks. Now you need to determine whether B can reach $(n,n)$.

It is guaranteed that the testdata is weak enough: that is, you do not need to consider the case where B moves to some cell and then gets killed by a roadblock dropping onto that cell, because such cases will not appear in the answers.

Output Format

For each test case, output Yes or No, answering whether B can reach $(n,n)$.

2

2
1 1
2 2

5
3 3
3 2
3 1
1 2
1 3
1 4
1 5
2 2

Yes
Yes

Hint

Sample explanation:

Here 0 means passable, x means blocked, and B means B's current position. From left to right represents time.

Case 1:
0 0    0 0    0 B  (already reached)
B 0    x B    x 0

Case 2:
0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0
0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0
0 0 0 0 0    0 0 x 0 0    0 0 x 0 0    0 0 x 0 0
0 0 0 0 0    0 0 0 0 0    0 0 x 0 0    0 0 x 0 0
B 0 0 0 0    0 B 0 0 0    0 0 B 0 0    0 0 x B 0 ......(B can reach the target)

Constraints:

• To prevent score farming, all testdata are handcrafted.
• For $20\%$ of the testdata, $n \le 3$.
• For $60\%$ of the testdata, $n \le 500$.
• For $100\%$ of the testdata, $n \le 1000$.
• For $100\%$ of the testdata, $T \le 10$.

Translated by ChatGPT 5