HZNUOJ

Counting

Tags:
Time Limit:  1 s      Memory Limit:   128 MB
Submission:0     AC:0     Score:100.00

Description

In a directed connected graph G, there are N nodes and M edges. Among the M edges, for arbitrary given node k (we named the N nodes 1, 2, . . . , N), if there are s edges point to it, we call the node k with a in-degree s, if there are t edges leads from it, we call the node k with a out-degree t. For the given graph G, we define the spanning tree as follows:


  1. The tree contains N nodes and N-1 edges in G;
  2. The N nodes are connected.


For the above definition of the spanning tree, if there is a node v meets that, the in-degree of node v is 0, and the in-degree of all the remaining nodes is 1, we call this kind of tree as outward tree roots with v. Now the given task is following:


In arbitrary given connected graph G with N nodes and M edges, can you tell me how many different kinds of trees there are in G meet the following condition?


  1. Maybe the tree is a outward tree roots with v, and also maybe it's only a spanning tree;
  2. The tree must contains the given h edges, you should assume the h edged belong to G;


You may assume that there is no same direction edge between any two nodes.

Input

In the first line, there is a single integer T, which indicates the test case. For each test case, the first line contains three integers N (2 <= N <= 100), M (N-1 <= M < 10000), R (0 <= R <= N), which N is the number of node, M is the number of directed edge, R is the root of the outward tree you should count, if R = 0, you task is counting the number of the spanning tree. In the next M lines, each line contains two integer numbers x and y, which is one edge that node x points to node y. After that, a integer h is given, which indicates the edges that the trees you are counting must contain, then next h lines is following, each line contains two integers x and y, indicates one edge which leads from x to y.

Output

For each test case, the first line you should output is "Case #:", where the '#' is the id of the test case, and then you should output one integer in the second line, which is the number of the outward tree roots witch R or the spanning tree (if R = 0) you have figured out, of course the tree must contains the given h edges. If the result is not less then 10007, please output the result mod 10007.

Samples

input
2 4 5 0 1 2 1 4 4 2 4 3 3 2 0 4 6 1 1 2 1 4 1 3 2 4 4 3 2 3 1 4 3
output
Case 1: 8 Case 2: 2

Source

湖南大学2008校赛