Problem: Detective

Want to try solving this problem? You can submit your code online if you log in or register.

Detective

Input File: detectivein.txt
Output File: detectiveout.txt
Time Limit: 1 second
Memory Limit: 1 GB

Congratulations on being the latest contestant on `Who Stole the Cookie?'. This is a game show where you, the contestant, are tasked with finding out who could have stolen a cookie from a cookie jar. Though because thieves are a dishonest bunch you may also conclude that you are being lied to.

You know that a single student committed the theft last night inside a dormitory with N children inside. Each child inside this dormitory is either a liar, or honest. A liar will always tell lies, and an honest child will always tell the truth. However, you do not know who is a liar and who is honest.

Since the theft, you have gathered M statements from the N children. These statements are all of the following form:

A says B is honest.
A says B is a liar.
A says B stole the cookie.

Given all of these statements, to win the game you must determine everyone who could have possibly stolen the cookie, or if the statements you received are inconsistent.

Input

The first line of input contains two integers, the number of children in the dormitory N and the number of statements you have gathered M.

The following M lines all contain three integers. The first integer is the number of the child making the statement (Child A). The second integer is the number of the child that the statement is being made about (Child B). The third integer indicates what type of statement is being made about child B, and these are given by the following:

The integer 1 indicates that child A claims that child B is honest.
The integer 2 indicates that child A claims that child B is a liar.
The integer 3 indicates that child A claims that child B stole the cookie.

You are guaranteed that no line of input will be repeated, and that a child will never make a claim about themselves.

Output

To win the prize, you must output the numbers of all children who could have stolen the cookie in ascending order. If there are no children who could have stolen the cookie, or there is an inconsistency in their statements then output the word MISTAKE.

Sample Input 1

Sample Output 1

2
5

Explanation 1

If child 1 always tells the truth, then child 5 stole the cookie (statement 2). Otherwise, child 1 always lies, and so does child 2 (since statement 1 is a lie). This means child 4 is telling the truth (statement 3), and so is child 3 (statement 6), so child 2 stole the cookie (statement 4). So the thief is either child 5 or child 2.

Note that the output must be 2 and then 5, since the output must be in ascending order. Outputting 5 followed by 2 would be marked incorrect.

Sample Input 2

Sample Output 2

MISTAKE

Explanation 2

Child 3 claims that child 1 always tells the truth, but the two disagree about who stole the cookie (statements 1-3); they must both be liars! Similarly, children 2 and 4 also always lie (statements 4-6).

Child 3 claims that child 4 always lies (statement 7), which is true. But child 3 never tells the truth, so there is a mistake.

Sample Input 3

Sample Output 3

1
2
5

Explanation 3

Since child 1 says child 2 always tells the truth, but they disagree about who stole the cookie they must both be lying. Since they are both lying, we can conclude that children 3 and 4 did not steal the cookie. This is the only inference that can be made, thus children 1, 2 or 5 may have stolen the cookie.

Subtasks & Constraints

For all cases 1 ≤ N ≤ 100,000 and 0 ≤ M ≤ 100,000 hold.

For Subtask 1 (15 marks), M, N ≤ 20.
For Subtask 2 (25 marks), Either only child 1 stole the cookie or the information is inconsistent.
For Subtask 3 (20 marks), M, N ≤ 1000.
For Subtask 4 (40 marks), there are no additional constraints.