你目前任職的公司決定將扁平化組織結構的概念發揮到極致：對於每一對員工 $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