A. Строительство небоскребов
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Мы собираемся построить новый город Метрополис. Город будет построен на бесконечной квадратной таблице. В итоге в городе будет $$$n$$$ небоскребов, каждый в своей клетке таблицы. В любой момент строительства все клетки, в которых еще нет небоскребов, называются пустыми.

Вам даны запланированные координаты $$$n$$$ небоскребов. Ваша задача — найти порядок, в котором их нужно строить, удовлетворив следующие условия.

  • У строителей есть только один кран, поэтому одновременно можно строить только один небоскреб.
  • Первый небоскреб можно построить в любой клетке.
  • Каждый следующий небоскреб должен иметь общую сторону или точку с одним из ранее построенных небоскребов, ведь так проще придерживаться линий сетки.
  • Во время строительства небоскреба должен существовать путь доставки материала к строительной площадке снаружи города, этот путь должен проходить только по пустым клеткам, соседние из которых соприкасаются стороной. Другими словами, должен быть путь по пустым клеткам, соседним по сторонам, соединяющий строящийся небоскреб и некоторую клетку $$$(r,c)$$$ такую, что $$$|r|>10^9$$$ и/или $$$|c|>10^9$$$.

Если решение существует, обозначим порядок, в котором небоскребы должны быть построены, как $$$s_1, \dots, s_n$$$. Есть два типа подзадач:

Тип 1: можно найти любое решение.

Тип 2: нужно найти решение, максимизирующее $$$s_n$$$. Среди всех таких решение, максимизирующее $$$s_{n-1}$$$, и так далее. Другими словами, нужно найти корректный порядок стройки, для которого последовательность $$$(s_n,s_{n-1},\dots,s_1)$$$ лексикографически максимальна.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 150,000$$$) — количество небоскребов.

Вторая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 2$$$), описывающее тип подзадачи, как объяснено выше.

Далее следуют $$$n$$$ строк. $$$i$$$-я из этих строк содержит два целых числа $$$r_i$$$ и $$$c_i$$$ ($$$|r_i|, |c_i| \le 10^9$$$), обозначающие координату клетки, где должен быть построен $$$i$$$-й небоскреб.

(Небоскребы не пронумерованы ни в каком специальном порядке. Единственная причина присвоить им номера — эти номера используются при выводе.)

Гарантируется, что никакие два небоскреба не совпадают.

Выходные данные

Если невозможно построить небоскребы согласно заданным правилам, выведите «NO».

Иначе выведите $$$n+1$$$ строку. Первая из этих строк должна содержать строку «YES». Далее для каждого $$$i$$$ $$$i$$$-я из оставшихся $$$n$$$ строк должна содержать единственное число $$$s_i$$$.

В подзадаче с $$$t = 1$$$, если существуют несколько решений, вы можете вывести любое.

Система оценки

Подзадача 1 (8 баллов): $$$t = 1$$$ и $$$n \le 10$$$

Подзадача 2 (14 баллов): $$$t = 1$$$ и $$$n \le 200$$$

Подзадача 3 (12 баллов): $$$t = 1$$$ и $$$n \le 2,000$$$

Подзадача 4 (17 баллов): $$$t = 2$$$ и $$$n \le 2,000$$$

Подзадача 5 (20 баллов): $$$t = 1$$$

Подзадача 6 (10 баллов): $$$t = 2$$$, $$$n \le 70,000$$$ и $$$|r_i|, |c_i| \le 900$$$ для всех $$$i$$$

Подзадача 7 (19 баллов): $$$t = 2$$$

Примеры
Входные данные
3
2
0 0
0 1
0 2
Выходные данные
YES
1
2
3
Входные данные
3
1
0 0
1 1
2 2
Выходные данные
YES
2
3
1
Входные данные
2
1
0 0
0 2
Выходные данные
NO
Примечание

В первом примере есть три небоскреба в одном ряду. Все из них могут быть доступны снаружи Метрополиса, существуют четыре порядка, которые сохраняют связность:

  • 1, 2, 3
  • 2, 1, 3
  • 2, 3, 1
  • 3, 2, 1

Так как $$$t = 2$$$, мы обязаны выбрать первый вариант.

Во втором примере единственная разница с первым примером — то, что небоскреб 2 имеет только общие углы с небоскребами 1 и 3. Все те же варианты порядков корректны. Так как $$$t = 1$$$, любой из этих ответов корректен.

В третьем примере Метрополис не связен, поэтому его точно нельзя построить.