문제
"천하제일 게임 대회"는 세계에서 가장 유명한 게임 대회이다.
플레이어들은 다른 모든 플레이어와 한 번씩 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열의 값과 같다.
출력
각 테스트 케이스에 대하여 한 줄마다 경기에 이길 수 있는 모든 승자들의 번호를 오름차순으로 공백으로 구분하여 출력한다.
예제
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 2
1 2 3 5 6 7
4
로그인해야 코드를 작성할 수 있어요.