题目描述

2020 年 5 月，国际航班一票难求。一位在美国华盛顿的中国留学生，因为一些原因必须在本周内回到北京。现在已知各个机场之间的航班情况，求问他回不回得来（不考虑转机次数和机票价格）。

输入格式

第一行为 case 个数 $n\ (n < 10)$。

每一个 case，第一行为机场个数 $N$，$N ≤ 10$。

之后的 $N$ 行，每一行包含 $N$ 个整数。第 $i$（$1 ≤ i ≤ N$）行的第 $j$（$1 ≤ j ≤ N$）个整数代表从第 $i$ 个机场出发到第 $j$ 个机场的能买到的航班的最低票价 $t$（$0 < t < 10000$）。如果不幸没有航班，那么用 $-1$ 表示。

第 $i$ 行第 $i$ 个整数为 $0$。起点华盛顿杜勒斯国际机场的编号为 $1$，终点北京首都国际机场的编号为 $N$。

输出格式

每一个 case 一行。能够回国，输出字符串 YES。如果无法回国，输出字符串 NO。

2
3
0 100 -1
-1 0 200
-1 -1 0
4
0 1 5 -1
3 0 1 -1
2 4 0 -1
4 1 1 0

YES
NO