Gosu

Ho is an expert in a martial art called Taebo. She runs a Taebo school, and there are $N$ students in her school. Ho is too old to teach Taebo, so 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. In a Taebo matchup, exactly one person wins the match and the other person loses the match. Ho thinks a student is good enough to receive her school if the student is a Gosu of Taebo.

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 a winning path from player $x$ to player $y$ be a sequence of $K+1$ integers $a\_0 = x,\ a\_1,\ \cdots ,\ a\_K = y$, where student $a\_i$ has won against student $a\_{i+1}$ for all $0 \le i < K$. We call $K$ the length of this winning path. For example, if there exists a winning path of length 1, we can immediately know that $x$ has won against student $y$. If there exists a winning path of length 2, then $x$ may not have won against $y$ directly, but there exists some other player $z$ that $x$ has won against, and $z$ has won against $y$.

The distance $d(x,\ y)$ is defined as a minimum length of a winning path from $x$ to $y$, if such exists. There could be a case that $x$ cannot 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 kinds of opponents, so she defines the weakness of student $i$ as a maximum value among $d(i,\ 1),\ d(i,\ 2),\ \cdots,\ d(i,\ N)$. A student $i$ is a 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 the next $N$ lines, a string $s\_i$ consists of W, L, and -. Let's denote the $j$-th character of $s\_i$ as $s\_{i,j}$. $s\_{i,j}$ is given as follows:

• $s\_{i,j}=$ -, if $i=j$.
• $s\_{i,j}=$ W, if student $i$ won against student $j$.
• $s\_{i,j}=$ L, if student $j$ won against student $i$.

Print two space-separated integers, ${\color{red}d}$ and ${\color{red}u}$, where student $u$ is Gosu, and $d$ is the weakness of student $u$.

If there are multiple answers, you can print any of them.

• $2 \le N \le 3\,000$
• $s\_{i, i} =$ - ($1 \le i \le N$)
• If $i \neq j$, then $s\_{i, j}=$ W or $s\_{i, j}=$ L. ($1 \le i \le N$)
• If $s\_{i, j} =$ W, then $s\_{j, i} =$ L. ($1 \le i,\ j \le N$)
• If $s\_{i, j} =$ L, then $s\_{j, i} =$ W. ($1 \le i,\ j \le N$)