Задача №113296. Черепахи в пруду
Пруд черепахи Тортиллы сильно изменился с момента последнего посещения Буратино. Теперь он представляет собой прямоугольное поле из \(w\) столбцов и \(h\) строк, в некоторых клетках которого расположены кувшинки. На этих кувшинках в солнечные дни греются многочисленные дети, внуки и правнуки Тортиллы.
На пруду находится набор из n связных кувшинок. Набор кувшинок называется связным, если от любой кувшинки можно дойти до любой другой, переходя по кувшинкам, смежным по стороне.
Черепахи очень любят ходить друг к другу в гости. Когда одна черепаха решает нанести визит другой, она строит некоторый маршрут, проходящий через смежные по стороне кувшинки и соединяющий ее кувшинку с кувшинкой своей знакомой. Однако неподвижный образ жизни черепах накладывает серьезные ограничения на возможные маршруты — перед началом движения черепаха выбирает некоторые два из четырех возможных направлений перемещения (вверх, вниз, влево, вправо) и затем может переходить с кувшинки на кувшинку только в одном из этих двух направлений.
Например, на приведенном ниже рисунке черепахе с кувшинки \(A\), желающей нанести визит черепахе с кувшинки \(B\), нужно выбрать направления вверх и влево, чтобы иметь возможность проложить маршрут. С другой стороны, черепаха с кувшинки C не имеет возможности добраться до кувшинки \(A\), так как на любом пути, соединяющем их кувшинки, потребуется перемещаться по меньшей мере в трех направлениях.
По итогам семейного совещания Тортилла приняла решение последовательно добавить к \(n\) имеющимся кувшинкам \(q\) новых.
Ваша задача — до начала добавлений и после каждого добавления определить, является ли набор кувшинок удобным для черепах. Тортилла гарантирует вам, что после каждого очередного добавления набор кувшинок остается связным.
В первой строке находятся два целых числа \(h\), \(w\) — количество строк и столбцов в клетчатом поле, которым является пруд (\(1 \le h, w \le 10^5\)).
В следующей строке находится целое число n — количество кувшинок в пруду в начальный момент (\(1 \le n \le 10^5\)).
В последующих \(n\) строках находится по два целых числа \(r_i , c_i\) — для каждой кувшинки заданы номера строки и столбца, на пересечении которых она находится (\(1 \le r_i \le h, 1 \le c_i \le w\)).
В следующей строке находится целое число \(q\) — количество кувшинок, которые собирается добавить Тортилла (\(0 \le q \le 100 000\)).
В последующих \(q\) строках в аналогичном формате заданы пары целых чисел \(nr_i\) , \(nc_i\) , обозначающие соответственно номер строки и номер столбца клетки с очередной добавленной кувшинкой (\(1 \le nr_i \le h, 1 \le nc_i \le w\)).
Гарантируется, что никакие две кувшинки во входных данных не совпадают. Гарантируется, что исходно и после каждого добавления набор кувшинок является связным.
Выведите \(q+1\) строку, каждая из которых представляет собой либо слово «YES», либо слово «NO», в зависимости от того, является ли на очередной момент времени система кувшинок удобной для черепах или нет. Первая строка должна содержать ответ для начального расположения кувшинок, каждая из последующих должна содержать ответ после очередного добавления кувшинки.
5 10 8 1 4 2 4 2 5 2 6 1 6 3 5 3 4 4 4 4 1 5 2 7 3 7 3 6
NO YES YES NO YES
3 3 5 1 1 1 2 1 3 2 3 3 3 4 2 1 3 2 3 1 2 2
YES NO NO NO YES