#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

ll n,m,q,A[maxn],B[maxn],C[maxn],f[maxn],cnt,x[maxn],c2;

inline int F(int x)
{
	if(f[x]==x) return x;
	return f[x]=F(f[x]);
}

inline void mer(int x,int y)
{
	int fx=F(x),fy=F(y);
	if(fx!=fy) f[fx]=fy;
}

int main()
{
	n=read(); m=read(); q=read(); rep(i,1,n) f[i]=i;
	rep(i,1,q)
	{
		A[i]=read()+1; B[i]=read()+1; C[i]=read();
		if(C[i]==0) mer(A[i],B[i]);
	}
	rep(i,1,n) if(f[i]==i) cnt++;
	rep(i,1,q)
	{
		if(C[i]==1)
		{
			int u=F(A[i]),v=F(B[i]);
			if(u==v) return puts("No"),0;
			else
			{
				if(!x[u]) x[u]=1,c2++;
				if(!x[v]) x[v]=1,c2++;
			}
		}
	}
	ll nw=n-cnt;
	if(cnt==1)
	{
		if(m==n-1) puts("Yes");
		else puts("No");
	}
	else if(cnt==2)
	{
		if(c2||m!=n-1) puts("No");
		else puts("Yes");
	}
	else
	{
		ll l=n,r=nw+((cnt-1)*cnt)/2; if(!c2) l--;
		if(m>=l&&m<=r) puts("Yes"); else puts("No");
	}
	return 0;
}
### Prompt

Please provide a CPP coded solution to the problem described below:

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

### Response

```cpp
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

ll n,m,q,A[maxn],B[maxn],C[maxn],f[maxn],cnt,x[maxn],c2;

inline int F(int x)
{
	if(f[x]==x) return x;
	return f[x]=F(f[x]);
}

inline void mer(int x,int y)
{
	int fx=F(x),fy=F(y);
	if(fx!=fy) f[fx]=fy;
}

int main()
{
	n=read(); m=read(); q=read(); rep(i,1,n) f[i]=i;
	rep(i,1,q)
	{
		A[i]=read()+1; B[i]=read()+1; C[i]=read();
		if(C[i]==0) mer(A[i],B[i]);
	}
	rep(i,1,n) if(f[i]==i) cnt++;
	rep(i,1,q)
	{
		if(C[i]==1)
		{
			int u=F(A[i]),v=F(B[i]);
			if(u==v) return puts("No"),0;
			else
			{
				if(!x[u]) x[u]=1,c2++;
				if(!x[v]) x[v]=1,c2++;
			}
		}
	}
	ll nw=n-cnt;
	if(cnt==1)
	{
		if(m==n-1) puts("Yes");
		else puts("No");
	}
	else if(cnt==2)
	{
		if(c2||m!=n-1) puts("No");
		else puts("Yes");
	}
	else
	{
		ll l=n,r=nw+((cnt-1)*cnt)/2; if(!c2) l--;
		if(m>=l&&m<=r) puts("Yes"); else puts("No");
	}
	return 0;
}
```