P15630 [2019 KAIST RUN Spring] Gosu

Ho is an expert in martial arts called $\textit{Taebo}$. She runs a Taebo school, and there are $N$ students in her school. Since Ho is too old to teach Taebo, she is going to hand over her school to one of her students. To find a suitable candidate, Ho made all $\frac{N(N-1)}{2}$ pairs of students do a Taebo matchup with each other, and wrote all the results. In a Taebo matchup, exactly one person wins the match, and another person loses the match. Ho thinks that a student is good enough to receive her school if the student is a $\textbf{Gosu}$ of Taebo. $\textbf{Gosu}$ is a Korean word which means a person who is very good at games, sports, competitive programming, etc. In Taebo, Gosu has a different meaning. Let's define a $\textbf{winning path}$ from player $x$ to player $y$ as a sequence of $K+1$ integers $a_0 = x,\ a_1,\ \cdots ,\ a_K = y$, where student $a_i$ has won student $a_{i+1}$ for all $0 \le i < K$. We call $K$ as the $\textbf{length}$ of this winning path. For example, if there exists a $\textit{winning path}$ of length 1, we can immediately know that $x$ has won student $y$. If there exists a winning path of length 2, then $x$ may not win $y$ directly, but there exists some other player $z$ that $x$ has won, and has won $y$. The $\textbf{distance}$ $d(x,\ y)$ is defined as a minimum length of winning path from $x$ to $y$, if such exists. There could be a case that $x$ can not find a winning path to $y$. In that case, we define $d(x,\ y) = 9000$. Note that, the path can have zero length, thus $d(i,\ i)$ is always $0$. Ho wants her student to be strong to all kind of opponents, so she defines the $\textbf{weakness}$ of student $i$, as a maximum value among $d(i,\ 1),\ d(i,\ 2),\ \cdots,\ d(i,\ N)$. A student $i$ is a $\textbf{Gosu}$ in Taebo when the weakness of student $i$ is minimum among all weakness values. By this definition, there can be multiple Gosu-s. Since Ho is too old to tell who is Gosu, your task is to find a Gosu and weakness value of Gosu to help Ho. If there exist multiple Gosu-s, you can print any of them.

In the first line, the number of students $N$ is given. In the $i$-th line of next $N$ lines, a string $s_i$ consists of $\texttt{W}$, $\texttt{L}$, and $\texttt{-}$. Let's denote $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$. --- - $2 \le N \le 3\,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$)

Print two space-separated integers, $d$ and $u$, where student $u$ is Gosu, and $d$ is weakness of student $u$. If there are multiple answers, you can print any of them.