Вы — искатель приключений. Сейчас Вы путешествуете по злому храму. Одолев пару злых зомби, Вы прибыли в квадратную комнату, состоящую из плиток, выложенных в таблицу размера n × n. Строки пронумерованы от 1 до n сверху вниз, а столбцы пронумерованы с 1 до n слева направо. В дальнем углу комнаты находится дверь, закрытая злыми магическими силами. На двери написано следующее:
Очищение от всякого зла пробудит дверь! Так как Вы довольно опытный искатель приключений, Вы мгновенно понимаете, в чем тут дело. Вы замечаете, что каждая ячейка в таблице изначально является злой. Надо очистить все эти ячейки.
Единственный известный Вам способ очищения плиток — заклинание «Очищение». Заклинание накладывается на одну плитку, а затем все ячейки в той же строке, а также все ячейки в том же столбце (включая выбранную плитку) очищаются! Разрешается очищать клетку несколько раз.
Вы хотели бы очистить все n × n ячеек, накладывая заклинание очищения как можно меньше раз. В теории все просто, но вы только что заметили, что есть еще особо злые плитки. На них заклинание очищения нельзя накладывать, даже после того, как они были очищены. Но эти плитки все же можно очистить, если наложить заклинание очищения на ячейку в той же строке или столбце.
Пожалуйста, найдите способ очистить все ячейки минимальным количеством накладываемых заклинаний. Если такого способа нет, выведите -1.
Выходные данные
Если очистить все клетки не удастся, то выведите -1. В противном случае, если Ваше решение накладывает x заклинаний очищения, выведите x строк. Каждая строка должна состоять из двух целых чисел, обозначающих номер строки и столбца ячейки, на которую следует наложить заклинание очищения.
Примечание
Первый пример иллюстрируется следующим образом. Фиолетовым выделены неочищенные злые плитки. Красным выделена плитка, на которую наложено заклинание очищения. Желтым выделены плитки, на которые распространяется текущее заклинание (возможно, ранее они уже были очищены). Зеленым выделены ранее очищенные плитки.
Во втором примере очистить ячейку, расположенную в строке 1 и столбце 1, невозможно.
К третьему примеру:
