There is a strongly-connected graph (i.e. you can reach any node from any other node) with n nodes and m edges. I will choose some of the edges to make another strongly connected graph. Your task is to guess that graph. Too difficult, right? Don’t worry, you only need to guess k edges. If all the edges exist in my graph, you win. I promise that from all possible graphs, the answer will be chosen uniformly. The original graph will not have self-loops or duplicated edges. You already have a guess, but you are a bit unsure. Why not write a program to calculate the probabilityyouwin? Forexample,ifn=4,m=5,theoriginalgraphhas5edges: 1→2,2→3,3→ 4, 4 → 1, 1 → 3, there are only two possible answers: Ifk=2,thebestwayistoguessedge1→2and2→3(or1→2and3→4etc.) whichwill guarantee a win. But if you would like to risk by guessing edges 1 → 3 and 2 → 3, the probability you win is 0.5. Input There will be at most 10 test cases. Each case begins with two integers n, m (3 ≤ n ≤ 15, 2 ≤ m ≤ 50). Each of the following m lines contains two different integers u, v (1 ≤ u, v ≤ n), that means u → v is in the original graph. Edges are numbered 1 to m in the same order they appear in the input. The last line begins with an integer k (1 ≤ k ≤ m) and k different integers, the edges you guess. Output For each test case, print the case number and the probability you win. Absolute error of 10−4 is allowed. Sample Input 45 12 23 34 41 13 212 45 12 23 34
2/2 41 13 252 Sample Output Case 1: 1.0000 Case 2: 0.5000