分数: 1100 点
问题陈述
有一个简单的连通无向图 G 与 N 顶点和 M 边,其中顶点被标记 1,2,\dots,N.The i第一条边连接两个顶点 u_i 和 v_i.
判断是否存在长度-N 非负整数序列 X=(X_1,X_2,\dots,X_N) 满足以下所有条件:
- X_v 不超过顶点的度数 v in G 对于每个 v=1,2,\dots,N.
- 有 no 通过向 M 的边缘 G 其中,对于每个 v=1,2,\dots,N,入度或出度 v 等于 X_v.
你有 T 测试用例;解决它们中的每一个。
约束
- 1 \leq T \leq 10^5
- 2 \leq N \leq 2 \times 10^5
- N-1 \leq M \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq N
- 所有输入值均为整数。
- 图表 输入中给出的 G 是一个简单的连通无向图。
- 总和 一个输入文件中的 N 每个输入中的所有测试用例最多 2 \times 10^5.
- 总和 一个输入文件中的 M 每个输入中的所有测试用例最多 2 \times 10^5.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
每个案例均按以下格式给出:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
输出
打印 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
如果存在一个 X 满足条件,打印 Yes;否则,打印 No.
样本输入 1
3 4 4 1 2 2 3 3 4 4 1 7 6 3 4 3 6 2 5 1 2 1 3 2 7 15 20 11 13 11 7 12 6 5 2 4 1 15 3 9 8 13 5 8 6 7 5 11 8 12 9 14 1 1 11 6 7 1 3 2 3 3 7 5 12 10 6
示例输出 1
Yes No Yes
在第一个测试用例中,例如, X=(2,2,2,1) 满足条件。
在第二个测试用例中,没有序列 X 满足条件。