거짓말쟁이들

비트랜드(Bitland)에서 곧 의회 선거가 열리며, 이에 맞춰 국영 방송 「Bit TV」에서 정치 토론이 진행됩니다. 토론에는 $1$번부터 $N$번까지 번호를 뽑은 $N$명의 후보가 참여합니다. 브로니우스(Bronius)는 매년처럼 이 토론을 아주 주의 깊게 지켜봅니다. 그는 올해 특히 다음 두 종류의 발언이 자주 반복되는 것을 발견했습니다.

• $i$번 후보가 "$j$번 후보는 항상 거짓말을 한다"라고 주장한다.
• $i$번 후보가 "$j$번 후보는 항상 진실을 말한다"라고 주장한다.

브로니우스는 이런 발언을 모두 받아 적었고, 이제 이 발언들이 서로 모순되지 않는지 확인하려 합니다.

각 후보를 '거짓말쟁이'와 '거짓말쟁이가 아닌 사람'으로 나누는 어떤 배정이 존재하여, 거짓말쟁이가 한 모든 발언은 거짓이고 거짓말쟁이가 아닌 사람이 한 모든 발언은 참이 되도록 만들 수 있다면, 그 발언들은 서로 모순되지 않는다고 합니다.

그러한 배정이 존재하는지 브로니우스가 판단할 수 있도록 도와주세요.

첫 번째 줄에 두 양의 정수, 후보의 수 $N$과 브로니우스가 모은 발언의 수 $M$이 주어집니다.

이어지는 $M$개의 줄 중 $i$번째 줄에는 $i$번째 발언을 나타내는 세 정수 $a_i$, $b_i$, $m_i$가 주어집니다.

• $m_i = 1$이면, $a_i$번 후보가 "$b_i$번 후보는 항상 거짓말을 한다"라고 주장한 것입니다.
• $m_i = 0$이면, $a_i$번 후보가 "$b_i$번 후보는 항상 진실을 말한다"라고 주장한 것입니다.

입력에서 $(a_i, b_i)$ 쌍은 서로 다릅니다. 즉, 후보 $a_i$는 후보 $b_i$에 대해 최대 한 번만 발언할 수 있습니다.

거짓말쟁이와 거짓말쟁이가 아닌 사람으로의 배정이 존재하면 EGZISTUOJA를, 존재하지 않으면 NEEGZISTUOJA를 출력하세요.

• $1 \le N, M \le 100000$
• $1 \le a_i \ne b_i \le N$
• $0 \le m_i \le 1$ ($1 \le i \le M$)