Електричні провода
Електричні провода
Є електрична мережа будинку з певною кількістю вузлів, деякі з яких сполучені проводами. Будь-яка пара вузлів може бути з'єднана максимум одним проводом. Жодний вузол не може бути підключений сам до себе. Кожний вузол мережі є або домашньою розеткою, або підключений до основної зовнішньої електромережі.
Ви хочете зробити схему безпечною та надлишковою, додавши стільки додаткових проводів, скільки це можливо. Єдина складність полягає в тому, що жодні два зовнішніх вузла електромережі на даний момент не з'єднані між собою (прямо чи опосередковано), і Вам слід зберегти цю властивість, інакше відбудеться замикання. Знайдіть максимальну кількість нових проводів, яку можна додати до схеми.
Вхідні дані
Складається з декількох тестів. Перший рядок кожного тесту містить кількість вузлів схеми n (1 ≤ n ≤ 50), пронумерованих цілими числами від 0 до n - 1. Наступні n рядків описують присутні провода: x-ий символ рядка y дорівнює 1 (одиниця), якщо вершини x та y сполучені проводом, та 0 (ноль) інакше. Наступний рядок містить кількість вузлів, під'єднаних до основної електромережі, за якою йде список самих вузлів.
Вихідні дані
Для кожного тесту вивести в окремому рядку максимальну кількість нових проводів, яку можна додати в електричну мережу.
3 000 000 000 2 0 1 5 01000 10100 01010 00100 00000 2 2 4
1 3