시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 214 52 33 22.603%

문제

몇몇 왕국은 심각한 경제적 어려움을 겪고 있다. 수년 동안, 그들은 비밀리에 서로 돈을 점점 더 많이 빌려왔다. 이제 그들의 부채가 드러났으니 충돌은 불가피하다..

n개의 왕국이 있다. 왕국의 각 쌍 (A, B)에 대해, A왕국이 B왕국에게 빚지고 있는 금의 양은 정수 dAB 로 표현한다. (dBA = -dAB 라고 가정한다.) 왕국의 잔고가 음수일 경우(받을 수 있는 돈보다 더 많은 돈을 지불해야하는 경우), 왕국은 파산할 수 있다. 파산은 왕국이 더이상 존재하지 않는 것처럼 양과 음의 모든 부채를 없앤다. 다음 왕국은 모든 남은 왕국들이 재정적으로 안정 될 때까지 파산할 수 있다.

누가 먼저 파산하는지에 따라, 시나리오가 달라질 수 있다. 특히, 어떤 경우에는 단 하나의 왕국만이 남을 수도 있다. 모든 왕국에 대해, 그 왕국이 유일한 생존국이 될 수 있는지의 여부를 구해라.

입력

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 테스트 케이스에 대한 설명은 다음과 같다.

각 테스트 케이스는 왕국의 개수 n으로 시작된다. (1<=n<=20) 

다음 n개의 줄에는 각각 공백으로 구분된 n개의 숫자들이 주어진다.

i번째 줄의 j번째 수는 i번째 왕국이 j번째 왕국에게 빚지고 있는 금의 양인 dij를 의미한다. 

모든 1<=i,j<=n에 대해 dii = 0 이고 dij = -dji 이다. 또한, 가능한 모든 i,j에 대해 |dij|<=106 이다.

출력

테스트케이스에 대한 답을 입력에 표시된 순서대로 출력해라. 각각의 테스트케이스에 대해, 유일한 생존자가 될 수 있는 왕국의 번호를 오름차순에 따라 한줄로 출력하라. 그러한 왕국이 없다면, 0을 출력해라.

예제 입력 1

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

예제 출력 1

1 3
W3sicHJvYmxlbV9pZCI6IjM0MDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMGNcdWMwYjBcdWQ1NThcdWIyOTQgXHVjNjU1XHVhZDZkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJhODdcdWJhODcgXHVjNjU1XHVhZDZkXHVjNzQwIFx1YzJlY1x1YWMwMVx1ZDU1YyBcdWFjYmRcdWM4MWNcdWM4MDEgXHVjNWI0XHViODI0XHVjNmMwXHVjNzQ0IFx1YWNhYVx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzIxOFx1YjE0NCBcdWIzZDlcdWM1NDgsIFx1YWRmOFx1YjRlNFx1Yzc0MCBcdWJlNDRcdWJjMDBcdWI5YWNcdWM1ZDAgXHVjMTFjXHViODVjIFx1YjNjOFx1Yzc0NCBcdWM4MTBcdWM4MTAgXHViMzU0IFx1YjljZVx1Yzc3NCBcdWJlNGNcdWI4MjRcdWM2NTRcdWIyZTQuIFx1Yzc3NFx1YzgxYyBcdWFkZjhcdWI0ZTRcdWM3NTggXHViZDgwXHVjYzQ0XHVhYzAwIFx1YjRkY1x1YjdlY1x1YjBhY1x1YzczY1x1YjJjOCBcdWNkYTlcdWIzY2NcdWM3NDAgXHViZDg4XHVhYzAwXHVkNTNjXHVkNTU4XHViMmU0Li48XC9wPlxyXG5cclxuPHA+blx1YWMxY1x1Yzc1OCBcdWM2NTVcdWFkNmRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM2NTVcdWFkNmRcdWM3NTggXHVhYzAxIFx1YzMwZCAoQSwgQilcdWM1ZDAgXHViMzAwXHVkNTc0LCBBXHVjNjU1XHVhZDZkXHVjNzc0IEJcdWM2NTVcdWFkNmRcdWM1ZDBcdWFjOGMgXHViZTVhXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWFlMDhcdWM3NTggXHVjNTkxXHVjNzQwIFx1YzgxNVx1YzIxOCBkPHN1Yj5BQiZuYnNwOzxcL3N1Yj5cdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTVjXHViMmU0LiAoZDxzdWI+QkE8XC9zdWI+ID0gLWQ8c3ViPkFCJm5ic3A7PFwvc3ViPlx1Yjc3Y1x1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NWNcdWIyZTQuKSBcdWM2NTVcdWFkNmRcdWM3NTggXHVjNzk0XHVhY2UwXHVhYzAwIFx1Yzc0Y1x1YzIxOFx1Yzc3YyBcdWFjYmRcdWM2YjAoXHViYzFiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViM2M4XHViY2Y0XHViMmU0IFx1YjM1NCBcdWI5Y2VcdWM3NDAgXHViM2M4XHVjNzQ0IFx1YzljMFx1YmQ4OFx1ZDU3NFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjApLCBcdWM2NTVcdWFkNmRcdWM3NDAgXHVkMzBjXHVjMGIwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDMwY1x1YzBiMFx1Yzc0MCBcdWM2NTVcdWFkNmRcdWM3NzQgXHViMzU0XHVjNzc0XHVjMGMxIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhYzgzXHVjYzk4XHViN2ZjIFx1YzU5MVx1YWNmYyBcdWM3NGNcdWM3NTggXHViYWE4XHViNGUwIFx1YmQ4MFx1Y2M0NFx1Yjk3YyBcdWM1YzZcdWM1NjRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM2NTVcdWFkNmRcdWM3NDAgXHViYWE4XHViNGUwIFx1YjBhOFx1Yzc0MCBcdWM2NTVcdWFkNmRcdWI0ZTRcdWM3NzQgXHVjN2FjXHVjODE1XHVjODAxXHVjNzNjXHViODVjIFx1YzU0OFx1YzgxNSBcdWI0MjAgXHViNTRjXHVhZTRjXHVjOWMwIFx1ZDMwY1x1YzBiMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyMDRcdWFjMDAgXHViYTNjXHVjODAwIFx1ZDMwY1x1YzBiMFx1ZDU1OFx1YjI5NFx1YzljMFx1YzVkMCBcdWI1MzBcdWI3N2MsIFx1YzJkY1x1YjA5OFx1YjlhY1x1YzYyNFx1YWMwMCBcdWIyZWNcdWI3N2NcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkMmI5XHVkNzg4LCBcdWM1YjRcdWI1YTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YjJlOCBcdWQ1NThcdWIwOThcdWM3NTggXHVjNjU1XHVhZDZkXHViOWNjXHVjNzc0IFx1YjBhOFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjNjU1XHVhZDZkXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVhZGY4IFx1YzY1NVx1YWQ2ZFx1Yzc3NCBcdWM3MjBcdWM3N2NcdWQ1NWMgXHVjMGRkXHVjODc0XHVhZDZkXHVjNzc0IFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwXHVjNzU4IFx1YzVlY1x1YmQ4MFx1Yjk3YyBcdWFkNmNcdWQ1NzRcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzEyNFx1YmE4NVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM2NTVcdWFkNmRcdWM3NTggXHVhYzFjXHVjMjE4IG5cdWM3M2NcdWI4NWMgXHVjMmRjXHVjNzkxXHViNDFjXHViMmU0LiAoMSZsdDs9biZsdDs9MjApJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDFcdWFjMDEgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxYyBuXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNzU4IGpcdWJjODhcdWM5ZjggXHVjMjE4XHViMjk0IGlcdWJjODhcdWM5ZjggXHVjNjU1XHVhZDZkXHVjNzc0IGpcdWJjODhcdWM5ZjggXHVjNjU1XHVhZDZkXHVjNWQwXHVhYzhjIFx1YmU1YVx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVhZTA4XHVjNzU4IFx1YzU5MVx1Yzc3OCBkPHN1Yj5pajxcL3N1Yj5cdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgMSZsdDs9aSxqJmx0Oz1uXHVjNWQwIFx1YjMwMFx1ZDU3NCBkPHN1Yj5paTxcL3N1Yj4gPSAwIFx1Yzc3NFx1YWNlMCBkPHN1Yj5pajxcL3N1Yj4gPSAtZDxzdWI+amkmbmJzcDs8XC9zdWI+XHVjNzc0XHViMmU0LiBcdWI2MTBcdWQ1NWMsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJhYThcdWI0ZTAgaSxqXHVjNWQwIFx1YjMwMFx1ZDU3NCB8ZDxzdWI+aWo8XC9zdWI+fCZsdDs9MTA8c3VwPjY8XC9zdXA+IFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjJmNVx1Yzc0NCBcdWM3ODVcdWI4MjVcdWM1ZDAgXHVkNDVjXHVjMmRjXHViNDFjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWI3N2MuJm5ic3A7XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1YzcyMFx1Yzc3Y1x1ZDU1YyBcdWMwZGRcdWM4NzRcdWM3OTBcdWFjMDAgXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNjU1XHVhZDZkXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM1ZDAgXHViNTMwXHViNzdjIFx1ZDU1Y1x1YzkwNFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWM2NTVcdWFkNmRcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0LCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNDA1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS2luZ2RvbXMiLCJkZXNjcmlwdGlvbiI6IjxwPlNldmVyYWwga2luZ2RvbXMgZ290IGludG8gc2VyaW91cyBmaW5hbmNpYWwgdHJvdWJsZXMuIEZvciBtYW55IHllYXJzLCB0aGV5IGhhdmUgYmVlbiBzZWNyZXRseSBib3Jyb3dpbmcgbW9yZSBhbmQgbW9yZSBtb25leSBmcm9tIGVhY2ggb3RoZXIuIE5vdywgd2l0aCB0aGVpciBsaWFiaWxpdGllcyBleHBvc2VkLCB0aGUgY3Jhc2ggaXMgaW5ldml0YWJsZS4uLjxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgbiBraW5nZG9tcy4gRm9yIGVhY2ggcGFpciAoQSwgQikgb2Yga2luZ2RvbXMsIHRoZSBhbW91bnQgb2YgZ29sZCB0aGF0IGtpbmdkb20gQSBvd2VzIHRvIGtpbmdkb20gQiBpcyBleHByZXNzZWQgYnkgYW4gaW50ZWdlciBudW1iZXIgZDxzdWI+QUI8XC9zdWI+ICh3ZSBhc3N1bWUgdGhhdCBkPHN1Yj5CQTxcL3N1Yj4gPSAmbWludXM7ZDxzdWI+QUI8XC9zdWI+KS4gSWYgYSBraW5nZG9tIGhhcyBuZWdhdGl2ZSBiYWxhbmNlIChoYXMgdG8gcGF5IG1vcmUgdGhhbiBpdCBjYW4gcmVjZWl2ZSksIGl0IG1heSBiYW5rcnVwdC4gQmFua3J1cHRjeSByZW1vdmVzIGFsbCBsaWFiaWxpdGllcywgYm90aCBwb3NpdGl2ZSBhbmQgbmVnYXRpdmUsIGFzIGlmIHRoZSBraW5nZG9tIGNlYXNlZCB0byBleGlzdC4gVGhlIG5leHQga2luZ2RvbSBtYXkgdGhlbiBiYW5rcnVwdCwgYW5kIHNvIG9uLCB1bnRpbCBhbGwgcmVtYWluaW5nIGtpbmdkb21zIGFyZSBmaW5hbmNpYWxseSBzdGFibGUuPFwvcD5cclxuXHJcbjxwPkRlcGVuZGluZyBvbiB3aG8gZmFsbHMgZmlyc3QsIGRpZmZlcmVudCBzY2VuYXJpb3MgbWF5IG9jY3VyJm1kYXNoO2luIHBhcnRpY3VsYXIsIHNvbWV0aW1lcyBvbmx5IG9uZSBraW5nZG9tIG1pZ2h0IHJlbWFpbi4gRGV0ZXJtaW5lLCBmb3IgZXZlcnkga2luZ2RvbSwgd2hldGhlciBpdCBjYW4gYmVjb21lIHRoZSBvbmx5IHN1cnZpdm9yLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBULiBUaGUgZGVzY3JpcHRpb25zIG9mIHRoZSB0ZXN0IGNhc2VzIGZvbGxvdzo8XC9wPlxyXG5cclxuPHA+VGhlIGRlc2NyaXB0aW9uIG9mIGVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIHRoZSBudW1iZXIgb2YgdGhlIGtpbmdkb21zIG4sIDEgJmxlOyBuICZsZTsgMjAuIFRoZW4gbiBsaW5lcyBmb2xsb3csIGVhY2ggY29udGFpbmluZyBuIHNwYWNlLXNlcGFyYXRlZCBudW1iZXJzLiBUaGUgai10aCBudW1iZXIgaW4gdGhlIGktdGggbGluZSBpcyB0aGUgbnVtYmVyIGQ8c3ViPmlqPFwvc3ViPiBvZiBnb2xkIGNvaW5zIHRoYXQgdGhlIGktdGgga2luZ2RvbSBvd2VzIHRvIHRoZSBqLXRoIG9uZS4gWW91IG1heSBhc3N1bWUgdGhhdCBkPHN1Yj5paTxcL3N1Yj4gPSAwIGFuZCBkPHN1Yj5pajxcL3N1Yj4gPSAmbWludXM7ZDxzdWI+amk8XC9zdWI+IGZvciBldmVyeSAxICZsZTsgaSwgaiAmbGU7IG4uIEFsc28sIHxkPHN1Yj5pajxcL3N1Yj58ICZsZTsgMTA8c3VwPjY8XC9zdXA+IGZvciBhbGwgcG9zc2libGUgaSwgai48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgYW5zd2VycyB0byB0aGUgdGVzdCBjYXNlcyBpbiB0aGUgb3JkZXIgaW4gd2hpY2ggdGhleSBhcHBlYXIgaW4gdGhlIGlucHV0LiBGb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgaW5kaWNlcyBvZiB0aGUga2luZ2RvbXMgdGhhdCBjYW4gYmVjb21lIHRoZSBzb2xlIHN1cnZpdm9ycywgaW4gaW5jcmVhc2luZyBvcmRlci4gSWYgdGhlcmUgYXJlIG5vIHN1Y2gga2luZ2RvbXMsIHByaW50IGEgc2luZ2xlIG51bWJlciAwPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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