Задача 53. Две бабочки ≡
| Автор: | Антон Карабанов | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
Условие
Две бабочки дневных в ночи немой
Вслепую бились в ожиданьи встречи,
Но был как будто ночью засекречен
Их путь друг к другу, днем такой прямой.
...
Георгий Васильев и Алексей Иващенко, "Две бабочки", 1981 г.
В теории графов граф «бабочка» (а также «галстук-бабочка» или «песочные часы») — это планарный неориентированный граф с 5 вершинами и 6 рёбрами (смотри рисунок).
Неориентированный граф задан матрицей смежности. Определите, можно ли в нём выделить хотя бы два подграфа «бабочка», не имеющих общих вершин?
Формат входных данных
Первая строка входного файла содержит натуральное число n — количество вершин. В следующих n строках без пробелов расположены по n цифр — матрица смежности графа (символ 1 соответствует наличию ребра, символ 0 — его отсутствию. Гарантируется отсутствие петель. Не гарантируется связность.
Формат выходных данных
Выведите Yes или No — ответ на вопрос задачи.
Ограничения
10 ≤ n ≤ 30
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
Смотри рисунок. Два подграфа «бабочка» выделены красным и синим цветом.
Примеры тестов
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|