Special Cake
InterviewTime limit1sMemory limit1024 MB
Given N statements about a cake thief, find every student who could be the culprit if all others tell the truth and the culprit lies on every statement.
- Level
Medium4 of 10
- Topics
- Array, Implementation
- Solved
- No attempts yet
Problem
Waaah...
Someone took advantage of the darkness and ate Swi's huge cake again!
Swi, who loves cake as always, had put a huge cake bought from a nearby shop on the table and was admiring it. But the dormitory heater was so warm that Swi fell asleep, and the cake disappeared while Swi was asleep!
The person who ate the cake is either Swi or one of the students other than Swi who were in the dormitory at the time. To find the culprit, Swi questioned all students who were in the dormitory while Swi slept. Swi sorted each student's statement into one of the following two types.
- Among the students in the list , the culprit is there.
- Among the students in the list , the culprit is not there.
If one of the students is the culprit, every other student knows who it is, so every student except the culprit tells the truth, and the culprit lies to hide the fact of eating the cake. If none of the students is the culprit, then Swi ate the cake, so the truth of any statement cannot be determined.
Swi wants to narrow down the students who could be the culprit based on the statements. If assuming a student is the culprit creates no contradiction among the statements, that student is called a possible culprit. If none of the students is a possible culprit, then by elimination Swi is the culprit, so print swi.
Input
The first line contains the message that Swi's cake is missing, swi's cake is missing!.
The second line contains , the number of students who were in the dormitory other than Swi.
The next statements are given, each spanning three lines. The student who made the -th statement has number . Each statement has the following format.
- The first line contains , the number of students in the list .
- The second line contains the numbers of the students in the list , , separated by spaces with no repeats.
- The third line contains an integer that indicates the type of statement. If the statement says the culprit is in the list, . If it says the culprit is not in the list, .
Output
Print the numbers of all possible culprits based on all the statements, in increasing order, separated by spaces.
If no student is a possible culprit, Swi ate the cake this time too, so print swi.
Constraints
- The sum of the number of students in all lists does not exceed .