Hypno

도시 어딘가에 새로운 PokéStop이 열렸다는 소식을 방금 들었습니다. 그곳에 가서 거기서 얻을 수 있는 아이템을 모으려고 합니다. 도시에는 교차로 $n$개가 있고, 이들은 양방향 도로 $m$개로 연결되어 있습니다. 교차로는 1부터 $n$까지 번호가 붙어 있습니다. 지금은 1번 교차로에 있고, PokéStop은 $n$번 교차로에 있습니다. 도로 하나를 건너는 데 1분이 걸립니다.

각 도로에는 Hypno가 한 마리씩 있습니다. 도로의 중간 지점에 도달하면 Hypno가 정신 능력을 사용하고, 당신은 아주 짧게 잠이 듭니다. 그러면 Hypno가 당신을 그 도로의 임의의 끝점으로 몽유병 상태로 걸어가게 합니다. 1분 뒤 확률 $\frac{1}{2}$로 도로 반대편 끝에 있고, 그렇지 않으면 원래 교차로에 그대로 있습니다.

당신은 각 Hypno에 대해 확률 $\frac{1}{2}$로 면역이 있습니다. 지금 있는 도로에 면역이 있는 Hypno가 있으면 그 도로는 항상 1분 만에 안전하게 건넙니다. 면역이 없는 Hypno가 있으면 그 도로를 건널 때마다 잠이 듭니다. 처음에는 어느 도로에 어떤 Hypno가 있는지 모르지만, 도로를 건너 보려고 시도한 뒤에는 지금 어느 끝점에 있는지 알 수 있습니다. $n$번 교차로의 PokéStop에 도달하는 데 걸리는 기대 시간의 최솟값은 얼마입니까?

첫 줄에 정수 $n$과 $m$이 주어집니다 ($2 \le n \le 200000$, $1 \le m \le 200000$). 각각 교차로 수와 도로 수입니다. 이어지는 $m$개의 줄에는 정수 $a$와 $b$가 주어지며 ($1 \le a, b \le n$, $a \ne b$), 이는 도로로 연결된 두 교차로입니다. 같은 두 교차로를 잇는 도로는 두 개 이상 없습니다. 도시는 연결되어 있어서 어떤 교차로에서든 다른 모든 교차로에 도달할 수 있습니다.

$n$번 교차로에 도달하는 데 걸리는 기대 시간의 최솟값을 실수 하나로 출력합니다. 절대 오차 또는 상대 오차가 $10^{-9}$를 넘지 않으면 정답으로 인정합니다.

첫 번째 예제에서 최적 전략은 두 번째 도로를 이용해 목적지로 계속 직접 가 보는 것입니다. 확률 $\frac{1}{2}$로 그 도로의 Hypno에 면역이 있어서 1분 만에 도착합니다. 나머지 경우에는 면역이 없어서, 이때의 기대 시간은 $\frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 + \frac{1}{8} \cdot 3 + \frac{1}{16} \cdot 4 + \cdots = 2$입니다. 전체 기대 시간은 $\frac{1}{2} \cdot 1 + \frac{1}{2} \cdot 2 = \frac{3}{2}$입니다.

두 번째 예제에서 두 번째 교차로를 계속 거쳐 가면 기대 시간은 3분입니다. 세 번째 교차로만 계속 거쳐 가도 3분입니다. 이보다 나은 전략이 있습니다.