Плоская организация
Компания, в которой Вы в настоящее время работаете, решила довести идею плоской организационной структуры до предела: для каждой пары сотрудников A и B либо A назначен непосредственным руководителем работника B, или B назначен непосредственным руководителем работника A. Это означает, что теперь у человека может быть довольно много непосредственных начальников. И это здорово, потому что это заставляет сотрудника чувствовать, что его работа действительно важна для многих людей, а не только для одного менеджера - так говорят руководители.
Однако всегда есть место для совершенствования. В качестве корпоративной цели на этот год иерархия будет пересмотрена чтобы гарантировать, что каждый раз, когда человек A непосредственно контролируется человеком B, то B в то же время косвенно контролируется A. Мы говорим, что B косвенно контролируется A, если существует n > 2 и такая последовательность (c[1]
, . .. c[n]
), что c[1]
= A, c[n]
= B и для каждого i < n , c[i]
является непосредственным руководителем c[i+1]
).
По словам руководителей это гарантирует, что любой сотрудник дважды подумает, прежде чем решить злоупотребить своей властью над кем-то другим.
Неудивительно, однако, что кто-то может немного разозлиться, если узнает, что его подчиненный был внезапно назначен его начальником. И некоторые такие решения могут вызвать больше негодования, чем другие. Ваша задача - выполнить корпоративную цель, обратив некоторые зависимости между сотрудниками таким образом, чтобы сумма обид по поводу этих изменений была как можно меньше.
Входные данные
Первая строка содержит количество тестов z (1 ≤ z ≤ 100). Далее следуют описания тестов.
Первая строка каждого набора входных данных содержит одно целое число n (1 ≤ n ≤ 2000) - количество сотрудников. Сотрудники пронумерованы от 1 до n.
Затем следуют n строк, содержащих n целых чисел d[i,j]
каждая (0 ≤ d[i,j]
≤ 2 * 10^ 9
). Если сотрудник i является непосредственным руководителем сотрудника j, то d[i,j]
> 0 описывает обиду, которую i испытал бы, если бы эта зависимость перевернутой. В противном случае (то есть, если j является непосредственным руководителем i или если i = j), то d[i,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, и их отношения должны измениться на противоположные. Не следует выводить одну и ту же пару сотрудников более одного раза.