D. Соединение районов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В городе есть $$$n$$$ районов, $$$i$$$-й район принадлежит $$$a_i$$$-й бандитской группировке. Изначально никакая пара районов не соединена друг с другом.

Вы — мэр города, и вам хочется построить $$$n-1$$$ двустороннюю дорогу, чтобы соединить все районы (два района могут быть соединены напрямую или через другие соединенные районы).

Если два района, принадлежащие одной и той же банде, связаны дорогой напрямую, то эта банда поднимет восстание.

Вы не хотите такого поворота, поэтому ваша задача — построить $$$n-1$$$ двустороннюю дорогу таким образом, что все районы достижимы друг из друга (быть может, с использованием промежуточных районов) и каждая пара районов, связанных напрямую, принадлежит разным бандам, или определить, что невозможно построить $$$n-1$$$ дорогу, удовлетворив все условия.

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

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

Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 5000$$$) — количество районов. Вторая строка набора тестовых данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ — номер банды, которой принадлежит $$$i$$$-й район.

Гарантируется, что сумма всех $$$n$$$ не превосходит $$$5000$$$ ($$$\sum n \le 5000$$$).

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

Для каждого набора тестовых данных выведите:

  • NO единственной строкой, если невозможно соединить все районы, удовлетворяя всем требованиям, заданным в условии задачи.
  • YES первой строкой и $$$n-1$$$ дорогу на следующей $$$n-1$$$ строке. Каждая дорога должна быть представлена как пара целых чисел $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n; x_i \ne y_i$$$), где $$$x_i$$$ и $$$y_i$$$ — два района, которые соединяет $$$i$$$-я дорога.

Для каждой дороги $$$i$$$, условие $$$a[x_i] \ne a[y_i]$$$ должно выполняться. Кроме того, все районы должны быть достижимы друг из друга (быть может, с использованием промежуточных районов).

Пример
Входные данные
4
5
1 2 2 1 3
3
1 1 1
4
1 1000 101 1000
4
1 2 3 4
Выходные данные
YES
1 3
3 5
5 4
1 2
NO
YES
1 2
2 3
3 4
YES
1 2
1 3
1 4