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

Однако всегда есть место для совершенствования. В качестве корпоративной цели на этот год иерархия будет пересмотрена чтобы гарантировать, что каждый раз, когда человек A непосредственно контролируется человеком B, то B в то же время косвенно контролируется A. Мы говорим, что B косвенно контролируется A, если существует n > 2 и такая последовательность (c1, . .. cn), что c1 = A, cn = B и для каждого i < n , ci является непосредственным руководителем ci+1).

По словам руководителей это гарантирует, что любой сотрудник дважды подумает, прежде чем решить злоупотребить своей властью над кем-то другим.

Неудивительно, однако, что кто-то может немного разозлиться, если узнает, что его подчиненный был внезапно назначен его начальником. И некоторые такие решения могут вызвать больше негодования, чем другие. Ваша задача - выполнить корпоративную цель, обратив некоторые зависимости между сотрудниками таким образом, чтобы сумма обид по поводу этих изменений была как можно меньше.

Входные данные

Первая строка содержит количество тестов z (1 ≤ z ≤ 100). Далее следуют описания тестов.

Первая строка каждого набора входных данных содержит одно целое число n (1 ≤ n ≤ 2000) - количество сотрудников. Сотрудники пронумерованы от 1 до n.

Затем следуют n строк, содержащих n целых чисел di,j каждая (0 ≤ di,j ≤ 2 * 10^ 9). Если сотрудник i является непосредственным руководителем сотрудника j, то di,j > 0 описывает обиду, которую i испытал бы, если бы эта зависимость перевернутой. В противном случае (то есть, если j является непосредственным руководителем i или если i = j), то di,j = 0 .

Общее количество сотрудников во всех тестах не превышает 10000.

Выходные данные

Для каждого теста найдите решение, которое гарантирует, что для любой пары сотрудников i, j (1 ≤ i, j ≤ n, i ≠ j), либо i будет непосредственным руководителем j, либо j будет косвенным руководителем i , или наоборот. Ваше решение должно свести к минимуму сумму недовольства сотрудников. Если существует более одного такого решения, вы можете вывести любое из них.

Если решения не существует, выведите слово "NO".

В противном случае в первой строке выведите слово "YES". Во второй строке выведите два целых числа k и r - количество зависимостей между сотрудниками, которые вы собираетесь обратить, и достигнутая сумма обид соответственно. Обратите внимание, что вам не нужно минимизировать k.

Затем выведите k строк, по два целых числа в каждой - идентификаторы сотрудников a, b (1 ≤ a, b ≤ n, a ≠ b), так что a в настоящее время является непосредственным руководителем b, и их отношения должны измениться на противоположные. Не следует выводить одну и ту же пару сотрудников более одного раза.