317. Camping

Problem Statement:
No, this is not the same camping we do when we play video games! Coach Fegla shares his knowledge - Yes, that is how great he is - So he decided to hold a knowledge camp for any university willing to participate. Fegla's reputation is sky high, which lead to a lot of universities with a lot of students wanting to attend the camp. The camp will be for a week or even more. It will be held at the AAST - Arab Academy for Science, Technology & Maritime Transport - which will manage providing rooms for the students to stay in during the camp. Because of the large number of students, they might have to share rooms with each other and roommates might neither know each other nor even belong to the same university. Fegla always pays attention to details no matter how small they might seem to be, and he is aware that it could affect the trainees spirit as they will not be happy with sharing their room with other trainees that they don't know.

Fegla knows some of the relations between the trainees, and he knows that if student X knows student Y that does not mean student Y necessarily knows student X. He will give you the relations between the students - as a directed relations - and will ask you to check whether student X knows student Y or not. Student X can know student Y directly or indirectly as in the case where student X knows student Z and student Z knows student Y (Student Z can know student Y directly or indirectly as well).

Input Format:
The input will start with an integer T which is the number of test cases. Each test case consists of several lines. First line contains two integers N and M representing the number of participating students and the number of relations Fegla is going to give you respectively. where (1 ≤ N ≤ 1, 000) and (1 ≤ M ≤ 100, 000). The following M lines each contains two integers X and Y meaning student X knows student Y (1 ≤ X, Y ≤ N). The following line contains an integer Q which is the number of queries Fegla is going to ask you (1 ≤ Q ≤ 1, 000, 000). Followed by Q lines each contains a query consisting of two integers A and B that Fegla wants to know if student A knows student B or not.

Output Format:
For each test case you should output "Case X:" where X is the test case number starting from 1 followed by Q line each should consist of a single string, "Yes" if student A knows student B, and "No" otherwise.
- Quotations are for clarity -

Sample Input:
1 3 3 1 2 2 1 1 3 6 1 2 2 1 1 3 3 1 2 3 3 2

Sample Output:
Case 1: Yes Yes Yes No Yes No

 Added by: hossamyosef Added at: 2014-11-11 15:32:24 UTC Time Limit: 3 seconds Partial score: No Source: ACM Jordanian Collegiate Programming Contest 2014