题目描述

Ho 是一种名为 跆搏 的武术的专家。她经营着一所跆搏学校，学校里有 $N$ 名学生。由于 Ho 年事已高，无法继续教授跆搏，她打算将学校交给她的其中一名学生。为了找到合适的候选人，Ho 让所有 $\frac{N(N-1)}{2}$ 对学生彼此之间进行了一场跆搏对决，并记录了所有结果。在一场跆搏对决中，恰好有一人获胜，另一人落败。Ho 认为，如果一名学生是跆搏的 高手，那么他就足够优秀来继承她的学校。

高手（Gosu） 是一个韩语词汇，意指在游戏、运动、竞技编程等方面非常出色的人。在跆搏中，高手有着不同的含义。

让我们定义从选手 $x$ 到选手 $y$ 的一条 获胜路径 为一个包含 $K+1$ 个整数的序列 $a_0 = x,\ a_1,\ \cdots ,\ a_K = y$，其中对于所有 $0 \le i < K$，学生 $a_i$ 都战胜了学生 $a_{i+1}$。我们称 $K$ 为这条获胜路径的 长度。例如，如果存在一条长度为 1 的获胜路径，我们可以立即知道 $x$ 战胜了学生 $y$。如果存在一条长度为 2 的获胜路径，那么 $x$ 可能没有直接战胜 $y$，但存在某个其他选手 $z$，使得 $x$ 战胜了 $z$，并且 $z$ 战胜了 $y$。

距离 $d(x,\ y)$ 定义为从 $x$ 到 $y$ 的获胜路径的最小长度（如果存在的话）。可能存在 $x$ 无法找到一条到 $y$ 的获胜路径的情况。在这种情况下，我们定义 $d(x,\ y) = 9000$。请注意，路径长度可以为零，因此 $d(i,\ i)$ 始终为 $0$。

Ho 希望她的学生能应对各种类型的对手，因此她定义学生 $i$ 的 弱点 为 $d(i,\ 1),\ d(i,\ 2),\ \cdots,\ d(i,\ N)$ 中的最大值。当学生 $i$ 的弱点值在所有学生的弱点值中是最小的时候，该学生 $i$ 就是跆搏中的 高手。根据这个定义，可能存在多个高手。

由于 Ho 年事已高，无法判断谁是高手，你的任务是帮助 Ho 找到一个高手以及该高手的弱点值。如果存在多个高手，你可以输出其中任意一个。

输入格式

第一行给出学生人数 $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}$。

• $2 \le N \le 3\,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$)

输出格式

输出两个由空格分隔的整数 $d$ 和 $u$，其中学生 $u$ 是高手，$d$ 是学生 $u$ 的弱点值。

如果存在多个答案，你可以输出其中任意一个。

2
-W
L-

1 1

3
-LW
W-L
LW

2 1

5
-WLLW
L-LLW
WW-LL
WWW-W
LLWL

1 4

提示

翻译由 DeepSeek 完成