Counting

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem 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.

Sample 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

Sample Output

Case 1:
8
Case 2:
2

Hint

Source

2008湖南大学校赛