Pass it to a friend#5433
LKS 2011 is set to take place in Rio de Janeiro, where everyone will be wearing white badges. Haven't you heard? This is the kind of rumor that Ostap, the LKS kid, loves to spread among his friends.
When Ostap shares a rumor with a friend, he also asks them to pass it on to all their friends. However, those friends will not continue spreading the rumor further. For instance, if Anya is friends with Vanya, and Vanya is friends with Sanya, but Anya is not friends with Sanya, then if Ostap tells a rumor to Anya, it will reach Vanya but not Sanya.
Ostap can only share one rumor with each person (otherwise, he risks being caught for making things up). What is the maximum number of rumors Ostap can spread so that each one reaches all of his friends?
The input consists of a square table of size n \times n, where n \leq 15, representing the number of Ostap's friends. In the -th row and -th column, there is a symbol Y if the -th and -th friends are friends with each other, and N if they are not.
Output the maximum number of rumors Ostap can spread among all his friends.
Example 1