14439번 - 알 수도 있는 사람

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

페이스북의 친구 관계는 대칭적이다. 즉, B가 A의 친구이면, A도 B의 친구이다. 하지만, A와 B가 친구이고, B와 C가 친구일 때, A와 C는 친구가 아닐 수도 있다.

n-친구는 페이스북 내부에서 사용하는 용어인다. 다음과 같이 정의된다.

• 두 사람이 친구이면 두 사람은 1-친구이다.
• A와 B가 n-친구이거나, A와 C가 n-친구이고, C와 B가 친구인 사람 C가 존재하는 경우에 두 사람 A와 B는 (n+1)-친구이다. (n ≥ 1)

두 사람이 얼마나 알 수 있는지 구하기 위해서 "거리 점수"를 사용한다. A와 B가 친구가 아닌 경우에 두 사람의 거리 점수란 A와 B가 3-친구가 되지 않게 하기 위해서 네트워크에서 제거해야 하는 사람(A와 B 제외)의 최수 수이다. 거리 점수가 높을수록, 두 사람은 더욱 알 수도 있는 사람이다.

페이스북 유저의 수 N과 친구 관계 정보, 두 사람 A와 B가 주어진다. 이때, A와 B의 거리 점수를 구하는 프로그램을 작성하시오. 

첫째 줄에 N, A, B가 주어진다. (2 ≤ N ≤ 40, 1 ≤ A, B ≤ N, A ≠ B)

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

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

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

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