405984: GYM102202 B Gosu

Ho is an expert in martial arts called 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 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's define a 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 length of this winning path. For example, if there exists a 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 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 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 next $$$N$$$ lines, a string $$$s_i$$$ consists of W, L, and -. Let's denote $$$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 student $$$j$$$.
• $$$s_{i,j}=$$$ L, if student $$$j$$$ won student $$$i$$$.

• $$$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$$$)

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.

2
-W
L-

1 1

3
-LW
W-L
LW-

2 1

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

1 4