分数: 700 点
问题陈述
Snuke 的母亲给了 Snuke 一个无向图,其中包括 N 顶点编号 0 to N-1 和 M 边缘。 该图是连通的并且不包含平行边或自环。
有一天,Snuke 打破了这张图。 幸好他还记得 Q 有关图表的线索。 的 i- 第一条线索 (0 \leq i \leq Q-1) 表示为整数 A_i,B_i,C_i 含义如下:
- If C_i=0:来自 Vertex 的只有一条简单路径(一条永远不会访问同一顶点两次的路径) A_i to B_i.
- If C_i=1:来自 Vertex 的有两条或更多简单路径 A_i to B_i.
Snuke不确定自己的记忆是否正确,并担心是否有与这些相符的图表 Q 线索。 确定是否存在与 Snuke 的记忆相匹配的图表。
约束
- 2 \leq N \leq 10^5
- N-1 \leq M \leq N \times (N-1)/2
- 1 \leq Q \leq 10^5
- 0 \leq A_i,B_i \leq N-1
- A_i \neq B_i
- 0 \leq C_i \leq 1
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M Q
A_0 B_0 C_0
A_1 B_1 C_1
\vdots
A_{Q-1} B_{Q-1} C_{Q-1}
输出
如果存在与 Snuke 内存匹配的图表,则打印 Yes;否则,打印 No.
示例输入 1
5 5 3 0 1 0 1 2 1 2 3 0
示例输出 1
Yes
例如,考虑一个有边的图 (0,1),(1,2),(1,4),(2,3),(2,4)。这张图与线索相符。
示例输入 2
4 4 3 0 1 0 1 2 1 2 3 0
示例输出 2
No
示例输入 3
10 9 9 7 6 0 4 5 1 9 7 0 2 9 0 2 3 0 4 1 0 8 0 0 9 1 0 3 0 0
示例输出 3
No