2117. DAGCH

【问题描述】
    厨师Hawlader和厨师Heickal是好朋友。除了烹饪以为，他们还喜爱算法。Hawlader喜欢图论而Heickal喜欢数论。

    又一次，厨师Hawlader给厨师Heickal讲授图论。“嘿，Heical，你应该更专注于对图论的学习。数论中还剩下什么呢？图论是这个世界的全部，你甚至可以将数论问题规划到图论来解决，你懂吗？”Hawlader说。而对于Heickal来说，他并不厌恶图论，根据她的理论，生活应该是数论，图论，动态规划，数据结构，ad hoc等等等等的混合。要成为一命优秀的厨师，你必须知道所有这些东西而不仅仅只有图论。

    Hecikal：“哦，你是图论的大师？那你知道DFS？”

    Hawlader：“当然，DFS，深度优先搜索，这是一个基本的图论算法。”

    Hecikal：“因此，对于任意一幅图，你可以按照DFS进入的时间给他们编号？”

    Hawlader：“太简单了。用下面的伪代码就行了”

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);

}

    Hecikal：“好的，我可以给你一个难一点的问题了。”

    Hawlader：“什么？放马过来吧！”

    Hecikal：“我会给你一个有N个节点，M条边的有向图。每个节点编号按照是上面的伪代码生成的。并且，从1号点出发，所有的节点都可达。”

    Hawlader：“好的，那问题呢？”

    Hecikal：“等等，我给你一些定义，一个节点x被称为是另一个节点y的supreme vertex，如果存在一条有向路x = v_0, v_1, ..., v_k = y，满足x < y < w，对于所有0 < i < k。也就是说，一条从x出发到y有0个或更多个中间节点的有向路，满足所有中间节点的编号都大于x和y的编号，并且x的编号小于y。如果v是另一个节点w所有的supreme vertex中编号最小的，v被称为是w的superior vertex。你将得到Q个询问。每个询问，将会给定一个节点v，你需要找出有多少节点，将v视为其superior vertex。”

    Hawlader：“噢！呃...”

    厨师Hawlader无法解决这个问题，他正在向你求助。
【输入格式】

    输入数据的第一行有一个整数T，表示数据的组数。每组测试数据的地养护，有三个整数N,M,Q。接下来的M行，每行有一对整数U_i和V_i表示一条从U_i出发，指向V_i的有向边。接下来的一行包含Q个用空格隔开的整数，P_1,P_2,...,P_q。每个整数表示一组询问。

【输出格式】

    对于每组询问，输出一行表示对应的结果。
【样例输入】

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

【样例输出】

2 0 0

3 2 0 0 1 0 1 0

【样例解释】

    样例一中，结点3有且仅有1作为其supreme vertex和superior vertex。因为有一条1到3的有向边。结点2有一个superme vertex 1（1 -> 3 -> 2）。因为结点2仅有这一个supreme vertex，所以这个结点也是其superior vertex。

    样例二中，结点4有两个supreme vertex 1 （1 -> 7 -> 8 -> 4） 和 2 （2 -> 5 -> 6 -> 4），因此结点1是结点4的superior vertex。

【数据规模和约定】

1 <= T <= 10

2 <= N <= 100000

N-1 <= M <= 200000

1 <= Q <= 100000

1 <= U_i, V_i <= N,  且U_i不等于V_i

没有重边，所有结点从1号结点可达