分数: 800 点
问题陈述
给你一个简单的连通无向图,包括 N 顶点和 M 边缘。 顶点已编号 1 to N,并且边缘已编号 1 to M.
边缘 i 连接顶点 a_i 和 b_i 双向。
确定是否可以使用每个边缘恰好一次形成三个电路(参见注释)。
注释
电路是一个循环,允许重复顶点但不允许重复边缘。
约束
- 输入中的所有值都是整数。
- 1 \leq N,M \leq 10^{5}
- 1 \leq a_i, b_i \leq N
- 给定的图很简单且连通。
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 : a_M b_M
输出
如果可以使用每个边缘恰好一次形成三个电路,则打印 Yes;如果不能,请打印 No.
示例输入 1
7 9 1 2 1 3 2 3 1 4 1 5 4 5 1 6 1 7 6 7
示例输出 1
Yes
- 可以使用每个边缘恰好一次来形成三个电路,如下所示:
示例输入 2
3 3 1 2 2 3 3 1
示例输出 2
No
- 需要三个电路。
示例输入 3
18 27 17 7 12 15 18 17 13 18 13 6 5 7 7 1 14 5 15 11 7 6 1 9 5 4 18 16 4 6 7 2 7 11 6 3 12 14 5 2 10 5 7 8 10 15 3 15 9 8 7 15 5 16 18 15
示例输出 3
Yes