Шахова головоломка#1163
Чому ти така засмучена? Так ти ніколи не досягнеш успіху!
Фольклор
Дівчинка Даша намагається розв'язати шахову задачу.
Завдання полягає в тому, щоб розташувати мінімальну кількість ферзів на шахівниці розміром n \times n так, щоб кожна клітинка перебувала під ударом. Деякі клітинки заборонено використовувати для розміщення ферзів. Ферзь ходить будь-яку відстань по діагоналі, вертикалі або горизонталі до краю дошки, але не може перестрибувати через іншого ферзя. Ферзь атакує клітинку, на якій стоїть, і всі клітинки, до яких він може дістатися.
Допоможи Даші, написавши програму для розв'язання цієї задачі.
Перший рядок містить два цілих числа і через пробіл — розмір дошки та кількість заборонених клітинок (3 \le n \le 10, 0 \le k \le n^2). Кожен із наступних рядків містить по два цілих числа і — координати забороненої клітинки (1 \le r, c \le n). Усі заборонені клітинки різні.
У першому рядку виведіть одне ціле число — мінімальну необхідну кількість ферзів. У наступних рядках вкажіть координати, в яких розміщено ферзів. Якщо існує декілька допустимих розв'язків, виведіть будь-який із них. Якщо розв'язку не існує, виведіть лише -1.
Приклад 1