eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Шахова головоломка

Шахова головоломка

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

Що ж це ви так убиваєтесь? Ви ж так ніколи не вб'єтесь!

Фольклор

Дівчинка Даша хоче розв'язати шахову головоломку.

На дошку розміром n×n необхідно поставити мінімальну кількість ферзів так, щоб вони били всі поля дошки. Головоломка ускладнються тим, що на деякі поля дошки ставити ферзів заборонено. Ферзь, це шахова фігура, яка ходить по діагоналі, вертикалі чи горизонталі на відстань, обмежену лише розмірами дошки. Ферзь під час свого ходу не може перескакувати через іншого ферзя. Ферзь б'є поле, на якому він стоїть, а також всі поля, на які він може піти.

Допоможіть Даші написати програму, яка розв'язує головоломку.

Вхідні дані

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

Вихідні дані

У першому рядку вихідного файлу виведіть m - мінімальну кількість ферзів. У наступних m рядках виведіть координати полів, на які поставлено ферзі. Якщо розв'язків декілька, виведіть довільний з них. Якщо розв'язку не існує, вихідний файл повинен містити єдине число -1.

Приклад

Вхідні дані #1
3 0
Вихідні дані #1
1
2 2
Автор А.Лопатін
Джерело Літня школа, Севастополь 2010