你目前就职的公司决定将扁平化组织结构的概念推向极致：对于每一对员工 $A$ 和 $B$，要么 $A$ 被指派直接监督 $B$ 的工作，要么 $B$ 被指派直接监督 $A$ 的工作。当然，这意味着一个人现在可能会有很多直接主管……高管们说，这很棒，因为它让员工觉得他们的工作对很多人来说都很重要，而不仅仅是对单一的经理。

不过，总有改进的空间。作为今年的公司目标，层级结构将被修订，以确保每当一个人 $A$ 被一个人 $B$ 直接监督时，同时 $A$ 也被 $B$ 间接监督（我们称 $A$ 被 $B$ 间接监督，如果存在 $n > 2$ 以及一个序列 $(c_1, \dots, c_n)$，使得 $c_1 = B$，$c_n = A$，且对于每个 $i < n$，$c_i$ 是 $c_{i+1}$ 的直接主管）。

高管们说，这将确保任何员工在决定滥用职权对付他人之前都会三思而后行。

然而，如果员工发现他们曾经的下属突然被任命为他们的主管，感到有些恼火也就不足为奇了。而且，其中一些决定可能会比其他决定引起更多的怨恨。你的任务是通过反转员工之间的一些从属关系来达成公司目标，使得这些变动带来的怨恨总和尽可能小。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 100$)。接下来是各测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2000$) —— 员工人数。员工编号从 $1$ 到 $n$。 接下来有 $n$ 行，每行包含 $n$ 个整数 $d_{i,j}$ ($0 \le d_{i,j} \le 2 \cdot 10^9$)。如果员工 $i$ 是员工 $j$ 的直接主管，则 $d_{i,j} > 0$ 表示如果该从属关系被反转，员工 $i$ 会感到的怨恨值。否则（即如果 $j$ 是 $i$ 的直接主管，或者 $i = j$），$d_{i,j} = 0$。 所有测试用例中的员工总数不超过 $10000$。

输出格式

对于每个测试用例，请给出一个解决方案，确保对于任意一对员工 $i, j$ ($1 \le i, j \le n, i \neq j$)，要么 $i$ 是 $j$ 的直接主管且 $j$ 是 $i$ 的间接主管，要么反之亦然。你的解决方案应使员工感到的怨恨总和最小。如果存在多个这样的解决方案，你可以输出其中任意一个。

如果不存在解决方案，输出一行包含单词 “NO”。 否则，第一行输出单词 “YES”。第二行输出两个整数 $k$ 和 $r$ —— 你打算反转的从属关系数量以及达到的怨恨总和。注意，你不需要最小化 $k$。 接下来输出 $k$ 行，每行包含两个整数 —— 员工标识符 $a, b$ ($1 \le a, b \le n, a \neq b$)，表示 $a$ 当前是 $b$ 的直接主管，且他们的关系应该被反转。你输出的每一对员工必须是唯一的。

样例

输入 1

1
5
0 1 0 6 11
0 0 1 6 12
2 0 0 7 12
0 0 0 0 4
0 0 0 0 0

输出 1

YES
2 10
4 5
2 4