P14616 [2019 KAIST RUN Fall] Gosu 2

Ho is an expert in martial arts called $\textit{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 $\textit{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 $\textbf{standard ranking chain}$ and assign other students with respect to such a chain. A $\textbf{standard ranking chain}$ of length $K$, is a sequence of $K$ different students $S_1, S_2, \ldots, 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 $s_i$ consisting of $\texttt{W}$, $\texttt{L}$, and $\texttt{-}$, 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}=$ $\texttt{-}$, if $i=j$. - $s_{i,j}=$ $\texttt{W}$, if student $i$ won student $j$. - $s_{i,j}=$ $\texttt{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} =$ $\texttt{-}$ ($1 \le i \le N$) - If $i \neq j$, then $s_{i, j}=$ $\texttt{W}$ or $s_{i, j}=$ $\texttt{L}$. ($1 \le i \le N$) - If $s_{i, j} = $ $\texttt{W}$, then $s_{j, i} = $ $\texttt{L}$. ($1 \le i,\ j \le N$) - If $s_{i, j} = $ $\texttt{L}$, then $s_{j, i} = $ $\texttt{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.