고수

호는 태보라는 무술의 고수이다. 그녀는 태보 학원을 운영하고 있고, 학원에는 $N$명의 학생이 있다. 호는 나이가 너무 많아 태보를 가르칠 수 없어서, 학생 중 한 명에게 학원을 물려주려고 한다. 적합한 후보를 찾기 위해 호는 $\frac{N(N-1)}{2}$개의 모든 학생 쌍을 만들어 태보 대결을 시켰다. 태보 대결에서는 정확히 한 명이 이기고 다른 한 명이 진다. 호는 학생이 태보의 고수라면 학원을 물려받을 만하다고 생각한다.

고수는 게임, 스포츠, 경쟁 프로그래밍 등에서 실력이 뛰어난 사람을 뜻하는 한국어 단어이다. 태보에서는 고수의 의미가 다르다.

플레이어 $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$를 직접 이기지 않았을 수도 있지만, $x$가 이긴 어떤 다른 플레이어 $z$가 존재하고 $z$가 $y$를 이겼다.

거리 $d(x,\ y)$는 $x$에서 $y$로 가는 승리 경로가 존재할 때 그 최소 길이로 정의한다. $x$에서 $y$로 가는 승리 경로를 찾을 수 없는 경우도 있다. 그런 경우 $d(x,\ y) = 9000$으로 정의한다. 경로의 길이는 0일 수 있으므로 $d(i,\ i)$는 항상 $0$이다.

호는 자신의 학생이 모든 종류의 상대에게 강하기를 원하므로, 학생 $i$의 약점을 $d(i,\ 1),\ d(i,\ 2),\ \cdots,\ d(i,\ N)$ 중 최댓값으로 정의한다. 학생 $i$의 약점이 모든 약점 값 중 최솟값일 때 학생 $i$는 태보의 고수이다. 이 정의에 따라 고수는 여러 명일 수 있다.

호는 나이가 너무 많아 누가 고수인지 말할 수 없다. 당신의 임무는 고수 한 명과 그 고수의 약점 값을 찾아 호를 돕는 것이다. 고수가 여러 명이면 아무나 출력해도 된다.

첫째 줄에 학생 수 $N$이 주어진다.

다음 $N$개 줄의 $i$번째 줄에는 W, L, -로 이루어진 문자열 $s\_i$가 주어진다. $s\_i$의 $j$번째 문자를 $s\_{i,j}$라 하자. $s\_{i,j}$는 다음과 같다:

• $i=j$이면 $s\_{i,j}=$ -.
• 학생 $i$가 학생 $j$를 이겼으면 $s\_{i,j}=$ W.
• 학생 $j$가 학생 $i$를 이겼으면 $s\_{i,j}=$ L.

학생 $u$가 고수이고 $d$가 학생 $u$의 약점일 때, ${\color{red}d}$와 ${\color{red}u}$를 공백으로 구분해 출력한다.

답이 여러 개면 아무나 출력해도 된다.

• $2 \le N \le 3\,000$
• $s\_{i, i} =$ - ($1 \le i \le N$)
• $i \neq j$이면 $s\_{i, j}=$ W 또는 $s\_{i, j}=$ L이다. ($1 \le i \le N$)
• $s\_{i, j} =$ W이면 $s\_{j, i} =$ L이다. ($1 \le i,\ j \le N$)
• $s\_{i, j} =$ L이면 $s\_{j, i} =$ W이다. ($1 \le i,\ j \le N$)