17512번 - Gosu 2 스페셜 저지다국어

Ho is an expert in martial arts called Taebo. She runs a Taebo school, and there are $N$ students in her school. To increase the inner competition inside the Taebo school, she is going to make a Taebo ranking website which assigns all students to a certain rank. To find a suitable rank, Ho made all $N(N-1)/2$ pairs of students do a Taebo matchup with each other. In a Taebo matchup, exactly one person wins the match, and another person loses the match. The outcome of Taebo matchups may not be very simple: For example, there might be a case that student A beats B, B beats C, and C beats A. Such situation would make the ranking assignment pretty complicated as there is no definite winner from those three students.

To overcome the issue, Ho will find a standard ranking chain and assign other students with respect to such a chain. A standard ranking chain of length $K$, is a sequence of $K$ different students $S_1,\ S_2,\ \cdots,\ S_k$ such that $S_i$ beats $S_j$ if and only if $i < j$. In other words, $S_1$ can beat all other students in the chain, $S_2$ can beat all other students in the chain except $S_1$, $S_3$ can beat all other students in the chain except $S_1, S_2$, and so on, and $S_k$ can beat no other student in the chain. Ho's website will assign other students based on such a chain, which will make the assignment easier.

Ho is not only an expert in Taebo, but she is a math genius too. Ho knows, that for any Taebo matchup, she can find the standard ranking chain of length $1 + \lfloor \log_2(N) \rfloor$, where $\log_2(N)$ is a base 2 logarithm. In other words, for any $k \geq 1$ such that $2^{k-1} \le N$, Ho can find a standard ranking chain of such a length. 

While Ho is very good at computer programming too, she is a little bit lazy, therefore she delegates her work to you. You should find a standard ranking chain of length exactly $1 + \lfloor \log_2(N) \rfloor$.

In the first line, the number of test cases $T$ is given. For each test case, the following instances are given:

In the first line, the number of students $N$ is given.

In the $i$-th line of the next $N$ lines, a string of $N$ characters, $s_i$, consisting of W, L, and - is given. Let's denote the $j$-th character of $s_i$ as $s_{i,\ j}$. $s_{i,\ j}$ is given as follows:

• $s_{i,\ j}=$ -, if $i=j$.
• $s_{i,\ j}=$ W, if student $i$ won student $j$.
• $s_{i,\ j}=$ L, if student $j$ won student $i$.

• $1 \le T \le 250\,000$
• $1 \le N \le 512$
• The sum of $N^2$ for all test cases does not exceed $2\,500\,000$.
• $s_{i, i} =$ - ($1 \le i \le N$)
• If $i \neq j$, then $s_{i, j}=$ W or $s_{i, j}=$ L. ($1 \le i \le N$)
• If $s_{i, j} = $ W, then $s_{j, i} = $ L. ($1 \le i,\ j \le N$)
• If $s_{i, j} = $ L, then $s_{j, i} = $ W. ($1 \le i,\ j \le N$)

For each test case, print exactly $1 + \lfloor \log_2(N) \rfloor$ integers in a single line, denoting the students in a standard ranking chain in the order of their skills. It can be proved that such a chain exists for every possible input.