Under construction

Still being built. Things may change

People You May Know

Time limit2sMemory limit512 MB

Summary
Given a friendship graph, find the minimum number of vertices to delete so that A and B are no longer 3-friends under the given n-friend definition.
Level

Hard8 of 10

Topics
Graph, BFS, Greedy, Brute force
Solved
No attempts yet

Problem

"People You May Know" is a system that recommends people you know in real life but are not yet friends with on Facebook. Today we want to improve this feature.

Friendship on Facebook is symmetric: if B is a friend of A, then A is a friend of B. However, if A and B are friends and B and C are friends, A and C are not necessarily friends.

An n-friend is a term used inside Facebook, defined as follows.

  • If two people are friends, they are 1-friends.
  • For n≥1n \ge 1, two people A and B are (n+1)-friends if A and B are n-friends, or if there is a person C such that A and C are n-friends and C and B are friends.

To measure how likely two people are to know each other, Facebook uses a "distance score". When A and B are not friends, their distance score is the minimum number of people (other than A and B) that must be removed from the network so that A and B are not 3-friends. The higher the distance score, the more likely the two people know each other.

Given the number of Facebook users N, the friendship relation, and two people A and B, write a program that computes the distance score of A and B.

Input

The first line contains N, A, and B. (2≤N≤402 \le N \le 40, 1≤A,B≤N1 \le A, B \le N, A≠BA \ne B)

Each of the next N lines describes the friendships. The j-th character of the i-th line describes the relation between person i and person j: 'Y' means they are friends and 'N' means they are not.

The j-th character of the i-th line equals the i-th character of the j-th line, and the i-th character of the i-th line is always 'N'. The B-th character of the A-th line is also always 'N'.

People are numbered from 1 to N.

Output

Print the distance score of A and B on the first line.

Examples4

  1. Example 1

    Input
    2 1 2
NN
NN
    Expected output
    0

  2. Example 2

    Input
    4 1 4
NYNN
YNYN
NYNY
NNYN
    Expected output
    1

  3. Example 3

    Input
    7 3 4
NYNYYYN
YNYNNYY
NYNNNNY
YNNNNNN
YNNNNYN
YYNNYNY
NYYNNYN
    Expected output
    1

  4. Example 4

    Input
    9 9 1
NYYYYNNNN
YNNNNYYYN
YNNNNNNYN
YNNNNNNYN
YNNNNNNNY
NYNNNNNNY
NYNNNNNNY
NYYYNNNNY
NNNNYYYYN
    Expected output
    3