Description

Ho 是一种名为 跆博（Taebo）的武术专家。她经营着一所跆博学校，学校里有 $N$ 名学生。为了增加学校内部的竞争，她打算创建一个 跆博排名网站，为所有学生分配一定的排名。为了找到合适的排名，Ho 让所有 $N(N-1)/2$ 对学生相互进行了跆博对决。在跆博对决中，恰好有一人获胜，另一人失败。跆博对决的结果可能并不简单：例如，可能存在学生 A 击败 B，B 击败 C，而 C 击败 A 的情况。这种情况会使排名分配变得相当复杂，因为无法从这三名学生中确定明确的胜者。

为了解决这个问题，Ho 将找到一个 标准排名链，并基于该链为其他学生分配排名。一个长度为 $K$ 的 标准排名链 是一个由 $K$ 名不同学生组成的序列 $S_1, S_2, \ldots, S_k$，满足 $S_i$ 击败 $S_j$ 当且仅当 $i < 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$ 的标准排名链。

Input Format

第一行给出测试用例的数量 $T$。对于每个测试用例，给出以下信息：

第一行给出学生数量 $N$。

接下来的 $N$ 行中，第 $i$ 行给出一个由字符 $\texttt{W}$、$\texttt{L}$ 和 $\texttt{-}$ 组成的字符串 $s_i$。记 $s_i$ 的第 $j$ 个字符为 $s_{i,j}$。$s_{i,j}$ 的给出规则如下：

• 若 $i = j$，则 $s_{i,j} = \texttt{-}$。
• 若学生 $i$ 击败了学生 $j$，则 $s_{i,j} = \texttt{W}$。
• 若学生 $j$ 击败了学生 $i$，则 $s_{i,j} = \texttt{L}$。

约束条件：

• $1 \le T \le 250,000$
• $1 \le N \le 512$
• 所有测试用例的 $N^2$ 之和不超过 $2,500,000$
• $s_{i, i} = \texttt{-}$（$1 \le i \le N$）
• 若 $i \neq j$，则 $s_{i, j} = \texttt{W}$ 或 $s_{i, j} = \texttt{L}$（$1 \le i \le N$）
• 若 $s_{i, j} = \texttt{W}$，则 $s_{j, i} = \texttt{L}$（$1 \le i, j \le N$）
• 若 $s_{i, j} = \texttt{L}$，则 $s_{j, i} = \texttt{W}$（$1 \le i, j \le N$）

Output Format

对于每个测试用例，在一行中输出恰好 $1 + \lfloor \log_2(N) \rfloor$ 个整数，表示标准排名链中的学生编号，按技能顺序排列。可以证明对于所有可能的输入，这样的链总是存在的。

5
1
-
2
-W
L-
3
-LW
W-L
LW-
4
-WLW
L-WL
WL-W
LWL-
5
-WLLW
L-LLW
WW-LL
WWW-W
LLWL-

1
1 2
3 2
3 1 4
4 3 1

Hint

翻译由 DeepSeek V3 完成