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 ll long long
using namespace std;
const int N = 1e5+7;
int u[N],v[N],c[N],group[N],num[N];
int f[N];
bool vis[N];
int sf(int x){
    return f[x]==x ? x : f[x] = sf(f[x]);
}
void un(int a,int b){
    f[sf(a)] = sf(b);
}
int main()
{
    ll m;
    ll Minedge=0,Maxedge=0;
    int n,q;
    scanf("%d%lld%d",&n,&m,&q);
    for(int i=0;i<=n;i++)f[i]=i;
    for(int i=0;i<q;i++){
        scanf("%d%d%d",&u[i],&v[i],&c[i]);
        if(c[i] == 0){
            un(u[i], v[i]);
        }
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        if(!vis[sf(i)])cnt++;
        vis[sf(i)] = 1;
        group[i] = cnt;
        num[cnt]++;
    }
    bool flag = 0;
    for(int i=0;i<q;i++){
        if(c[i] == 1){
        	flag = 1;
        	if(sf(u[i]) == sf(v[i])){
        		puts("No");
        		return 0;
			}
        }
    }
    if(flag && cnt <= 2){
    	puts("No");return 0;
	}
	else{
		for(int i=1;i<=cnt;i++){
			Minedge += num[i] - 1;
		}
		Maxedge = Minedge + 1ll * cnt * (cnt-1) / 2;
		if(flag) Minedge += cnt;
		else Minedge += cnt - 1;
	}
	//Maxedge = Minedge + 1ll * cnt * (cnt-1) / 2 - cnt + (!flag ? 1 : 0);
    if(Minedge <= m && m <= Maxedge){
        puts("Yes");
    }
    else{
        puts("No");
    }
}