Octopus#8365

Octopus

1 second

64 megabytes

Medium

Petryk recently returned from a seaside vacation, where he was captivated by the abundance of animals, especially his favorite, the octopus. Inspired, he decided to construct octopuses using his building set at home. This set includes flexible sticks that can connect disks, with each of the $n$ disks having $a_{i}$ a_i holes for inserting sticks. A stick cannot connect a disk to itself, and any two disks can be connected by at most one stick.

In Petryk's vision, an octopus is structured as follows:

The body consists of three or more disks connected in a circular formation by sticks.
Tentacles are formed by several disks connected linearly by sticks; they can branch but not loop back.
Each tentacle is attached to a disk in the octopus body with one stick.

An octopus can have multiple tentacles or none at all, and several tentacles can be attached to a single disk in the body. The illustration shows examples of octopuses.

Task

Help Petryk construct octopuses under the following conditions:

All disks must be used.
Every hole in each disk must be filled with a stick.
The number of octopuses assembled should be maximized, but this requirement applies only to certain sub-tasks.

Input

The first line contains a single integer $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5), representing the number of disks in Petryk's set.

The second line contains $n$ integers $a_{i}$ a_i ( $1 \leq a_{i} < n$ 1 \le a_i < n), indicating the number of holes in the $i$ -th disk.

The third line contains an integer $ma x imi z e$ , which is $0$ if maximizing the number of octopuses is not necessary, and $1$ if it is.

Output

On the first line, print "Yes" if it's possible to assemble the octopuses, otherwise print "No". If the answer is positive, also print the number $c$ , representing the number of octopuses. Then, provide $n$ lines, each containing two integers $n u m_{i}$ num_i ( $1 \leq n u m_{i} \leq c$ 1 \le num_i \le c) and $p_{i}$ p_i. Here, $n u m_{i}$ num_i is the octopus number to which disk $i$ belongs, and $p_{i}$ p_i is the number of the neighboring disk closer to the octopus body. If disk $i$ is part of the body, set $p_{i} = - 1$ p_i = -1.

Refer to the examples in the problem statement for clarity.

Examples

Example 1

Example 2

Example 3

Scoring

Sub-task	Points	Additional Restrictions	Maximization of Octopuses	Required Sub-tasks
0	0	Tests from the condition	Required	-
1	9	For all $i$ , $a_{i} \in {1, 3}$ a_i \in \{1, 3\}	Not required	-
2	13	For all $i$ , $a_{i} \in {1, 3}$ a_i \in \{1, 3\}	Required	1
3	27	-	Not required	1
4	51	-	Required	0, 1, 2, 3