Liars

In Bitland, parliamentary elections are approaching, which means political debates are being held on the national TV channel "Bit TV", featuring $N$ candidates who have drawn the numbers $1$ through $N$. As he does every year, Bronius follows these debates very closely. He noticed that this year the following two kinds of statements were repeated especially often:

• candidate $i$ claims that candidate $j$ always lies,
• candidate $i$ claims that candidate $j$ always tells the truth.

Bronius wrote down all such statements and now wants to check whether they contradict one another.

We say the statements do not contradict one another if there exists an assignment of the candidates into liars and non-liars such that every statement made by a liar is false and every statement made by a non-liar is true.

Help Bronius determine whether such an assignment exists.

The first line contains two positive integers: the number of candidates $N$ and the number of statements $M$ collected by Bronius.

$M$ lines follow. The $i$-th line contains three integers $a_i$, $b_i$, and $m_i$ describing the $i$-th statement:

• If $m_i = 1$, candidate $a_i$ claimed that candidate $b_i$ always lies.
• If $m_i = 0$, candidate $a_i$ claimed that candidate $b_i$ always tells the truth.

The pairs $(a_i, b_i)$ in the input are unique; that is, candidate $a_i$ can make at most one statement about candidate $b_i$.

Print EGZISTUOJA if the described assignment into liars and non-liars exists, or NEEGZISTUOJA if it does not.

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