F. Неразделимый
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два числа $$$n$$$ и $$$m$$$.

Неориентированный граф называется красивым, если выполняются следующие условия:

  • В нём нет петель и кратных рёбер.
  • В нём ровно $$$n$$$ вершин и $$$m$$$ рёбер.
  • Его вершины нельзя разделить на $$$2$$$ множества так, чтобы суммы степеней всех вершин в первом множестве и суммы степеней всех вершин во втором множестве совпадали.

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

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$n, m$$$ ($$$12 \leq n \leq 10^5, 1 \leq m \leq \min(2 \cdot 10^5, \frac{n(n-1)}{2})$$$) — количество вершин и рёбер в графе.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$ и сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите «No», если такого графа не существует. Иначе выведите «Yes», а затем, в следующих $$$m$$$ строках — рёбра красивого графа в произвольном порядке. Если ответов несколько, вы можете вывести любой из них.

Пример
Входные данные
5
12 7
12 1
90000 12
30 434
30 435
Выходные данные
Yes
1 2
2 3
3 4
4 5
5 1
1 3
2 4
No
Yes
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
No
No
Примечание

В первом наборе входных данных граф представляет собой простой цикл из $$$7$$$ вершин. Степени вершин равняются $$$\{2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0\}$$$. Несложно видеть, что в таком графе невозможно разделить вершины на $$$2$$$ части с равными суммами степеней.

Во втором наборе входных данных, так как $$$m = 1$$$, несложно видеть, что вершины всегда можно будет разделить на $$$2$$$ части с равными суммами степеней. Поэтому ответа не существует.