숲에서 길을 잃은 친구

친구가 숲에서 길을 잃었다. 데리러 와 달라고 전화가 왔지만 나는 너무 바빠서 그냥 집에 있고 싶다. 급히 숲 지도를 찾아보니 숲은 몇 개의 빈터와 빈터를 잇는 길로 이루어져 있다. 숲이 충분히 작고 단순해서 친구가 아무 방향으로나 뛰어다니기만 해도 쉽게 빠져나오기를 바랄 뿐이다.

친구의 설명을 들으면 지금 어느 빈터에 있는지는 알 수 있다. 친구는 빈터에 도착할 때마다 그 빈터에서 뻗어 나온 길 중 하나를 균등한 확률로 골라 달려간다. 방금 온 길을 되돌아가는 것도 포함한다. 한 빈터에서 다음 빈터까지 가는 데는 정확히 1분이 걸린다. 친구가 숲을 빠져나오기까지 걸리는 시간의 기댓값을 구하라.

첫 줄에 정수 $N$과 $M$이 주어진다. $N$은 숲에 있는 빈터의 개수 ($2 \le N \le 20$), $M$은 빈터를 잇는 길의 개수다. 빈터에는 $0$번부터 $N-1$번까지 번호가 붙어 있고, $0$번 빈터는 친구가 지금 있는 곳, $N-1$번 빈터는 숲의 출구다.

다음 $M$개 줄에는 각각 정수 $K$와 $L$이 주어진다. $K$번 빈터와 $L$번 빈터를 잇는 길이 있다는 뜻이다 ($0 \le K, L \le N-1$, $K \ne L$).

친구는 길을 따라 출구에 도달할 수 있다. 같은 두 빈터를 잇는 길은 많아야 하나이고, 길끼리 교차하지 않는다. $0$번 빈터에서 갈 수 없는 빈터가 있을 수도 있다.

친구가 숲을 빠져나오기까지 걸리는 시간의 기댓값을 분 단위로 한 줄에 출력한다. 소수점 아래 일곱째 자리에서 반올림하고, 소수점 아래를 정확히 여섯 자리로 맞춰 출력한다.