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