ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU contest. Petrozavodsk training camp. Winter 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

H. Магический квадрат

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Вася нарисовал на листке бумаги в клетку квадрат размера n2 × n2 и разделил его на n2 малых квадратов размера n × n. Вася хочет расставить в клетках числа от 0 до n2−1, чтобы получить магический квадрат. А именно, магическим квадратом он называет такой квадрат, что:
  1. В левой верхней клетке стоит число 0.
  2. В любом столбце никакие два числа не повторяются.
  3. В любой строке никакие два числа не повторяются.
  4. В любом малом квадрате никакие два числа не повторяются.
  5. Если поменять местами два малых квадрата, имеющих общую сторону, то получится квадрат, удовлетворяющий свойствам 2-4.
Несколько чисел Вася уже расставил. Скажите, сможет ли он, не стирая этих чисел, дополнить квадрат до магического.

Исходные данные

В первой строке — целые числа 1 ≤ n ≤ 3 и 0 ≤ kn4. В каждой из следующих k строк — тройка чисел a, b, c, означающая, что Вася поставил в клетке с номером (a, b) число c. Левая верхняя клетка имеет номер (0, 0), левая нижняя (0, n2−1), правая верхняя (n2−1, 0), правая нижняя (n2−1, n2−1). 0 ≤ сn2−1. Для любых двух троек чисел (a1, b1, c1) и (a2, b2, c2) либо a1a2, либо b1b2.

Результат

Выведите NO, если Вася не сможет достроить квадрат до магического. В противном случае выведите YES.

Примеры

исходные данныерезультат
2 4
0 0 0
1 2 1
2 1 2
3 3 3
NO
2 0
YES
Автор задачи: Александр Ипатов
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, January 2006
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1466. Магический квадрат