У Вани есть граф из $$$n$$$ вершин (пронумерованных от $$$1$$$ до $$$n$$$) и массив $$$a$$$ из $$$n$$$ целых чисел, изначально в графе нет рёбер. Ване стало скучно, и чтобы ему стало весело, он решил выполнить $$$n - 1$$$ операцию.
Операция под номером $$$x$$$ (операции нумеруются по порядку начиная с $$$1$$$) заключается в следующем:
- Выбрать $$$2$$$ различных числа $$$1 \leq u,v \leq n$$$, таких что $$$|a_u - a_v|$$$ делится на $$$x$$$.
- Добавить в граф неориентированное ребро между вершинами $$$u$$$ и $$$v$$$.
Помогите Ване с помощью $$$n - 1$$$ операции получить связный$$$^{\text{∗}}$$$ граф, или скажите, что это невозможно.
$$$^{\text{∗}}$$$Граф называется связным, если в нём можно от любой вершины дойти до любой другой, двигаясь по рёбрам.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^{3}$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных дано число $$$n$$$ ($$$1 \leq n \leq 2000$$$) — количество вершин в графе.
Во второй строке каждого набора входных данных дано $$$n$$$ чисел $$$a_1, a_2, \cdots a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.
Для каждого набора входных данных, если решения не существует, то выведите «No» (без кавычек).
Иначе выведите «Yes» (без кавычек), после этого выведите $$$n - 1$$$ строку, в $$$i$$$-й из них выведите числа $$$u$$$ и $$$v$$$, которые надо выбрать на операции $$$i$$$.
Вы можете вывести каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).
821 4499 7 1 13510 2 31 44 73587 6 81 44 32562 35 33 79 1656 51 31 69 42552 63 25 21 51233 40 3 11 31 43 37 8 50 5 12 22
YES 2 1 YES 4 1 2 1 3 2 YES 5 1 4 1 3 1 2 1 YES 4 1 3 1 2 1 5 4 YES 3 1 5 1 2 1 4 2 YES 4 1 5 1 2 1 3 2 YES 2 1 5 2 3 1 4 3 YES 9 1 12 9 11 1 10 1 6 1 7 6 2 1 8 2 5 2 3 1 4 1
Рассмотрим второй набор входных данных.
- Первая операция $$$(x = 1)$$$: можно соединить вершины $$$4$$$ и $$$1$$$, так как $$$|a_4 - a_1| = |13 - 99| = |-86| = 86$$$, а $$$86$$$ кратно $$$1$$$.
- Вторая операция $$$(x = 2)$$$: можно соединить вершины $$$2$$$ и $$$1$$$, так как $$$|a_2 - a_1| = |7 - 99| = |-92| = 92$$$, а $$$92$$$ кратно $$$2$$$.
- Третья операция $$$(x = 3)$$$: можно соединить вершины $$$3$$$ и $$$2$$$, так как $$$|a_3 - a_2| = |1 - 7| = |-6| = 6$$$, а $$$6$$$ кратно $$$3$$$.
Из картинки видно, что получился связный граф.
