Flower-like Pseudotree (Codeforces 1868D)
Tags: Greedy, trees

A pseudotree is a connected graph which has exactly one cycle and no self-loops. Note that a pseudotree may contain multiple-edges. It can be shown that a pseudotree with $$$n$$$ vertices always contains $$$n$$$ edges.After deleting all edges on the cycle in the pseudotree, a forest$$$^{\dagger}$$$ will be formed. It can be shown that each tree in the forest will contain exactly one vertex which is on cycle before removing the edges. If all trees in the forest have the same depth$$$^{\ddagger}$$$ when picking the vertex on cycle as root, we call the original pseudotree flower-like.Our friend sszcdjr, had a flower-like pseudotree with $$$n$$$ vertices and $$$n$$$ edges. However, he forgot all the edges in the pseudotree. Fortunately, he still remembers the degrees of vertices. Specifically, the degree of the $$$i$$$-th vertex is $$$d_i$$$.You have to help sszcdjr construct a possible flower-like pseudotree with $$$n$$$ vertices, where the degree of the $$$i$$$-th vertex is exactly $$$d_i$$$, or tell him that it is impossible.$$$^{\dagger}$$$ A forest is a graph in which all connectivity components are trees. A connected graph without cycles and self-loops is called a tree.$$$^{\ddagger}$$$ The depth of a tree with a root is the maximum distance from the root to the vertex of this tree.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1\leq t\leq 10^5$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2\leq n\leq 10^6$$$) — the number of vertices.The second line of each test case contains $$$n$$$ integers $$$d_1,d_2,\ldots,d_n$$$ ($$$1\leq d_i\leq n$$$) — the degree of each vertex.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, if there exist a possible flower-like pseudotree:  Print "Yes" (without quotes) in the first line.  Then, output $$$n$$$ lines, in each line print two integers $$$u_i$$$ and $$$v_i$$$ — the two vertices that the $$$i$$$-th edge connects. If there are multiple answers, you may output any of them.Otherwise, print "No" (without quotes) in the only line of output.You can output the first line of each test case in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Note: In the first test case, the only possible flower-like psuedotree is:  After deleting all edges on the cycle in the pseudotree, each tree has depth $$$0$$$.In the second test case, it can be proven that there's no such flower-like psuedotree.In the third test case, one of the possible flower-like psuedotrees is:  

Sample Inputs:
6
3
2 2 2
4
1 2 3 4
7
4 3 3 1 1 1 1
6
1 1 2 2 3 3
10
1 1 5 2 1 1 1 1 1 6
9
1 1 3 1 1 4 1 1 5

Sample Outputs:
Yes
1 2
2 3
3 1
No
Yes
1 2
2 3
3 1
1 4
1 5
2 6
3 7
Yes
5 6
6 5
1 3
2 4
3 5
4 6
No
Yes
3 6
6 9
9 3
1 3
2 6
4 6
5 9
7 9
8 9

Solution (Python):
def f(ds):
    n = len(ds)
    if sum(ds) != 2 * n:
        return
    if 2 not in ds:
        (hi, lo) = ([], [])
        for (i, d) in enumerate(ds):
            [lo, hi][d > 2] += [i]
        ans = list(zip(hi, hi[1:] + hi[:1]))
        for i in hi:
            for j in range(ds[i] - 2):
                ans += [(i, lo.pop())]
        return ans
    big = sum((v > 2 for v in ds))
    if big == 0:
        a = list(range(n))
        return zip(a, a[1:] + a[:1])
    if big == 1 or (big == 2 and ds.count(2) == 1):
        return
    if max(ds) == 3:
        (a, b) = (ds.count(3), ds.count(2))
        if (a + b) % 2 == 1 and (a == 2 or a + b < 6):
            return
    ans = []

    def E(i, j, ans=ans):
        ans += [(i, j)]
        ds[i] -= 1
        ds[j] -= 1
    ids = sorted(range(n), key=lambda i: ds[i], reverse=True)
    E(ids[0], ids[1])
    E(ids[1], ids[0])
    for i in range(2, n - 1, 2):
        if ds[ids[i + 1]] < 2:
            break
        E(ids[i - 2], ids[i])
        E(ids[i - 1], ids[i + 1])
    hot = ids[:i][::-1]
    for u in ids[i:]:
        while ds[hot[-1]] == 0:
            hot.pop()
        E(u, hot[-1])
        hot += [u]
    return ans
import sys
r = lambda : sys.stdin.readline()

def pr(*args):
    sys.stdout.write(' '.join(map(str, args)) + '\n')
for _ in range(int(r())):
    n = int(r())
    ans = f(list(map(int, r().split())))
    if not ans:
        pr('No')
        continue
    pr('Yes')
    for (i, j) in ans:
        pr(i + 1, j + 1)

Solution (Python):
def find_pairs(ds):
    n = len(ds)
    if sum(ds) != 2 * n:
        return None
    if 2 not in ds:
        (hi, lo) = ([], [])
        for (i, d) in enumerate(ds):
            if d > 2:
                hi += [i]
            else:
                lo += [i]
        ans = list(zip(hi, hi[1:] + hi[:1]))
        for i in hi:
            for j in range(ds[i] - 2):
                ans += [(i, lo.pop())]
        return ans
    big = sum((v > 2 for v in ds))
    if big == 0:
        a = list(range(n))
        return list(zip(a, a[1:] + a[:1]))
    if big == 1 or (big == 2 and ds.count(2) == 1):
        return None
    if max(ds) == 3:
        (a, b) = (ds.count(3), ds.count(2))
        if (a + b) % 2 == 1 and (a == 2 or a + b < 6):
            return None
    ans = []

    def add_edge(i, j):
        ans.append((i, j))
        ds[i] -= 1
        ds[j] -= 1
    ids = sorted(range(n), key=lambda i: ds[i], reverse=True)
    add_edge(ids[0], ids[1])
    add_edge(ids[1], ids[0])
    for i in range(2, n - 1, 2):
        if ds[ids[i + 1]] < 2:
            break
        add_edge(ids[i - 2], ids[i])
        add_edge(ids[i - 1], ids[i + 1])
    hot = ids[:i][::-1]
    for u in ids[i:]:
        while ds[hot[-1]] == 0:
            hot.pop()
        add_edge(u, hot[-1])
        hot += [u]
    return ans
import sys
input_func = lambda : sys.stdin.readline()
output_func = lambda *args: sys.stdout.write(' '.join(map(str, args)) + '\n')
for _ in range(int(input_func())):
    n = int(input_func())
    ans = find_pairs(list(map(int, input_func().split())))
    if not ans:
        output_func('No')
        continue
    output_func('Yes')
    for (i, j) in ans:
        output_func(i + 1, j + 1)

Solution (Python):
def find_pairs(ds):
    n = len(ds)
    if sum(ds) != 2 * n:
        return
    if 2 not in ds:
        (high_indices, low_indices) = ([], [])
        for (i, d) in enumerate(ds):
            if d > 2:
                high_indices.append(i)
            else:
                low_indices.append(i)
        pairs = list(zip(high_indices, high_indices[1:] + high_indices[:1]))
        for i in high_indices:
            for j in range(ds[i] - 2):
                pairs.append((i, low_indices.pop()))
        return pairs
    big = sum((v > 2 for v in ds))
    if big == 0:
        a = list(range(n))
        return list(zip(a, a[1:] + a[:1]))
    if big == 1 or (big == 2 and ds.count(2) == 1):
        return
    if max(ds) == 3:
        (a, b) = (ds.count(3), ds.count(2))
        if (a + b) % 2 == 1 and (a == 2 or a + b < 6):
            return
    pairs = []

    def add_pair(i, j):
        pairs.append((i, j))
        ds[i] -= 1
        ds[j] -= 1
    ids = sorted(range(n), key=lambda i: ds[i], reverse=True)
    add_pair(ids[0], ids[1])
    add_pair(ids[1], ids[0])
    for i in range(2, n - 1, 2):
        if ds[ids[i + 1]] < 2:
            break
        add_pair(ids[i - 2], ids[i])
        add_pair(ids[i - 1], ids[i + 1])
    hot = ids[:i][::-1]
    for u in ids[i:]:
        while ds[hot[-1]] == 0:
            hot.pop()
        add_pair(u, hot[-1])
        hot.append(u)
    return pairs
import sys
read_input = lambda : sys.stdin.readline()
print_result = lambda *args: sys.stdout.write(' '.join(map(str, args)) + '\n')
for _ in range(int(read_input())):
    n = int(read_input())
    pairs = find_pairs(list(map(int, read_input().split())))
    if not pairs:
        print_result('No')
        continue
    print_result('Yes')
    for (i, j) in pairs:
        print_result(i + 1, j + 1)