Мы собираемся построить новый город Метрополис. Город будет построен на бесконечной квадратной таблице. В итоге в городе будет \(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)\) лексикографически максимальна.
Выходные данные
Если невозможно построить небоскребы согласно заданным правилам, выведите «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\)
Примечание
В первом примере есть три небоскреба в одном ряду. Все из них могут быть доступны снаружи Метрополиса, существуют четыре порядка, которые сохраняют связность:
- 1, 2, 3
- 2, 1, 3
- 2, 3, 1
- 3, 2, 1
Так как \(t = 2\), мы обязаны выбрать первый вариант.
Во втором примере единственная разница с первым примером — то, что небоскреб 2 имеет только общие углы с небоскребами 1 и 3. Все те же варианты порядков корректны. Так как \(t = 1\), любой из этих ответов корректен.
В третьем примере Метрополис не связен, поэтому его точно нельзя построить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
0 0
0 1
0 2
|
YES
1
2
3
|
|
2
|
3
1
0 0
1 1
2 2
|
YES
2
3
1
|
|
3
|
2
1
0 0
0 2
|
NO
|