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:</p>

• 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.</p>

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

5 5
2 1 0
3 2 0
2 5 1
3 4 1
4 5 0

예제 출력 1

EGZISTUOJA

예제 입력 2

5 6
2 1 0
3 2 0
2 5 1
3 4 1
4 5 0
3 1 1

예제 출력 2

NEEGZISTUOJA