2단 중계

한 산악 지역에는 무선 중계기 N개가 세워져 있다. 중계기에는 1번부터 N번까지 번호가 붙어 있다.

어떤 두 중계기는 서로 전파를 직접 주고받을 수 있다. 직접 주고받는 관계는 양쪽으로 통한다. A번 중계기가 B번 중계기와 직접 주고받을 수 있다면 B번 중계기도 A번 중계기와 직접 주고받을 수 있다. 자기 자신과 직접 주고받는 관계는 없는 것으로 본다.

전파는 중계기를 거쳐 멀리까지 갈 수 있다. A번 중계기에서 B번 중계기까지 전파를 보낼 때, 직접 주고받는 관계를 몇 번 타고 가는지를 전달 횟수라고 하자. A번에서 B번까지 가는 길 가운데 전달 횟수가 가장 적은 경우를 생각하고, 그 값이 2 이하라면 B번 중계기를 A번 중계기의 2단 이웃이라고 부른다. 자기 자신은 2단 이웃으로 세지 않는다.

모든 중계기에 대하여 2단 이웃의 수를 세었을 때 그 가운데 가장 큰 값을 계산하는 프로그램을 작성하여라.

예를 들어 N=5인 상황을 가정하자. 직접 주고받을 수 있는지에 대한 정보가 다음의 표와 같다고 해보자. Y는 직접 주고받을 수 있다는 뜻이고 N은 그럴 수 없다는 뜻이다.

표를 보면 직접 주고받는 관계는 1번과 2번, 1번과 3번, 3번과 4번, 4번과 5번의 네 쌍이다.

3번 중계기를 기준으로 세어 보자. 1번과 4번은 전달 횟수 1로 닿는다. 2번은 1번을 거쳐서, 5번은 4번을 거쳐서 전달 횟수 2로 닿는다. 따라서 3번 중계기의 2단 이웃은 4개다.

모든 중계기에 대하여 같은 방법으로 세어 정리하면 다음의 표와 같다.

표에서 가장 큰 값은 3번 중계기의 4다. 따라서 현재 예시에서의 정답은 4다.

2번 중계기를 기준으로도 세어 보자. 1번은 전달 횟수 1로 닿고, 3번은 1번을 거쳐 전달 횟수 2로 닿는다. 4번은 1번과 3번을 거쳐야 하므로 전달 횟수가 3이고, 5번은 전달 횟수가 4다. 둘 다 2보다 크므로 2단 이웃이 아니다. 그래서 2번 중계기의 2단 이웃은 2개다.

직접 주고받는 관계가 하나도 없는 중계기도 있을 수 있다. 그런 중계기에서는 전파를 어디로도 보낼 수 없으므로 2단 이웃이 0개다.

입출력 예시

예시 1

입력

5
NYYNN
YNNNN
YNNYN
NNYNY
NNNYN

출력

4

예시 2

입력

8
NNYNNNNN
NNNNYNNY
YNNNNYNN
NNNNYNYN
NYNYNNNN
NNYNNNNN
NNNYNNNN
NYNNNNNN

출력

4

예시 3

입력

2
NN
NN

출력

0