伪树是一种只有一个循环并且没有自循环的连通图。请注意,伪树可能包含多条边。可以证明,具有 $$$n$$$ 个顶点的伪树始终包含 $$$n$$$ 边。
删除伪树中环上的所有边后,将形成森林$$$^{\dagger}$$$。可以证明,森林中的每棵树都将包含一个在删除边之前处于循环状态的顶点。如果森林中的所有树在选取循环上的顶点作为根时具有相同的深度$$$^{\ddagger}$$$,则我们将原始伪树称为花状树。
我们的朋友 sszcdjr 有一个像花一样的伪树,有 $$$n$$$ 个顶点和 $$$n$$$ 个边。然而,他忘记了伪树中的所有边。幸运的是,他还记得顶点的度数。具体来说,第$$$i$$$个顶点的度为$$$d_i$$$。
你必须帮助 sszcdjr 构建一个可能的具有 $$$n$$$ 个顶点的花状伪树,其中第 $$$i$$$ 个顶点的度恰好是 $$$d_i$$$,或者告诉他这是不可能的。
$$$^{\dagger}$$$ 森林是一个图,其中所有连接组件都是树。没有环和自环的连通图称为树。
$$$^{\ddagger}$$$ 有根的树的深度是从根到这棵树的顶点的最大距离。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\leq n\leq 10^6$$$) — 顶点数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$d_1,d_2,\ldots,d_n$$$ ($$$1\leq d_i\leq n$$$) — 每个顶点的度数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,如果存在可能的花状伪树:
- 在第一行打印“Yes”(不带引号)。
- 然后,输出$$$n$$$行,每行打印两个整数$$$u_i$$$和$$$v_i$$$——第$$$i$$$条边连接的两个顶点。
如果有多个答案,您可以输出其中任何一个。
否则,在输出的唯一行中打印“No”(不带引号)。
您可以以任何大小写(大写或小写)输出每个测试用例的第一行。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。
示例
输入 #1
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
输出 #1
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
注意
在第一个测试用例中,唯一可能的花状伪树是:
删除伪树中环上的所有边后,每棵树的深度为$$$0$$$。
在第二个测试用例中,可以证明不存在这种花状的伪树。
在第三个测试用例中,可能的花状伪树之一是: