Lost in the Woods

Your friend is lost in the woods. He called and asked you to come get him, but you are very busy and would rather stay home. You look up a map of the woods. The woods consist of a small number of clearings with paths connecting them. You hope the woods are small and simple enough that your friend gets out easily even if he just runs around at random.

From your friend's description you can tell which clearing he is in right now. Every time he reaches a clearing he picks one of the paths leading out of it uniformly at random and runs down it. That includes the path he just came from. Moving from one clearing to the next takes him exactly one minute. Compute the expected number of minutes until he gets out of the woods.

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

Each of the next $M$ lines contains two integers $K$ and $L$, meaning there is a path between clearing $K$ and clearing $L$ ($0 \le K, L \le N-1$, $K \ne L$).

Your friend can reach the exit by following paths. At most one path runs between any two clearings, and paths do not cross. Some clearings may be unreachable from clearing $0$.

Print one line with the expected number of minutes until your friend gets out of the woods. Round the value at the seventh decimal digit, rounding a half up, and print exactly six digits after the decimal point.