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

2D-Ним

2D-Ним

В настольную игру 2D--ним играют на доске в виде сетки, в узлах которой могут находиться фишки. Ход игрока состоит в удалении любого положительного количества подряд идущих фишек в любой строке или любом столбце. Например, рассмотрим левую доску на следующей картинке: \includegraphics{https://static.e-olymp.com/content/4f/4f8e74d1641cb2d8ea07418c8c7d488136c32861.jpg} Игрок может удалить фишки (\textbf{A}), (\textbf{B}), (\textbf{A}, \textbf{B}), (\textbf{A}, \textbf{B}, \textbf{C}), или (\textbf{B},\textbf{ F}), и так далее. Но он не может удалить (\textbf{A}, \textbf{C}), (\textbf{D}, \textbf{E}), (\textbf{H}, \textbf{I}) или (\textbf{B}, \textbf{G}). С целью написания программного обеспечения для игры в 2D--ним, программист хочет иметь возможность определять, была ли некоторая позиция проанализирована раньше. Из правил игры следует, что две выше представленные позиции эквивалентны. То есть если существует выигрышная стратегия для позиции слева, то эта же стратегия должна применяться для достижения выигрыша и для позиции справа. Последовательные группы фишек могут появляться в любом месте и в любой ориентации. То есть на обеих досках могут появляться одни и те же кластера фишек (кластером называется множество рядом стоящих фишек, достижимых между собой последовательностью одноклеточных ходов по горизонтали или вертикали). Например, кластер из фишек (\textbf{A}, \textbf{B}, \textbf{C}, \textbf{F}, \textbf{G}) встречается на обеих досках, хотя он отражен (справа налево), повернут и сдвинут. Ваша задача -- определить, являются ли две заданные позиции эквивалентными в описанном выше смысле. \InputFile Первая строка содержит единственное число -- количество тестов \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{10}). Первая строка каждого теста содержит три целых числа \textbf{W}, \textbf{H} и \textbf{n} (\textbf{1} ≤ \textbf{W}, \textbf{H} ≤ \textbf{100}). Здесь \textbf{W} -- ширина, а \textbf{H} -- высота игровой доски, измеряемые в количестве узлов сетки. \textbf{n} -- количество фишек на доске. Вторая строка содержит \textit{\textbf{n}} пар целых чисел (\textbf{x_i}, \textbf{y_i}), описывающих координаты фишек на первой доске (\textbf{0} ≤ \textbf{x_i} ≤ \textbf{W}, \textbf{0} ≤ \textbf{y_i} ≤ \textbf{H}). Третья строка описывает координаты фишек на второй доске в том же формате. \OutputFile Для каждого теста вывести \textbf{YES} или \textbf{NO} в зависимости от того, являются ли две заданные позиции эквивалентными.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
2
8 5 11
0 0 1 0 2 0 5 0 7 0 1 1 2 1 5 1 3 3 5 2 4 4
0 4 0 3 0 2 1 1 1 4 1 3 3 3 5 2 6 2 7 2 7 4
8 5 11
0 0 1 0 2 0 5 0 7 0 1 1 2 1 5 1 3 3 6 1 4 4
0 4 0 3 0 2 1 1 1 4 1 3 3 3 5 2 6 2 7 2 7 4
Выходные данные #1
YES
NO
Источник Tehran 2002, First Iran Nationwide Internet Programming Contest