Компания, в которой вы работаете, решила довести идею плоской организационной структуры до предела: для каждой пары сотрудников $A$ и $B$ либо $A$ был назначен непосредственным руководителем $B$, либо $B$ был назначен непосредственным руководителем $A$. Конечно, это означает, что теперь у человека может быть довольно много непосредственных руководителей... что замечательно, поскольку это заставляет сотрудника чувствовать, что его работа действительно важна для стольких людей, а не только для одного начальника, говорят руководители.

Однако всегда есть возможности для улучшения. В качестве корпоративной цели на этот год иерархия будет пересмотрена, чтобы гарантировать, что всякий раз, когда человек $A$ является непосредственным руководителем человека $B$, то $B$ также одновременно косвенно руководит $A$ (мы говорим, что $B$ косвенно руководит $A$, если существует $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