cho.shTime limit
2s
Memory limit
128 MB
Robinson Crusoe's ship was wrecked in a storm, and after many hardships he reached an island alone. Although exhausted and desperate, he still clearly remembered a legend about that island from his childhood.
According to the legend, the island is inhabited by a good tribe and an evil tribe. Robinson must find out who belongs to each tribe in order to survive, but the two tribes cannot be distinguished by appearance.
Everyone on the island knows everyone else, so each person knows whether any other person belongs to the good tribe. Members of the evil tribe may curse and kill someone who asks a question they dislike, but asking whether a person belongs to the good tribe is safe. Members of the good tribe always tell the truth, and members of the evil tribe always lie. The numbers of people in the two tribes are written in the legend and have not changed for centuries.
Robinson asked several questions. Given the answers, determine whether every islander can be classified as belonging to the good tribe or the evil tribe.
The first line contains three integers n, p1, and p2. n is the number of questions Robinson asked, p1 is the number of people in the good tribe, and p2 is the number of people in the evil tribe.
Each of the next n lines contains two integers xi, yi, and one word ai. The islanders are numbered from 1 to p1 + p2. If ai is yes, then xi answered that yi belongs to the good tribe. If ai is no, then xi answered that yi does not belong to the good tribe.
It is possible that xi and yi are the same person. The same question may also appear more than once. n is a nonnegative integer at most 1000, and each of p1 and p2 is a nonnegative integer at most 300. The given answers are not contradictory.
If the given information is sufficient to determine every islander's tribe, print the numbers of all people in the good tribe in increasing order on the first line. If p1 = 0, print an empty line.
If the information is not sufficient and more than one classification remains possible, print NO on the first line.