分数: 900 点
问题陈述
我们定义 密度 非空简单无向图的 为 \displaystyle\frac{(\text{number\ of\ edges})}{(\text{number\ of\ vertices})}.
给你正整数 N, D,以及一个简单的无向图 G 与 N 顶点和 DN 边缘。 的顶点 G 编号自 1 to N,以及 i第一条边连接顶点 A_i 和顶点 B_i。 判断是否 G 满足以下条件。
条件: 让 V 是顶点集 G。 对于任意非空 正确 子集 X of V,导出子图的密度 G by X is 严格小于 D.
有 T 测试用例解决。
什么是诱导子图?
对于顶点子集 图的 X 图表的 G, 诱导子图 of G by X 是带有顶点集的图 X 和包含所有边的边集 G 连接两个顶点 X。 在上述条件下,请注意,我们只考虑既不为空也不为整个集合的顶点子集。
约束
- T \geq 1
- N \geq 1
- D \geq 1
- 总和 DN 每个输入文件中的测试用例最多 5 \times 10^4.
- 1 \leq A_i < B_i \leq N \ \ (1 \leq i \leq DN)
- (A_i, B_i) \neq (A_j, B_j) \ \ (1 \leq i < j \leq DN)
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例 \mathrm{case}_i \ (1 \leq i \leq T) 的格式如下:
N D
A_1 B_1
A_2 B_2
\vdots
A_{DN} B_{DN}
输出
打印 T 行。
的 i- 第行应包含 Yes 如果给定的图 G 为 i第一个测试用例满足条件,并且 No 否则。
示例输入 1
2 3 1 1 2 1 3 2 3 4 1 1 2 1 3 2 3 3 4
示例输出 1
Yes No
- 第一个测试用例与示例输入 1 相同 问题D,并且满足条件。
- 对于第二个测试用例,由非空真子集导出的子图的边集 顶点集的 \{1, 2, 3\} 顶点集的 \{1, 2, 3, 4\} is \{(1, 2), (1, 3), (2, 3)\},其密度为 \displaystyle\frac{3}{3} = 1 = D。 因此,该图不满足条件。