알 수도 있는 사람

"알 수도 있는 사람"은 현실에서는 아는 사이지만 페이스북에서는 아직 친구가 아닌 사람을 추천하는 시스템이다. 오늘은 이 기능을 개선하려고 한다.

페이스북의 친구 관계는 대칭적이다. 즉, B가 A의 친구이면 A도 B의 친구이다. 하지만 A와 B가 친구이고 B와 C가 친구라고 해서 A와 C가 친구인 것은 아니다.

n-친구는 페이스북 내부에서 쓰는 용어로, 다음과 같이 정의한다.

• 두 사람이 친구이면 두 사람은 1-친구이다.
• $n \ge 1$일 때, A와 B가 n-친구이거나, A와 n-친구이면서 B와 친구인 사람 C가 있으면 A와 B는 (n+1)-친구이다.

두 사람이 서로 알 가능성을 재기 위해 "거리 점수"를 쓴다. A와 B가 친구가 아닐 때, 두 사람의 거리 점수는 A와 B가 3-친구가 되지 않도록 네트워크에서 제거해야 하는 사람(A와 B 제외)의 최소 수이다. 거리 점수가 높을수록 두 사람은 서로 알 가능성이 크다.

페이스북 사용자 수 N, 친구 관계, 두 사람 A와 B가 주어질 때 A와 B의 거리 점수를 구하는 프로그램을 작성하시오.

첫째 줄에 N, A, B가 주어진다. ($2 \le N \le 40$, $1 \le A, B \le N$, $A \ne B$)

둘째 줄부터 N개의 줄에 친구 관계가 주어진다. i번째 줄의 j번째 문자는 i번 사람과 j번 사람의 관계를 나타내며, 'Y'이면 친구이고 'N'이면 친구가 아니다.

i번째 줄의 j번째 문자는 j번째 줄의 i번째 문자와 같고, i번째 줄의 i번째 문자는 항상 'N'이다. A번째 줄의 B번째 문자도 항상 'N'이다.

사람의 번호는 1번부터 N번까지이다.

첫째 줄에 A와 B의 거리 점수를 출력한다.