Se da un graf neorientat simplu cu n noduri si m muchii, impreuna cu o colorare a nodurilor cu doua culori (0 si 1). Verificati daca aceasta colorare este o bipartitie valida, adica orice muchie leaga un nod de culoare 0 cu unul de culoare 1.
- Date de intrare
- Pe prima linie se citesc n si m. Urmeaza m linii, fiecare cu doua numere reprezentand o muchie. Pe ultima linie se citesc n numere: culoarea c[1], c[2], ..., c[n] (0 sau 1).
- Date de iesire
- Se afiseaza 'DA' daca partitia este valida, altfel 'NU'.
- Restrictii
- 1 <= n <= 100000, 0 <= m <= 100000
Exemple
Exemplul 1
Intrare
4 4 1 2 2 3 3 4 4 1 0 1 0 1
Iesire
DA
Exemplul 2
Intrare
3 3 1 2 2 3 1 3 0 1 0
Iesire
NU