← 返回题目列表

AtCoder · agc071_c

C. 可根据需要定向

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

分数: 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 满足条件。