Broken Candle
After setting the table and enjoying some pleasant conversation, our heroes shared their tales of traveling the world with Mr. Network. "I see you enjoy tackling intriguing problems," remarked Mr. Network. "Here's one from my own work experience."
"Once, I was tasked with setting up a computer network at my company. We had N computers. Unfortunately, the switch connecting all the computers began to malfunction, preventing any two computers from communicating directly. Furthermore, if computer A was exchanging information with computer B, no other computers could communicate with either A or B at that time. Your challenge is to determine the maximum number of computers that can simultaneously participate in the information exchange process," concluded Mr. Network.
Input
The first line of the input contains an integer N (1 ≤ N ≤ 18). The next N lines each contain N characters. The j-th character of the i-th line is 'Y' if computers i and j can exchange information, and 'N' otherwise. The i-th character of the i-th line is always 'N', and the matrix is symmetric.
Output
Output the maximum number of computers that can simultaneously participate in the information exchange process.