Broken Switch#6360
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 computers. Unfortunately, the switch connecting all the computers began to malfunction, preventing any two computers from communicating directly. Furthermore, if computer was exchanging information with computer , no other computers could communicate with either or 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.
The first line of the input contains an integer (1 \le N \le 18). The next lines each contain characters. The -th character of the -th line is '' if computers and can exchange information, and '' otherwise. The -th character of the -th line is always '', and the matrix is symmetric.
Output the maximum number of computers that can simultaneously participate in the information exchange process.
Example 1