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

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.

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.

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

2 5

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.

4 7 3 1 1 1 4 3 3 2 3 2 4 1 2 1 3 4 3 3 3 4 2

MISTAKE

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.

5 3 1 2 1 1 3 3 2 4 3

1 2 5

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.

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 21 September 2021, 9:59am AEST