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 int long long
const int MAX = 510000;
const int MOD =  998244353;
const int  Inv2 = (MOD+1)/2;
int oya[100000];
int findoya(int p){
     
    if(oya[p]<0){
        return p;
    }else{
        int t=oya[p];
       
        return  oya[p]=findoya(t);
    }
}
     vector<pair<int,int>> p[2];
     signed main(){
   int n,m,q;
   cin>>n>>m>>q;
   ;fill(oya,oya+n,-1);
   
        int a,b,c;
        for(int i=0;i<q;i++){
                cin>>a>>b>>c;
                p[c].push_back(make_pair(a,b));
        }
        for(int i=0;i<p[0].size();i++){
                a=findoya(p[0][i].first);
                b=findoya(p[0][i].second);
                // cerr<<'u';
                if(a==b)continue;
                if(oya[a]<oya[b])swap(a,b);
                oya[b]+=oya[a];
                oya[a]=b;
           

        }
     int l=1;
        for(int i=0;i<p[1].size();i++){
             l=0;
                if(findoya(p[1][i].first)==findoya(p[1][i].second)){
                        cout<<"No";
                        return 0;
                }

        }
        c=0;for(int i=0;i<n;i++)if(oya[i]<0)c++;//cerr<<c<<endl;
       
       
        if(n-l<=m&&m<=n-c+c*(c-1)/2)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;

         
}