← 返回题目列表

Codeforces · 1868/D

D. 花状伪树

中文机器翻译题面 查看原题

伪树是一种只有一个循环并且没有自循环的连通图。请注意,伪树可能包含多条边。可以证明,具有 $$$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$$$。

在第二个测试用例中,可以证明不存在这种花状的伪树。

在第三个测试用例中,可能的花状伪树之一是: