Funny Game
Contest: Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)
Difficulty rating: 1900
Tags: constructive algorithms, dsu, graphs, greedy, math, number theory, trees

Vanya has a graph with $$$n$$$ vertices (numbered from $$$1$$$ to $$$n$$$) and an array $$$a$$$ of $$$n$$$ integers; initially, there are no edges in the graph. Vanya got bored, and to have fun, he decided to perform $$$n - 1$$$ operations.

Operation number $$$x$$$ (operations are numbered in order starting from $$$1$$$) is as follows:

- Choose $$$2$$$ different numbers $$$1 \leq u,v \leq n$$$, such that $$$|a_u - a_v|$$$ is divisible by $$$x$$$.
- Add an undirected edge between vertices $$$u$$$ and $$$v$$$ to the graph.

Help Vanya get a connected$$$^{\text{∗}}$$$ graph using the $$$n - 1$$$ operations, or determine that it is impossible.

Input format:
Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{3}$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains the number $$$n$$$ ($$$1 \leq n \leq 2000$$$) — the number of vertices in the graph.

The second line of each test case contains $$$n$$$ numbers $$$a_1, a_2, \cdots a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output format:
For each test case, if there is no solution, then output "No" (without quotes).

Otherwise, output "Yes" (without quotes), and then output $$$n - 1$$$ lines, where in the $$$i$$$-th line, output the numbers $$$u$$$ and $$$v$$$ that need to be chosen for operation $$$i$$$.

You can output each letter in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Let's consider the second test case.

- First operation $$$(x = 1)$$$: we can connect vertices $$$4$$$ and $$$1$$$, since $$$|a_4 - a_1| = |13 - 99| = |-86| = 86$$$, and $$$86$$$ is divisible by $$$1$$$.

- Second operation $$$(x = 2)$$$: we can connect vertices $$$2$$$ and $$$1$$$, since $$$|a_2 - a_1| = |7 - 99| = |-92| = 92$$$, and $$$92$$$ is divisible by $$$2$$$.

- Third operation $$$(x = 3)$$$: we can connect vertices $$$3$$$ and $$$2$$$, since $$$|a_3 - a_2| = |1 - 7| = |-6| = 6$$$, and $$$6$$$ is divisible by $$$3$$$.

Example input:
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

Example output:
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

Editorial:
Note that we have only $$$n - 1$$$ edges, so after each operation, the number of connectivity components must decrease by $$$1$$$.
Since the order of operations is not important, we will perform the operations in reverse order. Then after the operation with number $$$x$$$, there will be $$$x + 1$$$ connectivity components in the graph. For each component, let's take any of its vertices $$$v$$$ and look at the number that corresponds to it. Note that we have chosen $$$x + 1$$$ numbers, so by the pigeonhole principle, some two numbers will be equal modulo $$$x$$$. This means that we find two vertices $$$u$$$ and $$$v$$$ from different components such that $$$|a_u - a_v|$$$ is a multiple of $$$x$$$. By drawing an edge between $$$u$$$ and $$$v$$$, we will achieve what we want — the number of connectivity components will become $$$1$$$ less.
Now it remains to go through the operations in reverse order and print the answer.