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 $ss$ i en oriktad graf med $nn$ noder och $mm$ kanter, och han vill ta sig till utgången vid nod nummer $tt$. 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}\backslash 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 $tt$. Med andra ord, du ska hitta det minsta 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}p\_i$ vara sannolikheten att han lyckas ta sig till nod $tt$ på exakt $ii$ sekunder om han följer strategin. Väntevärdet definieras som $$1\cdot p_1+2\cdot p_2+3\cdot p_3+\mathrm{.}\mathrm{.}\mathrm{.}1\backslash cdot\; p\_1\; +\; 2\backslash cdot\; p\_2\; +\; 3\backslash cdot\; p\_3\; +\; ...$$ 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 $nn$.

입력

Den första raden innehåller två heltal $nn$ och $mm$ ($2\le n\le {10}^{5}2\; \backslash leq\; n\; \backslash leq\; 10^5$ , $0\le m\le 2\cdot {10}^{5}0\; \backslash leq\; m\; \backslash leq\; 2\backslash cdot\; 10^5$). Den andra raden innehåller två heltal $ss$ och $tt$ ($1\le s,t\le n1\; \backslash leq\; s,t\; \backslash leq\; n$ , $s\mathrm{\ne }ts\; \backslash neq\; t$): startnod och utgång. De följande $mm$ raderna innehåller två heltal $u_{i}u\_i$ och $v_{i}v\_i$ ($1\le u_i,v_i\le n1\; \backslash leq\; u\_i\; ,\; v\_i\; \backslash leq\; n$ , $u_i\mathrm{\ne }{v}_{i}u\_i\; \backslash neq\; v\_i$), vilket betyder att en kant går mellan noderna $u_{i}u\_i$ och $v_{i}v\_i$.

출력

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}10^\{-2\}$.