7228번 - Melagiai 서브태스크다국어

문제

Bitlandijoje netrukus prasidės Seimo rinkimai, o tai reiškia, kad nacionalinėje televizijoje „Bit TV“ vyksta politiniai debatai, kuriuose dalyvauja N kandidatų, ištraukusių numerius nuo 1 iki N. Kaip ir kasmet, Bronius šiuos debatus labai įdėmiai seka. Jis pastebėjo, kad šiais metais ypač dažnai kartojosi šie du scenarijai:

• i-tasis kandidatas teigia, kad j-tasis kandidatas visada meluoja,
• i-tasis kandidatas teigia, kad j-tasis kandidatas visada sako tiesą.

Visus tokius teiginius Bronius užsirašė ir dabar nori patikrinti, ar jie vienas kitam neprieštarauja.

Sakysime, kad teiginiai neprieštarauja vienas kitam, jei egzistuoja toks kandidatų paskirstymas į melagius ir nemelagius, kad visi melagių teiginiai būtų neteisingi, o visi nemelagių teiginiai būtų teisingi.

Padėkite Broniui nustatyti, ar toks kandidatų paskirstymas egzistuoja.

입력

Pirmoje eilutėje pateikti du sveikieji teigiami skaičiai – kandidatų skaičius N ir Broniaus surinktų teiginių skaičius M.

Toliau pateikta M eilučių. i-toje eilutėje pateikti i-tą teiginį apibūdinantys trys sveikieji skaičiai a_i, b_i ir m_i:

• Jei m_i = 1, a_i-tasis kandidatas teigė, kad b_i-tasis kandidatas visada meluoja.
• Jei m_i = 0, a_i-tasis kandidatas teigė, kad b_i-tasis kandidatas visada sako tiesą.

(a_i, b_i) poros pradiniuose duomenyse yra unikalios, t. y., kandidatas a_i gali pateikti tik vieną teiginį apie kandidatą b_i arba visai jo nepateikti.

출력

Išveskite EGZISTUOJA, jei aprašytas paskirstymas į melagius ir nemelagius egzistuoja, arba NEEGZISTUOJA, jei neegzistuoja.

제한

• 1 ≤ N, M ≤ 100 000
• 1 ≤ a_i ≠ b_i ≤ N
• 0 ≤ m_i ≤ 1 (1 ≤ i ≤ M).

서브태스크

힌트