← 返回题目列表

AtCoder · agc038_d

D. 独特的路径

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

分数: 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