← 返回题目列表

AtCoder · oupc2023_day1_p

P. 切割图得分

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

配点 : 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. (1 点) N \leq 7
  2. (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 不满足约束。