Graph Challenge

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef Hawlader and Chef Heickal are two good friends. Apart from cooking they also love algorithms. Chef Hawlader loves graph theory and Chef Heickal loves number theory.
Once again, Chef Hawlader is giving lecture to Chef Heickal about graph theory. "Hey Heickal, you should concentrate more on graph theory research. What remains in number theory? Graph is everything in the world, you can convert every problem to graph and solve them easily. Even your number theory problems can be converted and solved with graph theory, you know?" says Chef Hawlader. Though Chef Heickal does not hate graph, but according to his theory the life should a mixture of dynamic programming, number theory, data structure, ad hoc, graph theory, and so on. To become a good Chef you have to know all of them not just graph theory.
 "So are you master of graph? Do you know about DFS?" asks Chef Heickal.
 "Yes, of course. DFS, in full form Depth First Search, is a traversing or searching algorithm on graph. It's a basic algorithm", Chef Hawlader replied with angriness in his face.
 "Then, for a given graph, can you number each vertex using DFS in preorder?" asks Chef Heickal again.
 "Too easy! It will be done by the following pseudo code:"
int C = 1; void DFS(int u) { new_number[u] = C; C++; // initially all value of visited array is set to false visited[u] = true; // here v can be chosen in an arbitrary order for each v such that there is a edge from u to v if(visited[v] == false) DFS(v); }
 "Okey, I can give you a hard problem", says Chef Heickal with evil smile.
 "What? Come on", replies Chef Hawlader with grinning face.
 "I'll give you a directed graph with N vertices and M edges. Here each vertex of the graph is numbered by DFS in preorder. Of course, every vertex other than vertex 1 are reachable from vertex 1."
 "Okey, so what's problem?"
 "Wait, I give some definitions. A vertex x is a supreme vertex of y, if there is a directed path x = v_{0}, v_{1}, ..., v_{k} = y, where x < y < v_{i} for all 0 < i < k, that is a path from x to y with zero or more intermediate vertex v_{i} and every intermediate vertex should be greater than x and y and x should be less than y. A vertex v is a superior vertex of w, if v is the minimum numbered vertex among all the supreme vertices of w. You will be given Q queries on the graph. On each query you will be given a vertex v, you have to find out how many vertices are there in the graph, which have vertex v as superior vertex."
 "Oh!! Duh!!"
Chef Hawlader could not solve the problem, he is asking you to solve it for him.
Input
The first line of the input contains an integer T, denoting the number of test cases. Then T test cases follow.
The first line of each test contains three spaceseparated integers N, M, and Q. The i^{th} line of the next M lines contains two spaceseparated integers U_{i} and V_{i} denoting the directed edge from vertex U_{i} to vertex V_{i}. The next line will contain Q space separated integers P_{1}, P_{2}, ..., P_{Q}, denoting the queries defined above.
Output
For each test case, print a single line containing Q spaceseparated integers, denoting the answer of the Q queries according to the order of the input. If there is no superior vertex for a query, print 0. See the sample input and output for detailed format.
Constraints
 1 ≤ T ≤ 10
 2 ≤ N ≤ 100000 (10^{5})
 N − 1 ≤ M ≤ 200000 (2 × 10^{5})
 1 ≤ Q ≤ 100000 (10^{5})
 1 ≤ U_{i}, V_{i} ≤ N, U_{i} ≠ V_{i}
 If i ≠ j, then (U_{i}, V_{i}) ≠ (U_{j}, V_{j})
 1 ≤ P_{i} ≤ N
 In the given graph, the vertices 2, 3, ..., N are reachable from vertex 1
 The vertices of the graph is numbered by DFS, denoted by the pseudo code in the statement
Example
Input: 2 3 3 3 1 2 1 3 3 2 1 2 3 8 9 8 1 2 1 7 2 3 2 5 3 4 5 6 7 8 6 4 8 4 1 2 3 4 5 6 7 8 Output: 2 0 0 3 2 0 0 1 0 1 0
Explanation
Example case 1. Vertex 3 has only vertex 1 as supreme vertex as well as superior vertex because there is a direct edge from 1 to 3 and vertex 2 has a supreme vertex 1 (1 → 3 → 2). As vertex 2 has only one supreme vertex, it is the superior vertex also.
Example case 2. Vertex 4 has three supreme vertices 1 (1 → 7 → 8 → 4), 2 (2 → 5 → 6 → 4) and 3 (3 → 4). So vertex 1 is the superior vertex of 4.
Author:  shiplu 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/DAGCH 
Tags  feb14, hard, shiplu 
Date Added:  12122013 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 