Tree on a Polygon - Repovive Premier Round 7 | Repovive

20E. Tree on a Polygon

2500 pts2s256 MB

$n$ vertices lie on the circumference of a circle. They are numbered from $1$ to $n$ in clockwise order.

You want to draw $n-1$ straight line segments between pairs of vertices so that they form a tree. Two edges must not intersect at any point other than a common endpoint.

The distance between two vertices in the tree is the number of edges on the simple path between them.

You are given an array of integers $a_1,a_2,\ldots,a_n$ .

Construct a non-crossing tree such that

the distance between vertices $i$ and $i+1$ is $a_i$ for every $1 \le i < n$ ;
the distance between vertices $n$ and $1$ is $a_n$ .

If no such tree exists, report it.

If several valid trees exist, you may output any of them. The edges may be output in any order.

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le a_i \le n-1$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{c} \texttt{No} \end{array} \quad\text{or}\quad \begin{array}{l} \texttt{Yes} \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

Samples

Input

Case 1

2
1 1

Case 2

3
1 1 2

Case 3

4
1 1 1 1

Case 4

5
1 3 1 2 1

Case 5

6
1 2 2 2 2 1

Explanation

Case 1

The edge $(1,2)$ gives both required distances.

Case 2

The edges $(2,3)$ and $(1,2)$ form a path. Its consecutive distances around the circle are $1,1,2$ .

Case 3

A distance of $1$ requires each of $(1,2)$ , $(2,3)$ , $(3,4)$ , and $(4,1)$ to be an edge. A tree on four vertices cannot contain all four of them.

Case 4

The printed edges form a non-crossing tree. The distances for $(1,2)$ , $(2,3)$ , $(3,4)$ , $(4,5)$ , and $(5,1)$ are respectively $1,3,1,2,1$ .

Case 5

The printed tree is a star centered at vertex $1$ . The first and last consecutive pairs have distance $1$ , and every other consecutive pair has distance $2$ .

Output

Case 1

Yes
1 2

Case 2

Yes
2 3
1 2

Case 3

No

Case 4

Case 5

$n$ vertices lie on the circumference of a circle. They are numbered from $1$ to $n$ in clockwise order.

You want to draw $n-1$ straight line segments between pairs of vertices so that they form a tree. Two edges must not intersect at any point other than a common endpoint.

The distance between two vertices in the tree is the number of edges on the simple path between them.

You are given an array of integers $a_1,a_2,\ldots,a_n$ .

Construct a non-crossing tree such that

the distance between vertices $i$ and $i+1$ is $a_i$ for every $1 \le i < n$ ;
the distance between vertices $n$ and $1$ is $a_n$ .

If no such tree exists, report it.

If several valid trees exist, you may output any of them. The edges may be output in any order.

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le a_i \le n-1$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{c} \texttt{No} \end{array} \quad\text{or}\quad \begin{array}{l} \texttt{Yes} \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

The edge $(1,2)$ gives both required distances.

The edges $(2,3)$ and $(1,2)$ form a path. Its consecutive distances around the circle are $1,1,2$ .

A distance of $1$ requires each of $(1,2)$ , $(2,3)$ , $(3,4)$ , and $(4,1)$ to be an edge. A tree on four vertices cannot contain all four of them.

The printed edges form a non-crossing tree. The distances for $(1,2)$ , $(2,3)$ , $(3,4)$ , $(4,5)$ , and $(5,1)$ are respectively $1,3,1,2,1$ .

The printed tree is a star centered at vertex $1$ . The first and last consecutive pairs have distance $1$ , and every other consecutive pair has distance $2$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

20E. Tree on a Polygon

Constraints

Input

Output

Samples

20E. Tree on a Polygon

Constraints

Input

Output

Samples