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>
using namespace std;
#define fr(i,low,up) for(register int i = low;i <= up; ++i)
#define nfr(i,low,up) for(register int i = low;i >= up; --i)
typedef long long ll;
const int N = 1e5+100;
int n,q;
ll m;

int fa[N];
inline int find(int x){
   return fa[x] == x ? x : fa[x] = find(fa[x]);
}

struct query{
   int u,v,c;
   bool operator < (const query &b) const {
      return c < b.c;
   }
}t[N];

int vis[N];
int bel[N];

int main(){
   scanf("%d%lld%d",&n,&m,&q);
   fr(i,1,q){
      scanf("%d%d%d",&t[i].u,&t[i].v,&t[i].c);
      ++t[i].u; ++t[i].v;
   }
   fr(i,1,n)fa[i] = i;
   sort(t+1,t+q+1);
   fr(i,1,q){
      if(t[i].c == 0){
         if(find(t[i].u) == find(t[i].v))continue ;
         fa[find(t[i].u)] = find(t[i].v);
      } else {
         if(find(t[i].u) == find(t[i].v)){
            puts("No"); return 0;
         }
         vis[find(t[i].u)] = vis[find(t[i].v)] = 1;
      }
   }
   int cnt = 0,cnt2 = 0;
   fr(i,1,n){
      if(!bel[find(i)])++cnt,bel[fa[i]] = 1;
      if(vis[i])++cnt2;
   }
   m -= n-cnt;
   if(cnt == 2 && cnt2 == 2){
      puts("No"); return 0;
   } else if(cnt2 == 2){
      cnt2 = 3;
   }
   if(m < cnt2){
      puts("No"); return 0;
   } else if(m > 1LL*cnt*(cnt-1)/2){
      puts("No"); return 0;
   }
   puts("Yes"); return 0;
}