题目描述

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.

5
1
-
2
-W
L3
-LW
W-L
LW4
-WLW
L-WL
WL-W
LWL5
-WLLW
L-LLW
WW-LL
WWW-W
LLWL

1
1 2
3 2
3 1 4
4 3 1