순간이동 통로

당신이 앉아서 프로그래밍을 하고 있는데 갑자기 전화가 울린다. 문제를 해결하는 데 도움이 필요한 친구 Erik이다. 그는 여러 방이 있고 그중 일부 방 쌍이 통로로 연결된 동굴에 갇혀 있다. 서로 연결된 두 방 사이를 이동하는 데에는 일 초가 걸린다. Erik은 한 방에 있으며 출구까지 얼마나 빨리 갈 수 있는지 알고 싶어 한다. 당신은 ``식은 죽 먹기군''이라고 생각하며 가장 좋아하는 최단 경로 알고리즘을 작성하기 시작한다. 하지만 그때 Erik에게 순간이동을 할 수 있다는 특이한 능력이 있음을 떠올린다.

Erik은 정점 $n$개와 간선 $m$개로 이루어진 무방향 그래프의 $s$번 정점에 있으며, $t$번 정점에 있는 출구로 가려고 한다. 일 초 동안 그는 인접한 정점으로 이동하거나 순간이동할 수 있다. 순간이동하면 균등하게 무작위로 선택된 정점에 도착한다(즉, 모든 정점의 확률은 $\frac{1}{n}$이다). 당신의 임무는 그가 $t$번 정점에 도달하는 데 걸리는 최소한의 가능한 평균 시간을 계산하는 것이다. 다시 말해, 최소의 $\textit{väntevärdet}$을 구해야 한다.

다음은 기댓값에 대한 간단한 소개이다. Erik이 특정 전략을 선택했다고 하자. 그리고 $p_i$을 그가 이 전략을 따를 때 정확히 $i$초 만에 $t$번 정점에 도달하는 데 성공할 확률이라고 하자. 기댓값은 다음과 같이 정의된다. $1\cdot p_1 + 2\cdot p_2 + 3\cdot p_3 + ...$ 나쁜 전략을 선택하면(예를 들어 두 정점 사이를 오가면서 절대 도착하지 않는다면) 기댓값이 무한히 커질 수 있다. 하지만 유한한 기댓값을 얻는 것은 항상 가능하다. 예를 들어 계속해서 순간이동하면 기댓값은 $n$이 된다.

점수

여러 테스트 케이스 그룹으로 풀이를 평가한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 맞혀야 한다.

그룹 | 배점 | 제한

$1$    |$26$|  $2 \le n \le 10$ , $0 \le m \le 20$

$2$    |$35$|  $2 \le n \le 200$ , $0 \le m \le 400$

$3$    |$39$|  추가 제한 없음.

첫째 줄에는 정수 두 개 $n$와 $m$ ($2 \leq n \leq 10^5$ , $0 \leq m \leq 2\cdot 10^5$)가 주어진다. 둘째 줄에는 시작 정점과 출구를 나타내는 정수 두 개 $s$와 $t$ ($1 \leq s,t \leq n$ , $s \neq t$)가 주어진다. 이어지는 $m$개의 줄에는 정수 두 개 $u_i$와 $v_i$ ($1 \leq u_i , v_i \leq n$ , $u_i \neq v_i$)가 주어진다. 이는 $u_i$번 정점과 $v_i$번 정점 사이에 간선이 있음을 뜻한다. 또한 각 정점 쌍 사이에는 최대 하나의 간선만 존재한다.

출구에 도달하는 데 걸리는 시간의 가능한 최소 기댓값을 하나의 수로 출력한다. 답의 상대 오차 또는 절대 오차가 최대 $10^{-2}$이면 정답으로 인정된다.

여기서 최적의 전략은 출구까지 곧장 걸어가는 것이며, $2$초가 걸린다. 따라서 기댓값은 $2$이다.

여기에는 간선이 전혀 없으므로 계속해서 순간이동하는 것만 가능하며, 그러면 기댓값은 $n$이 된다.

여기서 최적의 전략은 4번 정점에 있을 때 순간이동하고, 1번 정점이나 3번 정점에 있을 때는 출구로 곧장 걸어가는 것이다.