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 <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <algorithm>
#define meow(args...) fprintf(stderr, args)
const int N=1e5;
int n, q, fa[N], size[N];
long long m;
std::vector<std::pair<int, int>> dif;
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
template<class Type> Type read() {
	Type a;
	bool b;
	unsigned char c;
	while(c=getchar(), c-'0'>9&c!='-');
	for(a=(b=c=='-')?0:c-'0'; (c=getchar()-'0')<=9; a=a*10+c);
	return b?-a:a;
}
int find(int x) {return fa[x]==x?x:(fa[x]=find(fa[x]));}
int main() {
	int (*rd)()=read<int>;
	n=rd(), m=read<long long>()-n+1, q=rd();
	for(int i=0; i<n; ++i) fa[i]=i, size[i]=1;
	while(q--) {
		int u=rd(), v=rd(), c=rd();
		if(c) dif.emplace_back(u, v); else {
			u=find(u), v=find(v);
			if(u!=v) fa[v]=u, size[u]+=size[v];
		}
	}
	if(m==0) {
		puts(dif.empty()?"Yes":"No");
		return 0;
	}
	for(auto &e: dif) {
		e.first=find(e.first);
		e.second=find(e.second);
		if(e.first==e.second) {
			puts("No");
			return 0;
		}
	}
	int cnt=0;
	for(int i=0; i<n; ++i) cnt+=fa[i]==i;
	puts(cnt>=3&&m<=(cnt-2ll)*(cnt-1ll)/2?"Yes":"No");
	return 0;
}