В городе есть \(n\) районов, \(i\)-й район принадлежит \(a_i\)-й бандитской группировке. Изначально никакая пара районов не соединена друг с другом.
Вы — мэр города, и вам хочется построить \(n-1\) двустороннюю дорогу, чтобы соединить все районы (два района могут быть соединены напрямую или через другие соединенные районы).
Если два района, принадлежащие одной и той же банде, связаны дорогой напрямую, то эта банда поднимет восстание.
Вы не хотите такого поворота, поэтому ваша задача — построить \(n-1\) двустороннюю дорогу таким образом, что все районы достижимы друг из друга (быть может, с использованием промежуточных районов) и каждая пара районов, связанных напрямую, принадлежит разным бандам, или определить, что невозможно построить \(n-1\) дорогу, удовлетворив все условия.
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите:
- 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]\) должно выполняться. Кроме того, все районы должны быть достижимы друг из друга (быть может, с использованием промежуточных районов).