시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 114 28 21 30.882%

문제

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

플레이어들은 다른 모든 플레이어와 한 번씩 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+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOChUJmxlOzEwMClcdWFjMDAgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMCZuYnNwO1x1YWMwMSBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YjRlNFx1YzViNFx1YzYyNFx1YjI5NCBcdWM4MTVcdWJjZjQgOiZuYnNwOyZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1Yzc1OCBcdWMyMTggbiAoMiAmbGU7IG4gJmxlOyAzMCk8XC9saT5cclxuXHQ8bGk+XHVhZGY4IFx1YjJlNFx1Yzc0YyBuXHVhYzFjXHVjNzU4IFx1YzkwNCBcdWI5Y2NcdWQwN2MgXHVjOTExXHVhYzA0IFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIGlcdWQ1ODkmbmJzcDtqXHVjNWY0XHVjNzU4IFx1YWMxMlx1Yzc0MCZuYnNwO2lcdWJjODhcdWM5ZjgmbmJzcDtcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgalx1YmM4OFx1YzlmOCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWM2NDAgXHVhY2JkXHVhZTMwXHViOTdjIFx1ZDU1YyBcdWFjYjBcdWFjZmNcdWM3NzRcdWIyZTQgOlxyXG5cdDx1bD5cclxuXHRcdDxsaT5cdWM3NzRcdWFlMzQgXHVhY2JkXHVjNmIwIDombmJzcDsmIzM5OzEmIzM5OzxcL2xpPlxyXG5cdFx0PGxpPlx1YzljNCBcdWFjYmRcdWM2YjAgOiAmIzM5OzAmIzM5OzxcL2xpPlxyXG5cdFx0PGxpPlx1YmU0NFx1YWUzNCBcdWFjYmRcdWM2YjAgOiAmIzM5O2QmIzM5OzxcL2xpPlxyXG5cdFx0PGxpPlx1YzU0NFx1YzljMSBcdWFjYmRcdWFlMzBcdWI5N2MgXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWFjYmRcdWM2YjAgOiZuYnNwOyYjMzk7LiYjMzk7PFwvbGk+XHJcblx0XHQ8bGk+aT1qIFx1Yzc3OCBcdWFjYmRcdWM2YjAoXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0Jm5ic3A7XHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1YWNmYyBcdWFjYmRcdWFlMzBcdWI5N2MgXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4pJm5ic3A7OiAmIzM5O3gmIzM5OzxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzkxMVx1YWMwNCBcdWFjYjBcdWFjZmNcdWIyOTQgXHViYWE4XHVjMjFjXHVjNzc0IFx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1Yzk4OSwgaVx1ZDU4OSBqXHVjNWY0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjMTJcdWM3NzQgXHVjMjJiXHVjNzkwKCYjMzk7MCYjMzk7IFx1YjYxMFx1YjI5NCAmIzM5OzEmIzM5OylcdWM3NzRcdWJhNzQgalx1ZDU4OSBpXHVjNWY0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjMTJcdWIzYzQgXHViMmU0XHViOTc4IFx1YzIyYlx1Yzc5MFx1Yzc3NFx1YjJlNC4gXHViMmU0XHViOTc4IFx1YmFhOFx1YjRlMCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWMxMWNcdWIzYzQsIGlcdWQ1ODkgalx1YzVmNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhYzEyXHVjNzQwIGpcdWQ1ODkgaVx1YzVmNFx1Yzc1OCBcdWFjMTJcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYyA6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVkNTVjIFx1YzkwNFx1YjljOFx1YjJlNCZuYnNwO1x1YWNiZFx1YWUzMFx1YzVkMCBcdWM3NzRcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAmbmJzcDtcdWMyYjlcdWM3OTBcdWI0ZTRcdWM3NTggaW5kZXhcdWI5N2MgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTQyNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNoZXNzIENvbXBldGl0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBhIGNoZXNzIGNvbXBldGl0aW9uLCBldmVyeSBwbGF5ZXIgcGxheXMgb25lIGdhbWUgYWdhaW5zdCBldmVyeSBvdGhlciBwbGF5ZXIuIFRoZSB3aW5uZXIgcmVjZWl2ZXMgb25lIHBvaW50LCB0aGUgbG9zZXIgbm9uZS4gSW4gY2FzZSBvZiBhIGRyYXcsIGJvdGggcGxheWVycyByZWNlaXZlIGhhbGYgYSBwb2ludC4gV2hlbiBhbGwgZ2FtZXMgaGF2ZSBiZWVuIHBsYXllZCwgd2hvZXZlciBzY29yZWQgdGhlIG1vc3QgcG9pbnRzIHdpbnMgdGhlIGNvbXBldGl0aW9uLiBJZiBtdWx0aXBsZSBjb21wZXRpdG9ycyBhcmUgdGllZCBmb3IgdGhlIGhpZ2hlc3Qgc2NvcmUsIHRoZXkgd2lsbCBwbGF5IGEgc2VyaWVzIG9mIHRpZS1icmVhayBnYW1lcyB0byBkZXRlcm1pbmUgdGhlIHdpbm5lci48XC9wPlxyXG5cclxuPHA+Rm9yIHRoaXMgcHJvYmxlbSB3ZSBjb25zaWRlciBhIGNvbXBldGl0aW9uIHdoZXJlIHRoZSBnYW1lcyBhcmUgcGxheWVkIGluIGFyYml0cmFyeSBvcmRlci4gQmFzZWQgb24gdGhlIG91dGNvbWUgb2YgdGhlIGdhbWVzIHRoYXQgaGF2ZSBiZWVuIHBsYXllZCBzbyBmYXIgKHdoaWNoIGNvdWxkIGJlIGFsbCwgb3Igbm9uZSwgb3IgYW55dGhpbmcgaW4gYmV0d2VlbikgdGhlIG9yZ2FuaXplcnMgd2FudCB0byBkZXRlcm1pbmUgd2hpY2ggcGxheWVycyBjYW4gc3RpbGwgd2luIHRoZSBjb21wZXRpdGlvbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFuIGludGVnZXIgbiAoMiAmbGU7IG4gJmxlOyAzMCk6IHRoZSBudW1iZXIgb2YgcGxheWVycy48XC9saT5cclxuXHQ8bGk+biBsaW5lcyB3aXRoIG4gY2hhcmFjdGVycyBlYWNoLCBkZXNjcmliaW5nIHRoZSBpbnRlcm1lZGlhdGUgcmVzdWx0cy4gVGhlIGotdGggY2hhcmFjdGVyIG9uIHRoZSBpLXRoIGxpbmUgZ2l2ZXMgdGhlIHJlc3VsdCBvZiB0aGUgaS10aCBwbGF5ZXIgYWdhaW5zdCB0aGUgai10aCBwbGF5ZXI6XHJcblx0PHVsPlxyXG5cdFx0PGxpPiZyc3F1bzsxJnJzcXVvOyBmb3IgYSB3aW4sPFwvbGk+XHJcblx0XHQ8bGk+JnJzcXVvOzAmcnNxdW87IGZvciBhIGxvc3MsPFwvbGk+XHJcblx0XHQ8bGk+JnJzcXVvO2QmcnNxdW87IGZvciBhIGRyYXcsPFwvbGk+XHJcblx0XHQ8bGk+JnJzcXVvOy4mcnNxdW87IGlmIHRoaXMgZ2FtZSBoYXMgbm90IGJlZW4gcGxheWVkIHlldCw8XC9saT5cclxuXHRcdDxsaT4mcnNxdW87eCZyc3F1bzsgd2hlbiBpID0gaiAoc2luY2UgY29tcGV0aXRvcnMgZG8gbm90IHBsYXkgYWdhaW5zdCB0aGVtc2VsdmVzKS48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgaW50ZXJtZWRpYXRlIHJlc3VsdHMgYXJlIGd1YXJhbnRlZWQgdG8gYmUgaW50ZXJuYWxseSBjb25zaXN0ZW50LiBNb3JlIGZvcm1hbGx5LCBpZiB0aGUgai10aCBjaGFyYWN0ZXIgb24gdGhlIGktdGggbGluZSBpcyBhIGRpZ2l0ICgmcnNxdW87MCZyc3F1bzsgb3IgJnJzcXVvOzEmcnNxdW87KSB0aGVuIHRoZSBpLXRoIGNoYXJhY3RlciBvbiB0aGUgai10aCBsaW5lIHdpbGwgYmUgdGhlIG90aGVyIGRpZ2l0LiBJbiBhbGwgb3RoZXIgY2FzZXMsIHRoZSBqLXRoIGNoYXJhY3RlciBvbiB0aGUgaS10aCBsaW5lIGVxdWFscyB0aGUgaS10aCBjaGFyYWN0ZXIgb24gdGhlIGotdGggbGluZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggdGhlIDEtYmFzZWQgaW5kaWNlcyBvZiBhbGwgdGhlIHBsYXllcnMgdGhhdCBjYW4gcG9zc2libHkgd2luIHRoZSBjb21wZXRpdGlvbiwgaW4gaW5jcmVhc2luZyBvcmRlciwgc2VwYXJhdGVkIGJ5IHNwYWNlcy48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==