Friends

Interview

Time limit2sMemory limit128 MB

Summary

Given an N x N friendship matrix (N ≤ 50), find the maximum count of people reachable within two friendship links from any single person.

Level: Easy3 of 10
Topics: Graph, Matrix, Brute force
Solved: No attempts yet

Problem

For two people A and B, A is a 2-friend of B if A and B are direct friends, or if there exists a person C who is friends with both A and B. The most famous person is the person with the greatest number of 2-friends.

Given the friendship relations, write a program that prints the number of 2-friends of the most famous person.

Friendship is bidirectional, and a person is not friends with themself.

Input

The first line contains the number of people N. N is a positive integer not greater than 50.

Each of the next N lines contains a length-N string describing friendship relations. In the i-th string, the j-th character is Y if person i and person j are friends, and the letter N otherwise.

Output

Print the number of 2-friends of the most famous person on one line.

Examples5

Example 1
Input
```
3
NYY
YNY
YYN
```
Expected output
```
2
```
Example 2
Input
```
3
NNN
NNN
NNN
```
Expected output
```
0
```
Example 3
Input
```
5
NYNNN
YNYNN
NYNYN
NNYNY
NNNYN
```
Expected output
```
4
```

Example 4

Input

10
NNNNYNNNNN
NNNNYNYYNN
NNNYYYNNNN
NNYNNNNNNN
YYYNNNNNNY
NNYNNNNNYN
NYNNNNNYNN
NYNNNNYNNN
NNNNNYNNNN
NNNNYNNNNN

Expected output

Example 5

Input

15
NNNNNNNNNNNNNNY
NNNNNNNNNNNNNNN
NNNNNNNYNNNNNNN
NNNNNNNYNNNNNNY
NNNNNNNNNNNNNNY
NNNNNNNNYNNNNNN
NNNNNNNNNNNNNNN
NNYYNNNNNNNNNNN
NNNNNYNNNNNYNNN
NNNNNNNNNNNNNNY
NNNNNNNNNNNNNNN
NNNNNNNNYNNNNNN
NNNNNNNNNNNNNNN
NNNNNNNNNNNNNNN
YNNYYNNNNYNNNNN

Expected output