Octopus
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] 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 ≤ n ≤ 10^5), representing the number of disks in Petryk's set.
The second line contains n integers a[i] (1 ≤ a[i] < n), indicating the number of holes in the i-th disk.
The third line contains an integer maximize, 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 num[i] (1 ≤ num[i] ≤ c) and p[i]. Here, num[i] is the octopus number to which disk i belongs, and 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.
Refer to the examples in the problem statement for clarity.
Evaluation
Sub-task | Points | Additional Restrictions | Maximization of Octopuses | Required Sub-tasks |
|---|---|---|---|---|
0 | 0 | Tests from the condition | Required | - |
1 | 9 | For all i, | Not required | - |
2 | 13 | For all i, | Required | 1 |
3 | 27 | - | Not required | 1 |
4 | 51 | - | Required | 0, 1, 2, 3 |