Problem G
Teleportgång

Du sitter och programmerar när telefonen plötsligt ringer. Det är din kompis Erik som behöver hjälp med ett problem. Han sitter fast i en grotta med flera rum, där vissa par av rum är sammankopplade med gångar. Det tar en sekund att gå mellan två sammankopplade rum. Erik befinner sig i ett rum och vill veta hur snabbt han kan ta sig till utgången. “Lätt som en plätt” tänker du, och börjar skriva din favorit-kortaste-vägen-algoritm. Men då kommer du ihåg att Erik har en ovanlig förmåga, han kan nämligen teleportera sig.

Erik befinner sig på nod nummer $s$ i en oriktad graf med $n$ noder och $m$ kanter, och han vill ta sig till utgången vid nod nummer $t$. På en sekund kan han antingen gå till en närliggande nod eller teleportera sig. Om han teleporterar sig hamnar han på en likformigt slumpmässig nod (dvs. sannolikheten är $\frac{1}{n}$ för alla noder). Din uppgift är att räkna ut den minsta möjliga genomsnittliga tid det tar för honom att ta sig till nod nummer $t$. Med andra ord, du ska hitta det minsta $\textit{väntevärdet}$.

Här kommer en kort introduktion till väntevärden. Låt oss säga att Erik har valt en viss strategi, och låt $p_ i$ vara sannolikheten att han lyckas ta sig till nod $t$ på exakt $i$ sekunder om han följer strategin. Väntevärdet definieras som

Om man väljer en dålig strategi (t.ex. att gå fram och tillbaka mellan två noder och aldrig komma fram) så kan väntevärdet bli oändligt stort. Det är dock alltid möjligt att uppnå ett ändligt väntevärde – om man exempelvis teleporterar sig om och om igen så blir väntevärdet $n$.

Indata

Den första raden innehåller två heltal $n$ och $m$ ($2 \leq n \leq 10^5$ , $0 \leq m \leq 2\cdot 10^5$). Den andra raden innehåller två heltal $s$ och $t$ ($1 \leq s,t \leq n$ , $s \neq t$): startnod och utgång. De följande $m$ raderna innehåller två heltal $u_ i$ och $v_ i$ ($1 \leq u_ i , v_ i \leq n$ , $u_ i \neq v_ i$), vilket betyder att en kant går mellan noderna $u_ i$ och $v_ i$.

Utdata

Skriv ut ett tal: det minsta möjliga väntevärdet av tiden det tar att ta sig till utgången. Svaret anses korrekt om det har ett relativt eller absolut fel av högst $10^{-2}$.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av Sample 1

Här är den bästa strategin att bara gå raka vägen till utgången, vilket tar $2$ sekunder. Väntevärdet blir alltså $2$.

Förklaring av Sample 2

Här finns det inga kanter alls, så det enda man kan göra är att teleportera sig om och om igen, och då blir väntevärdet $n$.

Förklaring av Sample 3

Här är den bästa strategin att teleportera sig om man är på nod 4, men gå direkt till utgången om man är på nod 1 eller 3.

8 6
2 4
1 2
2 3
3 4
4 5
4 6
7 8

2

5 0
1 2

5

4 2
4 2
1 2
2 3

2.0

6 6
6 2
1 2
3 2
3 1
3 5
5 6
5 4

2.5