P3395 Roadblocks

# 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.

B 君站在一个 $n\times n$ 的棋盘上。最开始，B君站在 $(1,1)$ 这个点，他要走到 $(n,n)$ 这个点。 B 君每秒可以向上下左右的某个方向移动一格，但是很不妙，C 君打算阻止 B 君的计划。 **每秒结束的时刻**，C 君 会在 $(x,y)$ 上摆一个路障。B 君不能走在路障上。 B 君拿到了 C 君准备在哪些点放置路障。所以现在你需要判断，B 君能否成功走到 $(n,n)$。 **保证数据足够弱：也就是说，无需考虑“走到某处然后被一个路障砸死”的情况，因为答案不会出现此类情况。**

首先是一个正整数 $T$，表示数据组数。 对于每一组数据： 第一行，一个正整数 $n$。 接下来 $2n-2$ 行，每行两个正整数 $x$ 和 $y$，意义是在那一秒结束后，$(x,y)$ 将被摆上路障。

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

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