Description

For a tree $T$ with $n$ nodes, its diameter $\operatorname{diam}(T)$ is defined as the maximum distance between any two nodes.

Given a positive integer $n$ and the degree $d_i$ of each node $i$, construct a tree $T^\prime$ that minimizes $\operatorname{diam}(T^\prime)$. It is guaranteed that at least one valid tree exists. If multiple valid answers exist, output any one of them.

Input Format

This problem contains multiple test cases within a single test point.

The first line contains a positive integer $T$, representing the number of test cases.

For each test case:

• The first line contains a positive integer $n$.
• The second line contains $n$ positive integers, where the $i$-th integer denotes the degree $d_i$ of node $i$.

Output Format

For each test case, output $n - 1$ lines. Each line contains two positive integers $u_i$ and $v_i$, representing the edges of the constructed tree.

4
2
1 1
3
1 1 2
5
1 1 2 2 2
7
1 3 2 3 1 1 1

2 1
1 3
3 2
5 4
4 2
3 1
3 5
4 2
3 2
1 2
5 4
6 4
7 3

Hint

Sample Explanation

For the last test case in the sample input, the constructed tree is shown below:

Its diameter equals the distance between nodes $5$ and $7$ or nodes $6$ and $7$, which is $4$. It can be proven that no tree satisfying the conditions has a diameter smaller than $4$.

Data Constraints

This problem uses subtask scoring.

For $100\%$ of the data:

• $2 \le n \le 2 \times 10^5$;
• $1 \le T \le 10^5$;
• $\sum n \le 2 \times 10^5$;
• $1 \le d_i < n$;
• It is guaranteed that at least one valid solution exists.

Detailed subtask allocations are as follows:

Translation by DeepSeek R1