A large enterprise created a difficult multiple-choice e-quiz to promote a new product, promising an outstanding prize to the first contestants whose quizzes were totally correct. No-one could fill in the questionnaire twice.
When the competition ended, all contestants whose quizzes were correctly answered (henceforth called aces, to simplify) started to be collected. However, at that moment, the staff realised that they could not determine the exact UTC time of all answers. To tackle this problem, they processed the available information, creating rules of the form (a1,a2) to represent that they were absolutely certain that ace a1 had answered before ace a2. Now that winners must be announced, they still have not decided how to proceed. Nevertheless, aces have already been informed that prizes will be assigned strictly according to those rules. That is,
So, whatever the final prizes assignment will be, it will assign all prizes to distinct aces and it will not break any rule. An ace always wins if, for every possible final assignment, he wins a prize. Similarly, an ace never wins if, for every possible final assignment, he does not win any prize.
As an example, let us consider that there are two prizes, four aces, denoted by x, y, z, w, and two rules, (x,y) and (y,z). Then, the two prizes can be assigned either to aces x and y, or to aces x and w. Therefore, ace x always wins a prize, ace z never wins any prize, whereas aces y and w may or may not win a prize.
Given the number of prizes, the set of aces, and the set of rules, the goal is to find out whether an ace always wins and, if not, whether there is a chance that he wins a prize.
The first line of the input contains three integers, P, A and R, separated by a single space. P is the number of prizes, A is the number of aces, and R is the number of rules. Aces are identified by integers, ranging from 0 to A−1.
Each of the following R lines contains two integers, a1 and a2, which indicate that (a1,a2) is a rule. The two integers are separated by a single space.
The next line contains an integer T, which is the number of test cases, and each of the remaining T lines has also an integer, which represents the ace that wishes to know his chances of winning a prize.
The output consists of T lines, one for each test case.
An output line contains: Congratulations!, if the ace always wins; Sorry, if the ace never wins; or You have chances, otherwise.
3 7 6 0 2 3 6 4 2 4 5 3 4 6 5 5 3 4 2 0 1
Congratulations! You have chances Sorry You have chances You have chances
2 5 2 4 3 3 2 5 0 1 2 3 4
You have chances You have chances Sorry You have chances You have chances
This document was translated from LATEX by HEVEA.