시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 37 16 10 35.714%

문제

Several kingdoms got into serious financial troubles. For many years, they have been secretly borrowing more and more money from each other. Now, with their liabilities exposed, the crash is inevitable...

There are n kingdoms. For each pair (A, B) of kingdoms, the amount of gold that kingdom A owes to kingdom B is expressed by an integer number dAB (we assume that dBA = −dAB). If a kingdom has negative balance (has to pay more than it can receive), it may bankrupt. Bankruptcy removes all liabilities, both positive and negative, as if the kingdom ceased to exist. The next kingdom may then bankrupt, and so on, until all remaining kingdoms are financially stable.

Depending on who falls first, different scenarios may occur—in particular, sometimes only one kingdom might remain. Determine, for every kingdom, whether it can become the only survivor.

입력

The first line of the input contains the number of test cases T. The descriptions of the test cases follow:

The description of each test case starts with a line containing the number of the kingdoms n, 1 ≤ n ≤ 20. Then n lines follow, each containing n space-separated numbers. The j-th number in the i-th line is the number dij of gold coins that the i-th kingdom owes to the j-th one. You may assume that dii = 0 and dij = −dji for every 1 ≤ i, j ≤ n. Also, |dij| ≤ 106 for all possible i, j.

출력

Print the answers to the test cases in the order in which they appear in the input. For each test case, print a single line containing the indices of the kingdoms that can become the sole survivors, in increasing order. If there are no such kingdoms, print a single number 0

예제 입력

1
3
0 -3 1
3 0 -2
-1 2 0

예제 출력

1 3

힌트

출처

ACM-ICPC > Regionals > Europe > Central European Regional Contest > CERC 2012 A번

  • 문제의 오타를 찾은 사람: appa