路障
题目描述
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)$ 将被摆上路障。
输出格式
对于每一组数据,输出 `Yes` 或 `No`,回答 B 君能否走到 $(n,n)$。
输入输出样例
输入样例 #1
2
2
1 1
2 2
5
3 3
3 2
3 1
1 2
1 3
1 4
1 5
2 2
输出样例 #1
Yes
Yes
说明
样例解释:
以下 0 表示能走,x 表示不能走,B 表示 B 君现在的位置。从左往右表示时间。
```
Case 1:
0 0 0 0 0 B (已经走到了)
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君可以走到终点)
```
数据规模:
防止骗分,数据保证全部手造。
对于 $20\%$ 的数据,有 $n\le3$。
对于 $60\%$ 的数据,有 $n\le500$。
对于 $100\%$ 的数据,有 $n\le1000$。
对于 $100\%$ 的数据,有 $T\le10$。