Kolmogorov

Andrey는 러시아 외곽 지역의 똑똑한 아이들에게 큰 관심을 가지고 있다. 그 아이들은 근처에 수학 학교가 없다는 이유만으로 좋은 교육을 받지 못한다. Andrey는 기숙사를 갖춘 특별한 학교를 세우는 꿈을 꾼다. 그곳에서 재능 있는 아이들이 함께 살며 공부하고, 모스크바 국립 대학의 교수들이 선생님과 지도교사로 일한다. 그는 이 아이디어가 사람들에게 마음에 드는지 알아보기 위해 전국을 돌아다니며 여러 사람과 이야기하기로 했다.

그는 방금 Nsk에 도착했다. 이 도시의 유일한 학교를 방문해 감동적이고 의욕을 북돋는 연설을 해야 한다. 시간이 촉박하므로 현재 위치에서 학교까지 최대한 빨리 가려고 한다.

Nsk에는 $N$개의 교차로가 있고 $M$개의 양방향 도로로 연결되어 있다. 도로로 직접 연결된 두 교차로 사이를 걷는 데는 정확히 1분이 걸린다. 모든 도로는 서로 다른 두 교차로를 연결하며, 어떤 두 교차로도 두 개 이상의 도로로 직접 연결되지 않고, 모든 교차로 쌍은 직접 또는 간접적으로 연결되어 있다.

Andrey는 교차로 $1$에서 여행을 시작해 학교가 있는 교차로 $N$으로 간다. 그가 목적지까지 걸어야 하는 최소 시간(분)을 계산해 줄 수 있는가? 물론 가능하지만, 이것이 문제의 전부는 아니다.

이 학교의 교장은 이 방문이 마음에 들지 않아 Andrey의 강연을 최대한 짧게 만들 계획이다. 그는 유명한 수학자가 어둠을 매우 무서워한다는 것을 알고 있기에, 잔인한 목적을 달성하기 위해 거의 모든 가로등을 껐다. 이제 매 순간 단 하나의 도로만 불이 켜져 있다. 게다가 어떤 도로에 불이 켜지는지는 매분 바뀔 수 있다. 더 자세히 설명하면 다음과 같다.

• 매분이 시작될 때 $M$개의 가능한 도로 중 하나가 무작위로 균등하게 선택된다.
• 이 도로가 현재 1분 동안 불이 켜진다.
• Andrey가 불이 켜진 도로와 맞닿은 교차로에 서 있다면, 이 도로를 이용해 반대쪽 끝으로 갈 수 있다. 이번 1분 동안 가만히 서 있을 수도 있다. Andrey는 불이 켜진 도로 외의 다른 도로는 이용할 수 없다.

Andrey가 그래프에 대해 모든 것을 알고 최적으로 행동한다고 가정할 때, 목표에 도달하는 데 필요한 기댓값(분)을 구하라.

첫째 줄에 교차로의 수 $N$과 양방향 도로의 수 $M$이 주어진다 ($1 \leq N, M \leq 100\,000$).

다음 $M$개의 줄에는 각각 두 정수 $a_i$와 $b_i$가 주어지며, 이 도로가 연결하는 교차로 쌍을 나타낸다 ($1 \leq a_i, b_i \leq N$, $a_i \neq b_i$). 어떤 교차로에서든 다른 교차로로 갈 수 있고, 자기 자신으로 향하는 간선이나 중복 간선은 없다.

Andrey가 최적으로 행동할 때 교차로 $1$에서 교차로 $N$까지 가는 데 필요한 기댓값(분)을 실수 하나로 출력한다. 답의 절대 오차 또는 상대 오차가 $10^{-6}$을 넘지 않으면 정답으로 인정된다.

형식적으로, 답이 $A$이고 출제진의 답이 $B$일 때, checker는 $\frac{|A-B|}{\max(1,B)} \leq 10^{-6}$이면 답을 인정한다.

첫 번째 예제에서 Andrey는 다음 전략으로 행동할 수 있다.

• 처음에는 교차로 $1$에 머문다.
• 도로 $(1, 2)$에 불이 켜질 때까지 기다렸다가 이용해 교차로 $2$로 간다. 평균 대기 시간은 $2.0$분이다.
• 교차로 $2$에 서서 도로 $(2, 3)$에 불이 켜질 때까지 기다렸다가 이용해 교차로 $3$으로 간다. 평균 대기 시간은 역시 $2.0$분이므로, 목적지에 도달하는 데 필요한 기댓값은 $4.0$분이다.

두 번째 예제에서 Andrey는 다음과 같이 행동할 수 있다.

• 처음에는 교차로 $1$에 머문다.
• 도로 $(1, 2)$ 또는 $(1, 3)$ 중 하나에 불이 켜질 때까지 기다렸다가 각각 교차로 $2$ 또는 $3$으로 간다. 평균 대기 시간은 $2.0$분이다.
• 이제 교차로 $2$ 또는 $3$에 서 있고, 두 경우 모두 교차로 $4$로 가는 도로에 불이 켜질 때까지 기다리면 된다. 평균 대기 시간은 $4.0$분이므로, 학교에 도달하는 데 필요한 기댓값은 $6.0$분이다.