| Codeforces Round 1090 (Div. 4) |
|---|
| Закончено |
Теперь, когда сезон PMOI закончился (Cloud вышел победителем), Macaque может продолжить своё путешествие к просветлению. Задачи, которые ему предстоит решать, становятся всё сложнее, бремя прошлых жизней — всё тяжелее, а вы теряете свободу воли с такой скоростью, что с трудом можете вспомнить, когда в последний раз делали что-либо по собственной воле, без принуждения со стороны Macaque. Единственный плюс для вас в том, что Macaque устроит вам бесплатную экскурсию по своему нынешнему месту обитания высоко на деревьях, как только вы решите для него следующую задачу.
Вам даны два целых числа $$$x$$$ и $$$y$$$.
Ваша задача — построить дерево из $$$x + y$$$ вершин с корнем в вершине $$$1$$$ так, чтобы:
- Ровно $$$x$$$ вершин дерева имели чётный размер поддерева$$$^{\text{∗}}$$$.
- Ровно $$$y$$$ вершин имели нечётный размер поддерева.
$$$^{\text{∗}}$$$Поддерево вершины $$$u$$$ — это множество всех вершин, путь от которых до корня проходит через $$$u$$$ (включая саму вершину $$$u$$$).
Каждый набор входных данных содержит несколько наборов входных данных. В первой строке содержится количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^4$$$). Далее следуют описания наборов входных данных.
Каждая из следующих строк содержит два целых числа $$$x$$$ и $$$y$$$ ($$$0 \leq x, y \leq 2 \cdot 10^5$$$, $$$1 \leq x + y \leq 2 \cdot 10^5$$$).
Гарантируется, что сумма $$$x+y$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.
Для каждого запроса выведите «YES» или «NO» в зависимости от того, существует ли требуемое построение. Вы можете выводить «YES» и «NO» в любом регистре (например, «yES», «yes» и «Yes» будут распознаны как положительный ответ).
Если вы выводите «YES», выведите $$$x+y-1$$$ строк, каждая из которых должна содержать два целых числа $$$u$$$ и $$$v$$$, разделённые пробелом, обозначающие, что между вершинами $$$u$$$ и $$$v$$$ есть ребро.
71 12 10 33 40 21 04 7
YES 1 2 NO YES 1 2 1 3 YES 1 2 2 3 3 4 4 5 5 6 6 7 NO NO YES 1 2 2 3 3 4 4 5 4 11 2 6 6 7 7 8 2 9 9 10
В первом наборе входных данных выведенное дерево корректно, потому что вершина $$$1$$$ имеет размер поддерева $$$2$$$, что является чётным числом, а вершина $$$2$$$ имеет размер поддерева $$$1$$$, что является нечётным числом.
Во втором наборе входных данных можно показать, что корректного дерева не существует.
В четвёртом наборе входных данных вершины с чётным размером поддерева — это $$$[2, 4, 6]$$$, а вершины с нечётным размером поддерева — это $$$[1, 3, 5, 7]$$$.
Вывод для последнего набора входных данных показан на диаграмме ниже, где синие вершины имеют чётный размер поддерева, а красные вершины имеют нечётный размер поддерева.
