도박 안내서

이웃 나라의 철도망은 $1$번부터 $n$번까지 번호가 붙은 도시 $n$개와, 서로 다른 두 도시를 잇는 양방향 선로 $m$개로 이루어져 있다. 표는 모든 도시에 놓인 자동 발매기에서만 살 수 있다. 해커가 발매기를 건드린 뒤로 발매기는 전부 다음과 같이 작동한다. $a$번 도시의 발매기에 동전 하나를 넣으면, $a$번 도시와 선로로 직접 이어진 도시 가운데 하나를 균등한 확률로 골라 그 도시로 가는 편도 표 한 장을 내준다. 같은 도시에서 산 표라도 도착 도시는 서로 독립으로 정해진다.

컴퓨터공학을 공부하는 학생이 자신이 사는 $1$번 도시에서 지역 프로그래밍 대회가 이미 시작된 $n$번 도시로 가려고 한다. 학생은 발매기가 어떻게 작동하는지 알고 있고(물론 무작위 선택의 결과를 미리 알 수는 없다), 철도망 지도도 있다. 표를 한 장 사면 거기 적힌 도착 도시를 확인한 다음, 그 표를 바로 써서 도착 도시로 이동하거나, 표를 버리고 지금 있는 도시에서 새 표를 살 수 있다. 표는 얼마든지 계속 살 수 있다. $n$번 도시에 닿는 순간 여행은 끝난다.

학생은 계산 끝에 다음 두 조건을 만족하는 이동 전략을 찾아냈다.

• 여행이 언젠가 끝날 확률이 $1$이다.
• 여행에 쓰는 동전 개수의 기댓값이 가능한 한 작다.

학생이 쓰게 될 동전 개수의 기댓값을 구하라.

첫 줄에 도시의 수 $n$과 선로의 수 $m$이 주어진다($1 \le n, m \le 300000$).

다음 $m$개 줄에는 서로 다른 두 정수 $a$와 $b$가 주어지며($1 \le a, b \le n$), $a$번 도시와 $b$번 도시를 잇는 선로 하나를 뜻한다. 두 도시를 잇는 선로는 많아야 하나다. $1$번 도시에서 $n$번 도시로 가는 경로는 반드시 존재한다.

동전 개수의 기댓값을 소수점 아래 $10$자리까지 반올림해 한 줄에 출력한다.

그림은 두 번째 예제의 철도망이다.