SP329 CALLS - Calls

年轻的考古学家 Senoj Anaidni 最近发现了一些重要的文物，可能会让他一举成名。这些文物看起来像是古代电话公司的广告传单。他发现，现代的电话公司在制作传单时遵循一些基本的原则，而古代公司应该也是如此。 每家电话公司经营一定数量的电话线路。每条线路连接一对城市，并且可以双向使用。使用每条线路的费用为固定的正数。从城市 A 打电话到城市 B 时，可以直接拨打或通过其他城市中转。在中转情况下，通话费是所有使用线路费用的总和。有时，通过中转反而能更便宜，即便存在直接的连接。 为了让客户更容易理解，电话公司会罗列出所有服务城市对之间的最低通话费用。为了给客户留下深刻印象，公司还会标注其运营的线路数量。 Senoj 发现的每张古代传单开头都是这么写的：“我们使用 47 条电话线路，服务世界上最重要的 10 个城市！从斯巴达到特洛伊的通话费用为 12 丹尼罗，从斯巴达到雅典的费用为 15 丹尼罗……” 饱含了所有城市对之间的最廉价通话费用。 这似乎支持了 Senoj 对文物来源的假设，但他不太确定这些文物是否真实。其他考古学家经常戏弄他，制作一些假冒伪劣的文物来让他出丑。幸运的是，他们通常不够细心，所以我们可以假设，一张传单如果不能由任何电话公司发布，那它就是伪造的。

输入的第一行给定 Senoj 找到的传单数量 $t$。 \[$t \leq 50$\] 每张传单在一个独立的块中描述，块的第一行包含两个整数 $N$ 和 $K$，其中 $N$ 是城市数量，$K$ 是电话线路的数量。 \[$N \leq 300, K \leq 1200$\] 接下来的 $N-1$ 行表示所有城市对之间的最低通话费用。第 $i$ 行包含 $N-i$ 个数字，第 $j$ 个数字代表城市 $i$ 和城市 $i+j$ 之间的通话费用。

对于每个输入块，输出一行“YES”或“NO”。如果可以给公司运营的电话线路分配一组费用，这样让公布的最低通话费用成立，输出“YES”；否则输出“NO”。 **本翻译由 AI 自动生成**