The Kingdom of APIO is attacked by ninjas. Ninjas are very strong because, when they attack, they are hiding
in the shadows and other people cannot see them. The Kingdom was captured except for the APIO castle, where
the king lives. In front of the APIO castle, there is a line of
Task
Write a program that, given information of the guards and the reports from them, determines all bushes where "a ninja is certainly hiding".
Constraints
|
The number of bushes |
|
The number of hidden ninjas |
|
The number of guards |
Input Specification
Read the following data from the standard input.
- The first line of input contains three space separated integers
, , , where is the number of bushes, is the number of hidden ninjas, and is the number of guards. - The following
lines contain the information of the guards and the reports from them. The -th line of them contains three space separated integers , , ( ), describing that the guard is watching from the bush to the bush . The integer is either or . If , there is no ninja from the bush to the bush . If , there is at least one ninja from the bush to the bush .
For each input, it is guaranteed that there is at least one arrangement of ninjas which does not contradict the reports from the guards.
Output Specification
If there is a bush where "a ninja is certainly hiding", output the numbers of the bushes where "a ninja is certainly hiding" to the standard output. The numbers of bushes should be written in ascending order, and one line of output should contain only one number. Therefore, if there are -1
to the standard output.
Grading
In test cases worth
In test cases worth
Note that an additional batch worth
Sample Input 1
5 3 4
1 2 1
3 4 1
4 4 0
4 5 1
Sample Output 1
3
5
In this example, there are two possible arrangements of ninjas satisfying the conditions; three ninjas are hiding in the bush
Since a ninja is hiding in the bush
Sample Input 2
5 1 1
1 5 1
Sample Output 2
-1
In this example, there is no bush where "a ninja is certainly hiding". Therefore, we should output -1
.
Comments
Since the original data were still weak, an additional large test case was added worth 10 out of 110 marks, and all submissions were rejudged. The issue was noticed by Plasmatic.