Công ty nơi bạn đang làm việc đã quyết định đẩy ý tưởng về cấu trúc tổ chức phẳng đến giới hạn của nó: với mọi cặp nhân viên $A$ và $B$, hoặc $A$ đã được chỉ định để giám sát trực tiếp công việc của $B$, hoặc $B$ đã được chỉ định để giám sát trực tiếp công việc của $A$. Tất nhiên, điều này có nghĩa là một người có thể có khá nhiều cấp trên trực tiếp... điều này thật tuyệt vời, vì nó làm cho nhân viên cảm thấy công việc của họ thực sự quan trọng đối với rất nhiều người thay vì chỉ một người quản lý duy nhất, các giám đốc điều hành cho biết.

Tuy nhiên, luôn có chỗ để cải thiện. Là mục tiêu của công ty trong năm nay, hệ thống phân cấp sẽ được sửa đổi để đảm bảo rằng bất cứ khi nào một người $A$ được giám sát trực tiếp bởi một người $B$, thì $A$ cũng được giám sát gián tiếp bởi $B$ cùng một lúc (chúng ta nói rằng $A$ được giám sát gián tiếp bởi $B$ nếu tồn tại $n > 2$ và một dãy $(c_1, \dots, c_n)$ sao cho $c_1 = B, c_n = A$ và với mỗi $i < n$, $c_i$ là cấp trên trực tiếp của $c_{i+1}$).

Các giám đốc điều hành cho biết điều này sẽ đảm bảo rằng bất kỳ nhân viên nào cũng sẽ suy nghĩ kỹ trước khi quyết định lạm dụng quyền lực của mình đối với bất kỳ ai khác.

Tuy nhiên, không có gì ngạc nhiên khi một người có thể cảm thấy hơi khó chịu nếu họ biết rằng cấp dưới của mình đột nhiên được bổ nhiệm làm cấp trên của họ. Và một số quyết định như vậy có thể gây ra sự phẫn nộ nhiều hơn những quyết định khác. Nhiệm vụ của bạn là hoàn thành mục tiêu của công ty bằng cách đảo ngược một số mối quan hệ phụ thuộc giữa các nhân viên sao cho tổng mức độ phẫn nộ đối với những thay đổi này là nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số lượng bộ test $z$ ($1 \le z \le 100$). Các mô tả của các bộ test theo sau. Dòng đầu tiên của mỗi bộ test chứa một số nguyên duy nhất $n$ ($1 \le n \le 2000$) – số lượng nhân viên. Các nhân viên được đánh số từ 1 đến $n$.

Sau đó là $n$ dòng, mỗi dòng chứa $n$ số nguyên $d_{i,j}$ ($0 \le d_{i,j} \le 2 \cdot 10^9$). Nếu nhân viên $i$ là cấp trên trực tiếp của nhân viên $j$, thì $d_{i,j} > 0$ mô tả mức độ phẫn nộ mà $j$ sẽ cảm thấy nếu mối quan hệ phụ thuộc này bị đảo ngược. Ngược lại (tức là nếu $j$ là cấp trên trực tiếp của $i$ hoặc nếu $i = j$), $d_{i,j} = 0$.

Tổng số nhân viên trong tất cả các bộ test không vượt quá 10000.

Dữ liệu ra

Đối với mỗi bộ test, hãy đưa ra một giải pháp đảm bảo rằng, với bất kỳ cặp nhân viên $i, j$ ($1 \le i, j \le n, i \neq j$), hoặc $i$ sẽ là cấp trên trực tiếp của $j$ và $j$ sẽ là cấp trên gián tiếp của $i$, hoặc ngược lại. Giải pháp của bạn nên giảm thiểu tổng mức độ phẫn nộ mà các nhân viên sẽ cảm thấy. Nếu tồn tại nhiều hơn một giải pháp như vậy, bạn có thể in bất kỳ giải pháp nào trong số đó.

Nếu không tồn tại giải pháp, bạn nên xuất ra một dòng duy nhất chứa từ “NO”.

Nếu không, ở dòng đầu tiên, hãy xuất ra một từ duy nhất “YES”. Ở dòng thứ hai, in hai số nguyên $k$ và $r$ – số lượng các mối quan hệ phụ thuộc giữa các nhân viên mà bạn dự định đảo ngược và tổng mức độ phẫn nộ đạt được tương ứng. Lưu ý rằng bạn không cần phải giảm thiểu $k$.

Sau đó, xuất ra $k$ dòng, mỗi dòng chứa hai số nguyên – định danh của các nhân viên $a, b$ ($1 \le a, b \le n, a \neq b$) sao cho $a$ hiện đang là cấp trên trực tiếp của $b$ và mối quan hệ của họ cần được đảo ngược. Bạn không bao giờ được xuất ra cùng một cặp nhân viên nhiều hơn một lần.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

YES
2 10
4 5
2 4