Королевства
Королевства
Несколько королевств столкнулись с серьезными финансовыми трудностями. В течение многих лет они тайно занимали все больше и больше денег друг у друга. Теперь, когда разоблачены их обязательства, крах неизбежен ...
Имеется n королевств. Для каждой пары королевств (A, B) количество золота, которое королевство A обязано вернуть королевству B, выражается целым числом dAB
(мы предполагаем, что dBA
= -dAB
). Если королевство имеет отрицательное сальдо (должно платить больше, чем может получить), оно может обанкротиться. Банкротство удаляет все обязательства, как положительные, так и отрицательные, как если бы королевство перестало существовать. Затем следующее королевство может обанкротиться и так далее, пока все остальные королевства не станут финансово стабильными.
В зависимости от того, кто падает первым, могут возникнуть разные сценарии. В частности, иногда может остаться только одно королевство. Определите для каждого королевства, сможет ли оно стать единственным выжившим.
Входные данные
Первая строка содержит количество тестов t. Описания тестов приведены ниже:
Описание каждого теста начинается со строки, содержащей количество королевств n (1 ≤ n ≤ 20). Затем следуют n строк, каждая из которых содержит n чисел. j-ое число в i-ой строке - это количество dij
золотых монет, которое i-ое королевство должно вернуть j-ому. Можете считать, что dii
= 0 и dij
= -dji
для каждого 1 ≤ i, j ≤ n. Также |dij|
≤ 106
для всех возможных i, j.
Выходные данные
Для каждого теста выведите одну строку, содержащую индексы королевств, которые могут стать единственными выжившими, в порядке возрастания. Если таких королевств нет, выведите одно число 0.
1 3 0 -3 1 3 0 -2 -1 2 0
1 3