题目描述

$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