配点 : 100 点
問題文
每个顶点写入正整数的无向图 G' 的分数定义如下。 对于
- G' 的所有连通分量,求写在每个连通分量所包含的顶点处的正整数的总乘积,并将总和作为分数。
由正整数组成的长度 N 序列 使用 A = (A_1, A_2, \ldots, A_N) 和一个正整数 从范围 M 。到顶部 编号为 1 减去 N 它是一个具有 N 頂点 N - 1 边的简单连通无向图 G 判断是否存在满足以下条件的对象,如果有,请告诉我如何创建边缘。
- G 的顶点 从 i (1 \leq i \leq N) 是 写入 A_i 。
- G 减去 1 通过删除此下方的边获得 N 图的分数总和为 M 以下说法正确。 您将获得
T 会给出若干测试用例,请针对每个测试用例求出答案。
制約
- 1 \leq T \leq 5
- 2 \leq N \leq 200{,}000
- 1 \leq M \leq 10^{18}
- 1 \leq A_i \leq 10^{18}
- 1 对于一个输入中包含的测试用例,N 的总和是 200{,}000 以下
- 所有输入均为整数
小課題
- (1 点) N \leq 7
- (99 点)无附加约束 打印第
入力
输入是按以下格式从标准输入给出的。
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出。
N M A_1 A_2 \ldots A_N
出力
k 第 \mathrm{case}_k 。
分数总和 M 如果不可能做少于
请输出 No 。
如果可能的话
输出 1 线 Yes ,2 行后
如何根据以下格式创建 G 的边缘:
请输出 N-1 行。
列出
s_1 t_1
s_2 t_2
\vdots
s_{N-1} t_{N-1}
s_j, t_j 是 您也可以写 G 的边缘。这是顶部 s_j 和边 t_j 的边。
如果有多个答案,则任何输出都将是正确答案。
入力例 1
3 4 60 1 2 3 4 4 24 1 2 3 4 7 1000000000000000000 1 2 3 4 5 6 7
出力例 1
Yes 1 2 1 3 1 4 No Yes 1 3 3 5 5 4 2 5 7 6 1 6
1 关于第二个测试用例及其输出示例,可以考虑以下情况。
- 如果没有删除任何边,则得分为 如果删除第 (1 \times 2 \times 3 \times 4) = 24
- 1 条边,则得分为 (2) + (1 \times 3 \times 4) = 14
- 2 条边,则得分为 (3) + (1 \times 2 \times 4) = 11
- 3 条边,则得分为 (4) + (1 \times 2 \times 3) = 10
总分是 59 。 另外,总分 60 以下将是 有 G ,但其中任何一个都是正确答案。
2 对于第一个测试用例,分数总和为 24 像下面这样的东西 G 不存在,所以No 。
这个案例是个小问题 满足 1 约束。
入力例 2
3 10 20 1 1 1 1 1 1 1 1 1 1 4 3000 20 24 1 6 10 3000000 20 2 4 1 6 20 2 4 1 6
出力例 2
Yes 3 1 4 7 5 7 10 3 2 9 8 9 3 8 6 9 7 1 No Yes 10 9 4 6 5 4 4 9 9 3 9 1 8 4 1 2 7 9
这个案例是个小问题 满足 1 不满足约束。