Problem: Snuke's mother gave Snuke an undirected graph consisting of N vertices numbered 0 to N-1 and M edges. This graph was connected and contained no parallel edges or self-loops.

One day, Snuke broke this graph. Fortunately, he remembered Q clues about the graph. The i-th clue (0 \leq i \leq Q-1) is represented as integers A_i,B_i,C_i and means the following:

* If C_i=0: there was exactly one simple path (a path that never visits the same vertex twice) from Vertex A_i to B_i.
* If C_i=1: there were two or more simple paths from Vertex A_i to B_i.



Snuke is not sure if his memory is correct, and worried whether there is a graph that matches these Q clues. Determine if there exists a graph that matches Snuke's memory.

Constraints

* 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
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


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}


Output

If there exists a graph that matches Snuke's memory, print `Yes`; otherwise, print `No`.

Examples

Input

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


Output

Yes


Input

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


Output

No


Input

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


Output

No

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;
using lint=long long;

class union_find{
	int n;
	vector<int> p;
public:
	union_find(int n):n(n),p(n,-1){}
	int find(int u){ return p[u]<0?u:p[u]=find(p[u]); }
	void unite(int u,int v){
		u=find(u); v=find(v);
		if(u!=v){
			if(p[v]<p[u]) swap(u,v);
			p[u]+=p[v]; p[v]=u; n--;
		}
	}
	bool is_same(int u,int v){ return find(u)==find(v); }
	int size()const{ return n; }
	int size(int u){ return -p[find(u)]; }
};

int main(){
	int n,q;
	lint m; scanf("%d%lld%d",&n,&m,&q);
	vector<pair<int,int>> E1,E2;
	rep(i,q){
		int u,v,c; scanf("%d%d%d",&u,&v,&c);
		if(c==0) E1.emplace_back(u,v);
		else     E2.emplace_back(u,v);
	}

	union_find U(n);
	for(auto e:E1){
		int u,v; tie(u,v)=e;
		U.unite(u,v);
	}

	map<int,int> f;
	rep(u,n) if(f.count(U.find(u))==0) f.emplace(U.find(u),f.size());

	union_find V(U.size());
	for(auto e:E2){
		int u,v; tie(u,v)=e;
		if(U.is_same(u,v)) return puts("No"),0;
		V.unite(f[U.find(u)],f[U.find(v)]);
	}

	if(U.size()==2 && V.size()==1) return puts("No"),0;

	lint k=U.size();
	lint mn,mx=k*(k-1)/2;
	if(E2.empty()) mn=k-1; // spanning tree
	else           mn=k;   // cycle

	if((n-k)+mn<=m && m<=(n-k)+mx) puts("Yes");
	else                           puts("No");

	return 0;
}