Поламаний свіч
Накривши стіл і ведучи приємну бесіду, наші герої розповіли містеру Нетворку про свою подорож світом. "Я бачу ви полюбляєте вирішувати цікаві задачі?" – сказав містер Нетворк – "Тоді тримайте ще одну з моєї виробничої практики".
"Якось я займався налаштуванням комп'ютерної мережі у фірмі де тоді працював. Фірма мала N комп'ютерів. Свіч, до якого були підключені усі комп’ютери, почав сильно збоїти, і тому не будь-які два комп'ютери могли зв'язатися один з одним. Крім того, якщо комп'ютер A обмінювався інформацією з комп'ютером B, то ніякі інші комп'ютери не могли у цей час обмінюватися інформацією ні з A, ні з B. Вам необхідно обчислити максимальну кількість комп'ютерів, які могли одночасно брати участь у процесі обміну інформацією" – закінчив свою розповідь містер Нетворк.
Вхідні дані
У першому рядку файлу задано ціле число N (1 ≤ N ≤ 18). Далі йдуть N рядків по N символів, причому j-ий символ i-го рядка дорівнює 'Y', якщо i-ий і j-ий комп'ютери можуть обмінюватися інформацією, інакше він дорівнює 'N'. i-ий символ i-го рядка завжди дорівнює 'N', крім того, матриця символів симетрична.
Вихідні дані
Виведіть максимальну кількість комп'ютерів, які можуть одночасно брати участь у процесі обміну інформацією.