Tree Reconstruction with Minimal Value Modifications

You are given a sequence of n integers \(a_1,a_2,\ldots,a_n\). Your task is to construct an unrooted tree with exactly k nodes (numbered \(1,2,\ldots,k\)) whose degree sequence \(d_1,d_2,\ldots,d_k\) satisfies the tree property for undirected trees:

• If \(k=1\), then \(d_1=0\).
• If \(k\ge2\), then \(1\le d_i\le k-1\) for every \(i\) and \(\sum_{i=1}^{k}d_i=2(k-1)\).

The initial degree requirements are given by the sequence \(a\). However, the given sequence might not be a valid tree degree sequence. In order to obtain a valid sequence you are allowed to perform the following operations on the sequence:

1. Modification: Change the value at position \(i\) arbitrarily. (This operation is costly.)
2. Deletion: Delete the value at position \(i\) (free operation).
3. Swap: Swap the values at positions \(i\) and \(j\) (free operation).

You can perform these operations arbitrarily many times so that it is always possible to end up with a sequence which is the degree sequence of a tree. Your goal is to minimize the number of modification operations (type 1) used.

Once you decide on a valid tree degree sequence, you must actually construct a tree realizing that degree sequence. You may choose the order of the remaining elements arbitrarily (swaps are free) and you are also allowed to select any number \(k\) (with \(1\le k\le n\)) by deleting some positions.

Output Format:

Output a tree construction as follows:

• On the first line, print two integers \(m\) and \(k\) separated by a space, where \(m\) is the minimal number of modification operations performed, and \(k\) is the number of nodes in the constructed tree.
• On the second line, print \(k\) integers which are the 1-indexed positions (from the original sequence) that are used in order to define the nodes \(1,2,\ldots,k\) of the tree.
• Then print \(k-1\) lines, each containing two integers \(u\) and \(v\) (\(1\le u,v\le k\)) which denote an edge between nodes \(u\) and \(v\) in the tree.

Note: The operations of deletion and swap are free, so you can choose any subset of the original sequence and reorder them arbitrarily. For those elements whose value is already equal to the target degree in your final tree, no modification is needed. For other elements you must use a modification operation. The aim is to minimize the number of modifications.

---

Detailed Explanation:

Suppose you decide to use \(k\) elements from the original sequence. For \(k=1\), the only valid degree is 0; for \(k\ge2\), any valid tree degree sequence \(d_1,\ldots,d_k\) must satisfy \(d_i\in [1,k-1]\) and \(\sum d_i=2(k-1)\). Since swap and deletion are free, you can re-order the chosen elements arbitrarily. For each chosen element, if its value already equals the target degree you want for that node, you do not pay a cost; otherwise, you pay one modification cost. Hence, the task reduces to selecting a value of \(k\), picking a subset of indices and assigning degrees to nodes so that the unmodified positions (whose original value lies in the acceptable range and fits the sum condition) are maximized. Then you must actually construct a tree with the resulting degree sequence. One standard method is to use the Prufer-code reconstruction.

inputFormat

The first line contains a single integer \(n\) (the length of the sequence).
The second line contains \(n\) space-separated integers \(a_1,a_2,\ldots,a_n\).

outputFormat

Output the tree description in the following format:

• First line: two integers \(m\) and \(k\) (minimal modifications and number of nodes).
• Second line: \(k\) integers: the indices from the original sequence used as nodes (in order).
• Next \(k-1\) lines: each with two integers \(u\) and \(v\) denoting an edge between nodes \(u\) and \(v\).

sample

5
1 1 1 1 1

0 2
1 2
1 2

</p>