Problem D
Lost In The Woods

Your friend has gotten lost in the woods. He has called and asked for you to come get him, but you are very busy and would rather just stay home. You quickly look up a map of the woods. It appears that the woods consist of a small number of clearings, with paths connecting them. You hope that the woods are sufficiently small and simple that your friend can get out easily, even if he is just randomly running around.

From your friend’s description, you can figure out at which clearing he is. Assuming that every time he reaches a clearing, he runs in a uniformly random direction (including back the way he came), and that it takes him exactly one minute to get from clearing to clearing, can you predict how long it will take him to get out on average?

Input

The first line contains two integers $N$ and $M$, where $N$ is the number of clearings in the woods ($2 \leq N \leq 20$), and $M$ is the total number of paths between clearings. The clearings are numbered $0$ through $N-1$, such that clearing $0$ is the one where your friend is right now and clearing $N-1$ is the exit of the woods.

The next $M$ lines each contain two integers $K$ and $L$, indicating a path between clearing $K$ and clearing $L$ ($0 \leq K, L < N$, $K \neq L$).

You may assume that it is possible for your friend to reach the exit by following paths, that paths do not cross, and that there is at most one path between any two clearings.

Output

Output a single line containing a single number: the expected value of the number of minutes it will take your friend to get out of the woods.

Your answer may have an absolute error of at most $10^{-5}$.

3 3
0 1
1 2
0 2

2.000000

5 6
0 1
0 2
1 2
2 4
0 3
3 4

6.727273

4 4
0 1
1 3
3 0
0 2

3.333333