시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 136 34 25 29.412%

문제

"천하제일 게임 대회"는 세계에서 가장 유명한 게임 대회이다.

플레이어들은 다른 모든 플레이어와 한 번씩 1:1로 게임을 진행해야 한다. 승자는 1점을 받고, 패자는 점수를 받지 못한다. 동점인 경우 양측 플레이어 모두 0.5점을 받는다. 모든 경기가 끝난 후, 가장 많은 점수를 받은 플레이어가 대회의 우승자가 된다. 만약 가장 많은 점수를 받은 플레이어가 여러명이 있다면,  우승자를 구할 때까지 타이 브레이크 경기를 진행한다.

도현은 임의의 순서로 게임이 진행되었다는 사실을 알고, 지금까지의 대회 결과를 토대로 누가 대회에서 우승 하는지 예측하려 한다. 우리 모두 도현이를 도와 대회의 결과를 예측해보자.

입력

첫 번째 줄에는 테스트 케이스의 수(T≤100)가 들어온다.

그 다음 줄부터 각 케이스에 대해 들어오는 정보 :  

  • 플레이어의 수 n (2 ≤ n ≤ 30)
  • 그 다음 n개의 줄 만큼 중간 결과를 나타낸다. i행 j열의 값은 i번째 플레이어가 j번째 플레이어와 경기를 한 결과이다 :
    • 이긴 경우 : '1'
    • 진 경우 : '0'
    • 비긴 경우 : 'd'
    • 아직 경기를 하지 않은 경우 : '.'
    • i=j 인 경우(플레이어는 자기 자신과 경기를 하지 않는다.) : 'x'

중간 결과는 모순이 되지 않는다. 즉, i행 j열에 있는 값이 숫자('0' 또는 '1')이면 j행 i열에 있는 값도 다른 숫자이다. 다른 모든 케이스에서도, i행 j열에 있는 값은 j행 i열의 값과 같다.

출력

각 테스트 케이스에 대하여 : 

  • 한 줄마다 경기에 이길 수 있는 모든 승자들의 index를 오름차순으로 공백으로 구분하여 출력한다.

예제 입력 1

3
5
x.11d
.x1d1
00x.0
0d.x.
d01.x
7
x00111.
1x01d.d
11x1.00
000x000
0d.1xd1
0.11dxd
.d110dx
7
x00011.
1x00d.d
11x0.0.
111x111
0d.0xd.
0.10dx.
.d.0..x

예제 출력 1

1 2
1 2 3 5 6 7
4
W3sicHJvYmxlbV9pZCI6IjU0MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjOWNcdWQ1NThcdWM4MWNcdWM3N2MgXHVhYzhjXHVjNzg0IFx1YjMwMFx1ZDY4YyIsImRlc2NyaXB0aW9uIjoiPHA+JnF1b3Q7XHVjYzljXHVkNTU4XHVjODFjXHVjNzdjIFx1YWM4Y1x1Yzc4NCBcdWIzMDBcdWQ2OGMmcXVvdDtcdWIyOTQgXHVjMTM4XHVhY2M0XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM3MjBcdWJhODVcdWQ1NWMgXHVhYzhjXHVjNzg0IFx1YjMwMFx1ZDY4Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViNGU0XHVjNzQwIFx1YjJlNFx1Yjk3OCBcdWJhYThcdWI0ZTAmbmJzcDtcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWM2NDAgXHVkNTVjIFx1YmM4OFx1YzUyOSZuYnNwOzE6MVx1Yjg1YyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjOWM0XHVkNTg5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjMmI5XHVjNzkwXHViMjk0IDFcdWM4MTBcdWM3NDQgXHViYzFiXHVhY2UwLCBcdWQzMjhcdWM3OTBcdWIyOTQgXHVjODEwXHVjMjE4XHViOTdjIFx1YmMxYlx1YzljMCBcdWJhYmJcdWQ1NWNcdWIyZTQuIFx1YjNkOVx1YzgxMFx1Yzc3OCBcdWFjYmRcdWM2YjAmbmJzcDtcdWM1OTFcdWNlMjEgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0IFx1YmFhOFx1YjQ1MCAwLjVcdWM4MTBcdWM3NDQmbmJzcDtcdWJjMWJcdWIyOTRcdWIyZTQuJm5ic3A7XHViYWE4XHViNGUwIFx1YWNiZFx1YWUzMFx1YWMwMCBcdWIwNWRcdWIwOWMgXHVkNmM0LCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWJjMWJcdWM3NDAgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1YjMwMFx1ZDY4Y1x1Yzc1OCBcdWM2YjBcdWMyYjlcdWM3OTBcdWFjMDAgXHViNDFjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc0MCBcdWM4MTBcdWMyMThcdWI5N2MgXHViYzFiXHVjNzQwJm5ic3A7XHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1YzVlY1x1YjdlY1x1YmE4NVx1Yzc3NCBcdWM3ODhcdWIyZTRcdWJhNzQsICZuYnNwO1x1YzZiMFx1YzJiOVx1Yzc5MFx1Yjk3YyBcdWFkNmNcdWQ1NjAgXHViNTRjXHVhZTRjXHVjOWMwIFx1ZDBjMFx1Yzc3NCBcdWJlMGNcdWI4MDhcdWM3NzRcdWQwNmMgXHVhY2JkXHVhZTMwXHViOTdjIFx1YzljNFx1ZDU4OVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2M0XHVkNjA0XHVjNzQwIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI4NWMgXHVhYzhjXHVjNzg0XHVjNzc0IFx1YzljNFx1ZDU4OVx1YjQxOFx1YzVjOFx1YjJlNFx1YjI5NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHVjNTRjXHVhY2UwLCBcdWM5YzBcdWFlMDhcdWFlNGNcdWM5YzBcdWM3NTggXHViMzAwXHVkNjhjIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWQxYTBcdWIzMDBcdWI4NWMgXHViMjA0XHVhYzAwIFx1YjMwMFx1ZDY4Y1x1YzVkMFx1YzExYyBcdWM2YjBcdWMyYjkmbmJzcDtcdWQ1NThcdWIyOTRcdWM5YzAgXHVjNjA4XHVjZTIxXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVjNmIwXHViOWFjIFx1YmFhOFx1YjQ1MCBcdWIzYzRcdWQ2MDRcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1YjMwMFx1ZDY4Y1x1Yzc1OCBcdWFjYjBcdWFjZmNcdWI5N2MgXHVjNjA4XHVjZTIxXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTgoVCZsZTsxMDApXHVhYzAwIFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAmbmJzcDtcdWFjMDEgXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWI0ZTRcdWM1YjRcdWM2MjRcdWIyOTQgXHVjODE1XHViY2Y0IDombmJzcDsmbmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWM3NTggXHVjMjE4IG4gKDIgJmxlOyBuICZsZTsgMzApPFwvbGk+XHJcblx0PGxpPlx1YWRmOCBcdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWM5MDQgXHViOWNjXHVkMDdjIFx1YzkxMVx1YWMwNCBcdWFjYjBcdWFjZmNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBpXHVkNTg5Jm5ic3A7alx1YzVmNFx1Yzc1OCBcdWFjMTJcdWM3NDAmbmJzcDtpXHViYzg4XHVjOWY4Jm5ic3A7XHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIGpcdWJjODhcdWM5ZjggXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVjNjQwIFx1YWNiZFx1YWUzMFx1Yjk3YyBcdWQ1NWMgXHVhY2IwXHVhY2ZjXHVjNzc0XHViMmU0IDpcclxuXHQ8dWw+XHJcblx0XHQ8bGk+XHVjNzc0XHVhZTM0IFx1YWNiZFx1YzZiMCA6Jm5ic3A7JiMzOTsxJiMzOTs8XC9saT5cclxuXHRcdDxsaT5cdWM5YzQgXHVhY2JkXHVjNmIwIDogJiMzOTswJiMzOTs8XC9saT5cclxuXHRcdDxsaT5cdWJlNDRcdWFlMzQgXHVhY2JkXHVjNmIwIDogJiMzOTtkJiMzOTs8XC9saT5cclxuXHRcdDxsaT5cdWM1NDRcdWM5YzEgXHVhY2JkXHVhZTMwXHViOTdjIFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVhY2JkXHVjNmIwIDombmJzcDsmIzM5Oy4mIzM5OzxcL2xpPlxyXG5cdFx0PGxpPmk9aiBcdWM3NzggXHVhY2JkXHVjNmIwKFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCZuYnNwO1x1Yzc5MFx1YWUzMCBcdWM3OTBcdWMyZTBcdWFjZmMgXHVhY2JkXHVhZTMwXHViOTdjIFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuKSZuYnNwOzogJiMzOTt4JiMzOTs8XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM5MTFcdWFjMDQgXHVhY2IwXHVhY2ZjXHViMjk0IFx1YmFhOFx1YzIxY1x1Yzc3NCBcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM5ODksIGlcdWQ1ODkgalx1YzVmNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhYzEyXHVjNzc0IFx1YzIyYlx1Yzc5MCgmIzM5OzAmIzM5OyBcdWI2MTBcdWIyOTQgJiMzOTsxJiMzOTspXHVjNzc0XHViYTc0IGpcdWQ1ODkgaVx1YzVmNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhYzEyXHViM2M0IFx1YjJlNFx1Yjk3OCBcdWMyMmJcdWM3OTBcdWM3NzRcdWIyZTQuIFx1YjJlNFx1Yjk3OCBcdWJhYThcdWI0ZTAgXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwXHVjMTFjXHViM2M0LCBpXHVkNTg5IGpcdWM1ZjRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWMxMlx1Yzc0MCBqXHVkNTg5IGlcdWM1ZjRcdWM3NTggXHVhYzEyXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMgOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1ZDU1YyBcdWM5MDRcdWI5YzhcdWIyZTQmbmJzcDtcdWFjYmRcdWFlMzBcdWM1ZDAgXHVjNzc0XHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwJm5ic3A7XHVjMmI5XHVjNzkwXHViNGU0XHVjNzU4IGluZGV4XHViOTdjIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU0MjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDaGVzcyBDb21wZXRpdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+SW4gYSBjaGVzcyBjb21wZXRpdGlvbiwgZXZlcnkgcGxheWVyIHBsYXlzIG9uZSBnYW1lIGFnYWluc3QgZXZlcnkgb3RoZXIgcGxheWVyLiBUaGUgd2lubmVyIHJlY2VpdmVzIG9uZSBwb2ludCwgdGhlIGxvc2VyIG5vbmUuIEluIGNhc2Ugb2YgYSBkcmF3LCBib3RoIHBsYXllcnMgcmVjZWl2ZSBoYWxmIGEgcG9pbnQuIFdoZW4gYWxsIGdhbWVzIGhhdmUgYmVlbiBwbGF5ZWQsIHdob2V2ZXIgc2NvcmVkIHRoZSBtb3N0IHBvaW50cyB3aW5zIHRoZSBjb21wZXRpdGlvbi4gSWYgbXVsdGlwbGUgY29tcGV0aXRvcnMgYXJlIHRpZWQgZm9yIHRoZSBoaWdoZXN0IHNjb3JlLCB0aGV5IHdpbGwgcGxheSBhIHNlcmllcyBvZiB0aWUtYnJlYWsgZ2FtZXMgdG8gZGV0ZXJtaW5lIHRoZSB3aW5uZXIuPFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIHByb2JsZW0gd2UgY29uc2lkZXIgYSBjb21wZXRpdGlvbiB3aGVyZSB0aGUgZ2FtZXMgYXJlIHBsYXllZCBpbiBhcmJpdHJhcnkgb3JkZXIuIEJhc2VkIG9uIHRoZSBvdXRjb21lIG9mIHRoZSBnYW1lcyB0aGF0IGhhdmUgYmVlbiBwbGF5ZWQgc28gZmFyICh3aGljaCBjb3VsZCBiZSBhbGwsIG9yIG5vbmUsIG9yIGFueXRoaW5nIGluIGJldHdlZW4pIHRoZSBvcmdhbml6ZXJzIHdhbnQgdG8gZGV0ZXJtaW5lIHdoaWNoIHBsYXllcnMgY2FuIHN0aWxsIHdpbiB0aGUgY29tcGV0aXRpb24uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIG4gKDIgJmxlOyBuICZsZTsgMzApOiB0aGUgbnVtYmVyIG9mIHBsYXllcnMuPFwvbGk+XHJcblx0PGxpPm4gbGluZXMgd2l0aCBuIGNoYXJhY3RlcnMgZWFjaCwgZGVzY3JpYmluZyB0aGUgaW50ZXJtZWRpYXRlIHJlc3VsdHMuIFRoZSBqLXRoIGNoYXJhY3RlciBvbiB0aGUgaS10aCBsaW5lIGdpdmVzIHRoZSByZXN1bHQgb2YgdGhlIGktdGggcGxheWVyIGFnYWluc3QgdGhlIGotdGggcGxheWVyOlxyXG5cdDx1bD5cclxuXHRcdDxsaT4mcnNxdW87MSZyc3F1bzsgZm9yIGEgd2luLDxcL2xpPlxyXG5cdFx0PGxpPiZyc3F1bzswJnJzcXVvOyBmb3IgYSBsb3NzLDxcL2xpPlxyXG5cdFx0PGxpPiZyc3F1bztkJnJzcXVvOyBmb3IgYSBkcmF3LDxcL2xpPlxyXG5cdFx0PGxpPiZyc3F1bzsuJnJzcXVvOyBpZiB0aGlzIGdhbWUgaGFzIG5vdCBiZWVuIHBsYXllZCB5ZXQsPFwvbGk+XHJcblx0XHQ8bGk+JnJzcXVvO3gmcnNxdW87IHdoZW4gaSA9IGogKHNpbmNlIGNvbXBldGl0b3JzIGRvIG5vdCBwbGF5IGFnYWluc3QgdGhlbXNlbHZlcykuPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIGludGVybWVkaWF0ZSByZXN1bHRzIGFyZSBndWFyYW50ZWVkIHRvIGJlIGludGVybmFsbHkgY29uc2lzdGVudC4gTW9yZSBmb3JtYWxseSwgaWYgdGhlIGotdGggY2hhcmFjdGVyIG9uIHRoZSBpLXRoIGxpbmUgaXMgYSBkaWdpdCAoJnJzcXVvOzAmcnNxdW87IG9yICZyc3F1bzsxJnJzcXVvOykgdGhlbiB0aGUgaS10aCBjaGFyYWN0ZXIgb24gdGhlIGotdGggbGluZSB3aWxsIGJlIHRoZSBvdGhlciBkaWdpdC4gSW4gYWxsIG90aGVyIGNhc2VzLCB0aGUgai10aCBjaGFyYWN0ZXIgb24gdGhlIGktdGggbGluZSBlcXVhbHMgdGhlIGktdGggY2hhcmFjdGVyIG9uIHRoZSBqLXRoIGxpbmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHRoZSAxLWJhc2VkIGluZGljZXMgb2YgYWxsIHRoZSBwbGF5ZXJzIHRoYXQgY2FuIHBvc3NpYmx5IHdpbiB0aGUgY29tcGV0aXRpb24sIGluIGluY3JlYXNpbmcgb3JkZXIsIHNlcGFyYXRlZCBieSBzcGFjZXMuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=