401577: GYM100495 I Two friends

It is not so easy to meet with your friend in the forest when you are both lost. You might ask how that would happen? Well, imagine, you are going with your friend, you are quite fast and your friend is slow. As there is a big fog, you turn around and you can't find your friend.

There is quite a shock, of course. But it is interesting to know what the expected time to meet with your friend would be, if you just waited in your place or went to any neighbouring place completely at random (with the same probability). We assume that your friend would do the same.

For example, if you are at place which has 3 neighbouring places, you would wait with the probability equal to 0.25 and you go to any of the 3 places with probability equal to 0.25. Assume, that you are doing the same operation each moment of time (as well as your friend).

You meet with your friend at the i-th place, if you and your friend happen to be at the same i-th place for the first time after some number of described steps.

The place is neighbouring to the given place if they are connected by a path.

The first line contains the number of test cases T (1 ≤ T ≤ 50).

In the first line of every test case there are two integers n (1 ≤ n ≤ 15) and m (0 ≤ m ≤ n·(n - 1) / 2) - the number of places in the forest and the number of paths. Two places have at most one path between them.

In the following m lines of every test case there two numbers u_i and v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i) - the places connected by an undirected i-th path.

In the last line of every test case there are two integers a and b (1 ≤ a, b ≤ n) - the first friend's initial place and the second friend's initial place.

Note: the forest is not necessarily connected.

For each test case output one line containing “Case #tc: exp1 exp2 ... expn” where tc is the number of the test case (starting from 1) and expi shows the expected numbers of steps to meet at the i-th place.

The answer will be considered correct if the absolute or relative error does not exceed 10^- 7 compared with the judge's answer.

If it is not possible to meet at the i-th place, print "N/A" as its expectation.

2
2 0
1 2
3 2
1 2
2 3
1 3

Case #1: N/A N/A
Case #2: 17.589743589744 4.800000000000 17.589743589744