3147. 星门Ⅱ

想必大家还记得上次校赛 “星门” 那道题,没错又是星门。

这次废话不多说,给定一个无向连通图,其中包含 个点 ,由 条边 连通。其中有一些边是特殊边。

例如在下面这个图中,包含 个点 ,由 条边 连通。其中 是特殊边。

image-20200702164852739

image-20200702164852739.png


现在询问,是否存在一个方案,使得由该图得到的最小生成树中,恰好包含 个特殊边。


输入

第一行输入三个整数 ,意义如题面所述。

接下来 行,每行输入三个整数 ,第 行表示编号为 的边负责连接点 和  ,而 表示是否为特殊边, 为是, 为否。

*输入保证每两个点之间至多有一条边连接。


输出

如果存在符合要求的方案输出 ,否则输出


样例

输入

6 9 2
1 2 0
1 4 1
4 6 0
3 4 0
1 3 0
3 6 1
3 5 1
5 6 0
2 5 0

输出

 Yes


说明

存在方案满足要求,如下图:

image-20200702170640152image-20200702170640152.png

当然也有很多其他方案可行。


难度等级: 0
总通过次数: 3
总提交次数: 57