Задача №115136. Разрезание торта
Недавно Максиму исполнилось \(k\) лет. В честь этого ему подарили торт, представляющий собой таблицу из \(n\) строк и \(m\) столбцов. На торте находятся \(k\) свечей, \(i\)-я свеча находится на пересечении \(x_i\)-й строки и \(y_i\)-го столбца (две свечи не могут стоять в одном и том же месте).
Максим хочет разрезать торт так, чтобы на каждом куске была ровно одна свеча. Для этого он может сделать несколько (возможно \(0\)) горизонтальных разрезов и несколько (возможно \(0\)) вертикальных разрезов. Каждый разрез должен проходить вдоль всего торта и должен проходить только по границам клеток таблицы.
Более формально, Максим может сколько угодно раз сделать одно из следующих действий:
- Выбрать число \(x\) такое, что \(1 \le x \le n - 1\) и провести горизонтальный разрез, если он не был до этого проведён, отделив строки с номерами \(1, \ldots, x\) от строк с номерами \(x + 1, \ldots, n\).
- Выбрать число \(y\) такое, что \(1 \le y \le m - 1\) и провести вертикальный разрез, если он не был до этого проведён, отделив столбцы с номерами \(1, \ldots, y\) от столбцов с номерами \(y + 1, \ldots, m\).
Определите, получится ли разрезать торт так, чтобы на каждой части была ровно одна свеча.
Красным цветом выделены разрезы.
Первая строка входных данных содержит три целых числа \(n\), \(m\) и \(k\) (\(1 \le n, m \le 10^9\), \(1 \le k \le 10^5\)) — размеры торта и количество свечей соответственно.
В \(i\)-й из следующих \(k\) строк записаны два целых числа \(x_i\) и \(y_i\) (\(1 \le x_i \le n\), \(1 \le y_i \le m \)) — номер строки и столбца, где находится \(i\)-я свеча, соответственно.
Выведите « No » (без кавычек), если Максим не сможет разрезать торт так, чтобы на каждой части было по одной свече.
В противном случае выведите « Yes ». Во второй строке выведите два целых числа \(a\) и \(b\) — количество горизонтальных и вертикальных разрезов, которые надо сделать Максиму, соответственно.
В третьей строке выведите \(a\) различных целых чисел — горизонтальные разрезы, которые надо сделать Максиму, в любом порядке.
В четвёртой строке выведите \(b\) различных целых чисел — вертикальные разрезы, которые надо сделать Максиму, в любом порядке.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки « yEs », « yes », « Yes » и « YES » будут приняты как положительный ответ.
В первом примере проводить разрезы не надо.
Во втором примере, на пересечении каждой строки и каждого столбца стоит свеча, поэтому надо провести все возможные разрезы.
В четвёртом примере можно провести разрезы так, как показано на рисунке из условия.
В данной задаче \(50\) тестов, помимо тестов из условия, каждый из них оценивается в \(2\) балла. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие в случае \(k \le 200\), наберут не менее \(30\) баллов.
Решения, корректно работающие в случае \(k \le 2000\), наберут не менее \(40\) баллов.
Решения, корректно работающие в случае \(\min(n, m) \le 20\), наберут не менее \(30\) баллов.
1 1 1 1 1
Yes 0 0
2 2 4 1 1 1 2 2 1 2 2
Yes 1 1 1 1
2 2 3 1 1 1 2 2 2
No
6 6 6 2 2 1 3 3 5 5 6 6 3 5 2
Yes 1 2 3 2 3
1000000000 1000000000 4 2 1 1 2 2 3 3 2
No