题目描述

すぬけ君は、$0$ から $N-1$ までの番号のついた $N$ 個の頂点と、$M$ 本の辺からなる無向グラフをお母さんにもらいました。 このグラフは連結で、また、多重辺や自己ループは存在しませんでした。

ある日、すぬけ君はこのグラフを壊してしまいました。 しかし、すぬけ君はこのグラフについて、$Q$ 個の情報を覚えています。 $i$ ($0\ \leq\ i\ \leq\ Q-1$) 番目の情報は整数 $A_i,B_i,C_i$ で表され、次のことを意味します。

• $C_i=0$ の時: 頂点 $A_i$ から $B_i$ に向かう単純パス（同じ頂点を $2$ 度通らないパス）が、$1$ つしか存在しない。
• $C_i=1$ の時: 頂点 $A_i$ から $B_i$ に向かう単純パスが $2$ つ以上存在する。

すぬけ君は自分の記憶に自信がないので、これら $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 と出力せよ。

题目大意

有一张联通图 $n$ 个点 $m$ 条边。

给定 $Q$ 条限制，每条限制形如$A_i,B_i,C_i$

若 $C_i = 0$，则 $A_i$ 到 $B_i$ 仅有一条简单路径。

否则，若 $C_i=1$，则 $A_i$ 到 $B_i$ 有多条简单路径。

判定在这 $Q$ 条限制下能否构造出合法的图。可以输出 Yes，否则输出 No

translated by Soulist

数据范围：$n,Q\le 10^5,m\le \frac{n(n-1)}{2}$

注意点的编号从 $0$ 开始，构造出来的合法的图不允许存在重边和自环，其必须联通。

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

Yes

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

No

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$
• 入力される値はすべて整数である。

Sample Explanation 1

例えば、辺集合が $(0,1),(1,2),(1,4),(2,3),(2,4)$ であるグラフを考えると、これは条件を満たします。