고수 2

Ho는 태보라는 무술의 고수다. 그녀는 태보 학교를 운영하고 있고, 학교에는 $N$명의 학생이 있다. 태보 학교 내부의 경쟁을 키우기 위해, 그녀는 모든 학생에게 순위를 부여하는 태보 랭킹 웹사이트를 만들려고 한다. 적절한 순위를 정하기 위해, Ho는 $N(N-1)/2$개의 모든 학생 쌍이 서로 태보 대결을 하도록 했다. 태보 대결에서는 정확히 한 명이 이기고 다른 한 명이 진다. 태보 대결의 결과는 그리 단순하지 않을 수 있다. 예를 들어 학생 A가 B를 이기고, B가 C를 이기고, C가 A를 이기는 경우가 있을 수 있다. 이런 상황에서는 세 학생 중 확실한 승자가 없으므로 순위를 매기기가 꽤 복잡해진다.

이 문제를 해결하기 위해, Ho는 표준 랭킹 체인을 찾고 그 체인을 기준으로 다른 학생들의 순위를 매길 것이다. 길이 $K$의 표준 랭킹 체인은 $K$명의 서로 다른 학생 $S_1,\ S_2,\ \cdots,\ S_k$의 수열로서, $i < j$일 때 그리고 그때만 $S_i$가 $S_j$를 이긴다. 다시 말해, $S_1$은 체인에 있는 다른 모든 학생을 이길 수 있고, $S_2$는 $S_1$을 제외한 체인의 다른 모든 학생을 이길 수 있고, $S_3$은 $S_1, S_2$를 제외한 체인의 다른 모든 학생을 이길 수 있으며, 이런 식으로 이어져 $S_k$는 체인에 있는 어떤 학생도 이길 수 없다. Ho의 웹사이트는 이런 체인을 기준으로 다른 학생들의 순위를 매기므로, 순위를 정하기가 더 쉬워진다.

Ho는 태보 고수일 뿐만 아니라 수학 천재이기도 하다. Ho는 어떤 태보 대결 결과에 대해서도 길이 $1 + \lfloor \log_2(N) \rfloor$의 표준 랭킹 체인을 찾을 수 있다는 것을 알고 있다. 여기서 $\log_2(N)$은 밑이 2인 로그다. 다시 말해, $2^{k-1} \le N$인 모든 $k \geq 1$에 대해, Ho는 그런 길이의 표준 랭킹 체인을 찾을 수 있다.

Ho는 컴퓨터 프로그래밍도 매우 잘하지만 조금 게으르기 때문에, 이 일을 당신에게 맡긴다. 당신은 길이가 정확히 $1 + \lfloor \log_2(N) \rfloor$인 표준 랭킹 체인을 찾아야 한다.

첫 번째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스마다 다음 입력이 주어진다.

첫 번째 줄에 학생 수 $N$이 주어진다.

다음 $N$개의 줄 중 $i$번째 줄에 W, L, -로 이루어진 길이 $N$의 문자열 $s_i$가 주어진다. $s_i$의 $j$번째 문자를 $s_{i,\ j}$라고 하자. $s_{i,\ j}$는 다음과 같이 주어진다.

• $i=j$이면 $s_{i,\ j}=$ -

• 학생 $i$가 학생 $j$를 이겼으면 $s_{i,\ j}=$ W

• 학생 $j$가 학생 $i$를 이겼으면 $s_{i,\ j}=$ L

• $1 \le T \le 250\,000$

• $1 \le N \le 512$

• 모든 테스트 케이스에 대한 $N^2$의 합은 $2\,500\,000$을 넘지 않는다.

• $s_{i, i} =$ - ($1 \le i \le N$)

• $i \neq j$이면 $s_{i, j}=$ W 또는 $s_{i, j}=$ L이다. ($1 \le i \le N$)

• $s_{i, j} =$ W이면 $s_{j, i} =$ L이다. ($1 \le i,\ j \le N$)

• $s_{i, j} =$ L이면 $s_{j, i} =$ W이다. ($1 \le i,\ j \le N$)

각 테스트 케이스마다 정확히 $1 + \lfloor \log_2(N) \rfloor$개의 정수를 한 줄에 출력한다. 이 정수들은 표준 랭킹 체인에 속한 학생들을 실력 순서대로 나타낸다. 이러한 체인은 모든 가능한 입력에 대해 존재한다는 것을 증명할 수 있다.