Несколько королевств столкнулись с серьезными финансовыми трудностями. В течение многих лет они тайно занимали все больше и больше денег друг у друга. Теперь, когда разоблачены их обязательства, крах неизбежен ...
Имеется n королевств. Для каждой пары королевств (A, B) количество золота, которое королевство A обязано вернуть королевству B, выражается целым числом d[AB]
(мы предполагаем, что d[BA]
= -d[AB]
). Если королевство имеет отрицательное сальдо (должно платить больше, чем может получить), оно может обанкротиться. Банкротство удаляет все обязательства, как положительные, так и отрицательные, как если бы королевство перестало существовать. Затем следующее королевство может обанкротиться и так далее, пока все остальные королевства не станут финансово стабильными.
В зависимости от того, кто падает первым, могут возникнуть разные сценарии. В частности, иногда может остаться только одно королевство. Определите для каждого королевства, сможет ли оно стать единственным выжившим.
Первая строка содержит количество тестов t. Описания тестов приведены ниже:
Описание каждого теста начинается со строки, содержащей количество королевств n (1 ≤ n ≤ 20). Затем следуют n строк, каждая из которых содержит n чисел. j-ое число в i-ой строке - это количество d[ij]
золотых монет, которое i-ое королевство должно вернуть j-ому. Можете считать, что d[ii]
= 0 и d[ij]
= -d[ji]
для каждого 1 ≤ i, j ≤ n. Также |d[ij]|
≤ 10^6
для всех возможных i, j.
Для каждого теста выведите одну строку, содержащую индексы королевств, которые могут стать единственными выжившими, в порядке возрастания. Если таких королевств нет, выведите одно число 0.