Имеется электрическая цепь дома с заданным количеством узлов, некоторые из которых связаны проводами. Любая пара узлов может быть соединена максимум одним проводом. Никакой узел не может быть подключен сам к себе. Каждый узел цепи является либо домашней электрической розеткой, либо подключен к основной внешней электросети.
Вы хотите сделать схему безопасной и избыточной, добавив столько дополнительных проводов, на сколько это возможно. Единственная сложность заключается в том, что никакие два внешних узла электросети на данный момент не соединены между собой (прямо или косвенно), и Вам следует сохранить это свойство, иначе произойдет замыкание. Найдите максимальное количество новых проводов, которое можно добавить в схему.
Состоит из нескольких тестов. Первая строка каждого теста содержит количество узлов схемы n (1 ≤ n ≤ 50), пронумерованных целыми числами от 0 до n - 1. Следующие n строк описывают имеющиеся в наличии провода: x-ый символ строки y равен 1 (единица), если вершины x и y соединены проводом, и 0 (ноль) иначе. Следующая строка содержит количество узлов, подсоединенных к основной электросети, за которой следует список самих узлов.
Для каждого теста вывести в отдельной строке максимальное количество новых проводов, которое можно добавить в электрическую схему.