Республиканская олимпиада по информатике. 2018 год

Задача D. Разница

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

У вас есть мультимножества $S$. Разница мультимножества и множества состоит в том, что в мультимножестве одно и то же число может содержаться несколько раз, а в множестве — только один раз. Изначально, в мультимножестве содержатся все целые числа от $1$ до $n$ по одному разу. За одну операцию вы можете убрать два числа $a$ и $b$ из мультимножества и добавить их абсолютную разницу |$a$ - $b$|. Вы хотите выполнить некоторые операции так, чтобы в мультимножестве было только одно число $x$.

Формат входного файла

В первой строке входных данных задается одно целое число $T$ ($1 \le T \le 100$) — количество тестов. В следующих $T$ строках задаются по два целых числа $n$ и $x$ ($2 \le n \le 10^5, 0 \le x \le n$) — описание теста. Сумма всех $n$ по всем тестам не превышает $5 \cdot 10^5$.

Формат выходного файла

Для каждого теста выведите "NO" (без кавычек), если невозможно получить $x$. Иначе, для этого теста выведите "YES" (без кавычек) и в следующих $n$-$1$ строках выведите операции в порядке их выполнения. Для каждой операции выведите два целых числа $a$ и $b$ числа, которые выбираются с текущего мультимножества.

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

Данная задача содержит четыре подзадачи, в каждой подзадаче выполняются ограничения из условий:

1. $2 \le n \le 4$. Оценивается в $12$ баллов.
2. $n$-нечетное и $x = (n + 1) / 2$. Оценивается в $15$ баллов.
3. $0 \le x \le 1$. Оценивается в $23$ баллов.
4. $2 \le n \le 10^5$. Оценивается в $50$ баллов.

Пример:

Вход

2
5 1
5 0

Ответ

YES
2 3
4 5
1 1
1 0
NO

( Yerzhan Utkelbayev )