Network#1763
In your company's computer network, there are computers. Due to a malfunctioning switch, not all pairs of computers can communicate with each other. Additionally, if computer is exchanging information with computer , no other computers can communicate with either or during that time. Your task is to determine the maximum number of computers that can simultaneously participate in exchanging information.
The first line contains the integer (1 \leq n \leq 18). Each of the next lines contains characters. The -th character of the -th line is "Y" if computers and can exchange information, and "N" otherwise. The -th character of the -th line is always "N", and the matrix is symmetric.
Output the maximum number of computers that can simultaneously participate in exchanging information.
Example 1