Тест
В детском саду проводится тестирование. Детям показывают белые листы бумаги прямоугольной формы, разделенные на равные квадраты с помощью горизонтальных и вертикальных линий. Некоторые квадраты закрашены черной краской, а другие остаются белыми.
Фигурой на таком рисунке называется совокупность черных квадратов, для любой пары которых можно провести ломаную линию, полностью проходящую через черные квадраты и не пересекающую вершины квадратов.
Разными фигурами считаются те, которые невозможно совместить с помощью последовательных параллельных переносов, поворотов на 90° и симметрии относительно вертикальной или горизонтальной оси.
Детям предлагается определить, сколько всего фигур изображено на рисунке, и сколько из них являются различными.
Напишите программу, которая правильно ответит на поставленный вопрос.
Входные данные
Первая строка содержит число n — количество квадратов по вертикали и горизонтали на рисунке.
Следующие n строк по n символов представляют рисунок, где символ « » (пробел) обозначает белый квадрат, а любой другой символ — черный квадрат.
В 20% тестов n ≤ 30, в 40% тестов n ≤ 90, в 60% тестов n ≤ 180, в 80% тестов n ≤ 360, во всех тестах n ≤ 528.
Количество клеток в одной фигуре не превышает: 50 в 20% тестов, 500 в 36% тестов, 2000 в 52% тестов, 8000 в 68% тестов, 15000 в 84% тестов, 125000 в 100% тестов.
Выходные данные
Выведите в одной строке два натуральных числа: общее количество фигур и количество различных фигур. Известно, что оба числа не превышают 248.