У Вани есть граф из \(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{∗}}\) граф, или скажите, что это невозможно.
Выходные данные
Для каждого набора входных данных, если решения не существует, то выведите «No» (без кавычек).
Иначе выведите «Yes» (без кавычек), после этого выведите \(n - 1\) строку, в \(i\)-й из них выведите числа \(u\) и \(v\), которые надо выбрать на операции \(i\).
Вы можете вывести каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).
Примечание
Рассмотрим второй набор входных данных.
- Первая операция \((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\).
Из картинки видно, что получился связный граф.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
2
1 4
4
99 7 1 13
5
10 2 31 44 73
5
87 6 81 44 32
5
62 35 33 79 16
5
6 51 31 69 42
5
52 63 25 21 5
12
33 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
|