题目描述

すぬけ君有一个包含 $N$ 个编号为 $0$ 到 $N-1$ 的顶点和 $M$ 条边的无向图，这个图是他的妈妈送给他的。该图是连通的，并且不存在重边或自环。

有一天，すぬけ君不小心把这个图弄坏了。但他还记得关于这个图的 $Q$ 条信息。第 $i$ 条信息（$0 \leq i \leq Q-1$）由整数 $A_i, B_i, C_i$ 表示，含义如下：

• 当 $C_i=0$ 时：从顶点 $A_i$ 到 $B_i$ 之间只存在一条简单路径（即不经过重复顶点的路径）。
• 当 $C_i=1$ 时：从顶点 $A_i$ 到 $B_i$ 之间存在两条或更多条简单路径。

すぬけ君对自己的记忆没有信心，他担心是否真的存在一个满足这 $Q$ 条信息的图。请你判断是否存在一个与这些记忆一致的图。

输入格式

输入按以下格式从标准输入读入。

$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}$

输出格式

如果存在一个与すぬけ君的记忆一致的图，输出 Yes；否则输出 No。

样例 1

输入

5 5 3
0 1 0
1 2 1
2 3 0

输出

Yes

样例 2

输入

4 4 3
0 1 0
1 2 1
2 3 0

输出

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

输出

No

说明/提示

限制条件

• $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$
• 所有输入的值均为整数。

样例说明 1

例如，考虑边集为 $(0,1),(1,2),(1,4),(2,3),(2,4)$ 的图，它满足所有条件。

由 ChatGPT 4.1 翻译