eolymp
bolt
Try our new interface for solving problems
Məsələlər

Шахматная головоломка

Шахматная головоломка

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Что же вы так убиваетесь? Вы же так никогда не убьётесь!

Фольклор

Девочка Даша хочет решить шахматную головоломку.

На доску размера n×n необходимо поставить минимальное количество ферзей так, чтобы они били все поля доски. Головоломка осложняется тем, что на некоторые поля доски ставить ферзей запрещено. Ферзь, это шахматная фигура, которая ходит по диагонали, вертикали или горизонтали на расстояние, ограниченное лишь размерами доски. Ферзь во время своего хода не может перескакивать через другого ферзя. Ферзь бьёт поле, на котором он стоит, а также все поля, на которые он может пойти.

Помогите Даше написать программу, решающую головоломку.

Giriş verilənləri

В первой строке входного файла заданы через пробел два целых числа n и k - размер доски и количество запрещенных полей (3n10, 0kn^2). В следующих k строках заданы координаты запрещенных полей. Координаты поля задаются через пробел двумя целыми числами r и c (1r, cn). Гарантируется, что все запрещённые поля попарно различны.

Çıxış verilənləri

В первой строке выходного файла выведите m - минимальное количество ферзей. В следующих m строках выведите координаты полей, на которые поставлены ферзи. Если решений несколько, выведите любое из них. Если решения не существует, выходной файл должен содержать единственное число -1.

Nümunə

Giriş verilənləri #1
3 0
Çıxış verilənləri #1
1
2 2
Müəllif А.Лопатин
Mənbə Летняя школа, Севастополь 2010