Problem:
 Score : 600 points    Problem Statement There is a cave consisting of N rooms and M one-directional passages. The rooms are numbered 1 through N .  Takahashi is now in Room 1 , and Room N has the exit. The i -th passage connects Room s_i and Room t_i ( s_i < t_i ) and can only be traversed in the direction from Room s_i to Room t_i . It is known that, for each room except Room N , there is at least one passage going from that room.  Takahashi will escape from the cave. Each time he reaches a room (assume that he has reached Room 1 at the beginning), he will choose a passage uniformly at random from the ones going from that room and take that passage.  Aoki, a friend of Takahashi's, can block one of the passages (or do nothing) before Takahashi leaves Room 1 . However, it is not allowed to block a passage so that Takahashi is potentially unable to reach Room N .  Let E be the expected number of passages Takahashi takes before he reaches Room N . Find the value of E when Aoki makes a choice that minimizes E .      Constraints  2 \leq N \leq 600  N-1 \leq M \leq \frac{N(N-1)}{2}  s_i < t_i  If i != j , (s_i, t_i) \neq (s_j, t_j) . (Added 21:23 JST)  For every v = 1, 2, ..., N-1 , there exists i such that v = s_i .         Input Input is given from Standard Input in the following format:  N  M  s_1  t_1  :  s_M  t_M       Output Print the value of E when Aoki makes a choice that minimizes E .
Your output will be judged as correct when the absolute or relative error from the judge's output is at most 10^{-6} .        Sample Input 1 4 6
1 4
2 3
1 3
1 2
3 4
2 4      Sample Output 1 1.5000000000  If Aoki blocks the passage from Room 1 to Room 2 , Takahashi will go along the path 1 → 3 → 4 with probability \frac{1}{2} and 1 → 4 with probability \frac{1}{2} . E = 1.5 here, and this is the minimum possible value of E .       Sample Input 2 3 2
1 2
2 3      Sample Output 2 2.0000000000  Blocking any one passage makes Takahashi unable to reach Room N , so Aoki cannot block a passage.       Sample Input 3 10 33
3 7
5 10
8 9
1 10
4 6
2 5
1 7
6 10
1 4
1 3
8 10
1 5
2 6
6 9
5 6
5 8
3 6
4 8
2 7
2 9
6 7
1 2
5 9
6 8
9 10
3 9
7 8
4 5
2 10
5 7
3 5
4 7
4 9      Sample Output 3 3.0133333333

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x):
        s = 0
        for y in v[x]:
            if d[y]:
                d[y] = 0
                e_[y] = dfs(y)
            s += e[y]
        p = 0
        if v[x]:
            res = s/len(v[x])
            res += 1
            p = e[x] = res
        if len(v[x]) > 1:
            ns = s-max([e[y] for y in v[x]])
            p = 1+ns/(len(v[x])-1)
        return p

    def dfs2(x):
        if not v_[x]:
            return
        s = 0
        for y in v_[x]:
            if d[y]:
                d[y] = 0
                dfs2(y)
            s += p[y]/len(v[y])
        p[x] = s

    n,m = LI()
    v = [[] for i in range(n)]
    v_ = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v_[b].append(a)
    e = [0]*n
    d = [1]*n
    d[0] = 0
    e_ = [0]*n
    e_[0] = dfs(0)
    p = [0]*n
    p[0] = 1
    d = [1]*n
    d[n-1] = 0
    dfs2(n-1)
    res = e[0]
    print(res+min(list(map(lambda x:x[0]*(x[2]-x[1]), zip(p,e,e_)))))
    return


if __name__ == "__main__":
    solve()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        s, t = map(int, input().split())
        adj[s].append(t)

    dp0 = [0.] * (N+1)
    ans = N-1
    for i in range(N-1, 0, -1):
        s = 0
        m = -1
        maxj = 0
        for j in adj[i]:
            s += dp0[j]
            if dp0[j] > m:
                m = dp0[j]
                maxj = j
        dp0[i] = s / len(adj[i]) + 1
        if len(adj[i]) > 1:
            dp = dp0[:]
            dp[i] = (s - m) / (len(adj[i]) - 1) + 1
            for ii in range(i-1, 0, -1):
                ss = 0
                for jj in adj[ii]:
                    ss += dp[jj]
                dp[ii] = ss / len(adj[ii]) + 1
            ans = min(ans, dp[1])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
a = [[] for i in range(n-1)]
for i in range(m):
  s, t = map(int, input().split())
  a[s-1].append(t-1)
dp = [0]*n
sum_d = [0]*(n-1)
max_d = [0]*(n-1)
b = [0]*n
for i in range(n-2,-1,-1):
  for j in a[i]:
    sum_d[i] += dp[j] + 1
    b[i] += 1
    if max_d[i] < dp[j]+1 and len(a[i]) > 1:
      max_d[i] = dp[j]+1  
  dp[i] = sum_d[i] / b[i]
min_dp = dp[0]
for k in range(n-2):
  if b[k]==1:
    continue
  ddp = [0]*k + [dp[k] - (sum_d[k]-max_d[k])/(b[k]-1)]
  for i in range(k-1,-1,-1):
    ddp[i] = sum([ddp[j] for j in a[i] if j <= k]) / b[i]
  min_dp = min(min_dp,dp[0] - ddp[0])
print(min_dp)

Solution (Python):
import sys
input=sys.stdin.readline

N,M=map(int,input().split())
st=[list(map(int,input().split())) for i in range(M)]

data=[[] for i in range(N)]
edge_num=[0]*N
for s,t in st:
    s-=1
    t-=1
    edge_num[s]+=1
    data[s].append(t)

dp=[0]*N

for i in range(N-2,-1,-1):
    kkk=edge_num[i]
    for v in data[i]:
        dp[i]+=(dp[v]+1)/kkk

ans=dp[0]

for i in range(N-1):
    new_dp=dp[:]
    num=data[i][0]
    for v in data[i]:
        if dp[v]>dp[num]:
            num=v
    kkk=edge_num[i]
    if kkk==1:
        continue
    new_dp[i]=0
    for v in data[i]:
        if num==v:
            continue
        else:
            new_dp[i]+=(dp[v]+1)/(kkk-1)
    for j in range(i-1,-1,-1):
        new_dp[j]=0
        kkk=edge_num[j]
        for v in data[j]:
            new_dp[j]+=(new_dp[v]+1)/kkk
    ans=min(ans,new_dp[0])

print(ans)

Solution (Python):
def solve():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        adjL[s].append(t)
        outdegs[s] += 1

    probs = [0] * N
    probs[0] = 1
    for v in range(N):
        for v2 in adjL[v]:
            probs[v2] += probs[v] / outdegs[v]

    dp = [0] * N
    for v in reversed(range(N-1)):
        dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1

    ans = dp[0]
    for vRem in range(N):
        if outdegs[vRem] == 1: continue
        sumDP, maxDP = 0, -1
        for v2 in adjL[vRem]:
            sumDP += dp[v2]
            if dp[v2] > maxDP:
                maxDP = dp[v2]
        dp2 = (sumDP-maxDP) / (outdegs[vRem]-1) + 1
        decre = dp[vRem] - dp2
        ans2 = dp[0] - decre * probs[vRem]
        ans = min(ans, ans2)

    print(ans)


solve()

Solution (Python):
def solve():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    adjLRev = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        adjL[s].append(t)
        adjLRev[t].append(s)
        outdegs[s] += 1

    probs = [0] * N
    expes = [0] * N
    probs[0] = 1
    for v in range(N):
        prob, expe, outdeg = probs[v], expes[v], outdegs[v]
        if prob != 0:
            num = expe / prob
            for v2 in adjL[v]:
                probs[v2] += prob / outdeg
                expes[v2] += prob * (num+1) / outdeg

    probRevs = [0] * N
    expeRevs = [0] * N
    probRevs[-1] = 1
    for v in reversed(range(N)):
        prob, expe = probRevs[v], expeRevs[v]
        if prob != 0:
            num = expe / prob
            for v0 in adjLRev[v]:
                probRevs[v0] += prob / outdegs[v0]
                expeRevs[v0] += prob * (num+1) / outdegs[v0]

    ans = expes[-1]
    for vRem in range(N-1):
        if outdegs[vRem] == 1: continue
        values = []
        prob, expe, outdeg = probs[vRem], expes[vRem], outdegs[vRem]
        for v2 in adjL[vRem]:
            value = expe*probRevs[v2] + expeRevs[v2]*prob + prob*probRevs[v2]
            values.append(value)
        sumV = sum(values)
        ans2 = expes[-1] - sumV / outdeg
        for value in values:
            ans = min(ans, ans2 + (sumV-value) / (outdeg-1))

    print(ans)


solve()

Solution (Python):
import sys
input = sys.stdin.readline

def solve(N, M, adjL, outdegs):
    dp = [0] * N
    for v in reversed(range(N-1)):
        dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1

    ans = dp[0]
    for vRem in range(N-1):
        if outdegs[vRem] == 1: continue
        sumDP, maxDP = 0, -1
        for v2 in adjL[vRem]:
            sumDP += dp[v2]
            if dp[v2] > maxDP:
                maxDP = dp[v2]
        dp[vRem] = (sumDP-maxDP) / (outdegs[vRem]-1) + 1
        for v in reversed(range(vRem)):
            dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1
        ans = min(ans, dp[0])

    print(ans)


N, M = map(int, input().split())
adjL = [[] for _ in range(N)]
outdegs = [0] * N
for _ in range(M):
    s, t = map(int, input().split())
    s, t = s-1, t-1
    adjL[s].append(t)
    outdegs[s] += 1

solve(N, M, adjL, outdegs)

Solution (Python):
def solve():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        adjL[s].append(t)
        outdegs[s] += 1

    dp = [0] * N
    for v in reversed(range(N-1)):
        dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1

    ans = dp[0]
    for vRem in range(N-1):
        if outdegs[vRem] == 1: continue
        sumDP, maxDP = 0, -1
        for v2 in adjL[vRem]:
            sumDP += dp[v2]
            if dp[v2] > maxDP:
                maxDP = dp[v2]
        dp[vRem] = (sumDP-maxDP) / (outdegs[vRem]-1) + 1
        for v in reversed(range(vRem)):
            dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1
        ans = min(ans, dp[0])

    print(ans)


solve()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

INF = 10**5
n, m = map(int, input().split())
e = [INF for _ in range(n)]
e[n-1] = 0
adj = [[] for _ in range(n)]
farthest = [0 for _ in range(n)]
for _ in range(m):
	s, t = map(int, input().split())
	adj[s-1].append(t-1)

for x in range(n-2, -1, -1):
	if adj[x] == [n-1]:
		e[x] = 1		
	else:		
		su = 0
		for v in adj[x]:
			su += e[v]
			farthest[x] = max(farthest[x], e[v])
		e[x] = su/len(adj[x]) + 1

ans = e[0]

for i in range(n-1):
	f = e
	if len(adj[i]) == 1:
		f[i] = INF
	else:
		f[i] = ((e[i] - 1) * len(adj[i]) - farthest[i]) / (len(adj[i]) - 1) + 1

	for x in range(i-1, -1, -1):
		if adj[x] == [n-1]:
			f[x] = 1		
		else:		
			su = 0
			for v in adj[x]:
				if f[v] == INF:
					f[x] = INF
					break
				su += f[v]
			else:
				f[x] = su/len(adj[x]) + 1
	ans = min(ans, f[0])

print(ans)

Solution (Python):
n, m = map(int, input().split())
g = [[] for _ in range(n)]
ig = [[] for _ in range(n)]
z = []

for i in range(m):
    s, t = map(int, input().split())
    g[s-1].append(t-1)
    ig[t-1].append(s-1)
    z.append((s, t))

dp = [0]*n
for v in range(n-1)[::-1]:
    now = 0
    for u in g[v]:
        now += dp[u]
    now /= len(g[v])
    now += 1
    dp[v] = now

p = [0]*(n)
p[0] = 1

for i in range(1, n):
    for _p in ig[i]:
        p[i]+=p[_p]/len(g[_p])

ma = 0
for s, t in z:
    k = len(g[s-1])
    if k ==1 : continue
    a, b = dp[s-1], dp[t-1]
    c = k/(k-1)*(a-1-b/k) + 1
    ma = max(ma, (a-c)*p[s-1])
print(dp[0]-ma)

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

g = [[] for _ in range(N+1)]
ig = [[] for _ in range(N+1)]
for _ in range(M):
    x, y = map(int, input().split())
    g[x].append(y)
    ig[y].append(x)

dp1 = [0] * (N+1)
dp2 = [0] * (N+1)
dp1[1] = 1



for i in range(1, N+1):
    for j in ig[i]:
        dp1[i] += dp1[j]/len(g[j])
df = 0
for i in range(N, 0, -1):
    t = 0
    for v in g[i]:
        t += (dp2[v]+1)
    if len(g[i]) > 0:
        dp2[i] = t/len(g[i])
    if len(g[i]) == 1:
        continue
    for v in g[i]:
        pv = (t-dp2[v]-1)/(len(g[i])-1)
        
        df = max(df, dp1[i]*(dp2[i]-pv))
        
print(dp2[1]-df)

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

g = [[] for _ in range(N+1)]
ig = [[] for _ in range(N+1)]
for _ in range(M):
    x, y = map(int, input().split())
    g[x].append(y)
    ig[y].append(x)

dp1 = [0] * (N+1)
dp2 = [0] * (N+1)
dp1[1] = 1

for i in range(1, N+1):
    for j in ig[i]:
        dp1[i] += dp1[j]/len(g[j])
df = 0
for i in range(N, 0, -1):
    t = 0
    for v in g[i]:
        t += (dp2[v]+1)
    if len(g[i]) > 0:
        dp2[i] = t/len(g[i])
    if len(g[i]) == 1:
        continue
    for v in g[i]:
        pv = (t-dp2[v]-1)/(len(g[i])-1)
        df = max(df, dp1[i]*(dp2[i]-pv))
print(dp2[1]-df)

Solution (Python):
"""
References
----------
[0]. 解説(公式), https://img.atcoder.jp/abc144/editorial.pdf, AtCoder
    - O(NM)
[1]. kmjp. AtCoder ABC 
    - O(NM)
[2]. physics0523. Fork in the Road(ABC144-F), <https://physics0523.hatenablog.com/entry/2019/10/27/235334>, physics0523's 精進ログ
    - O(M)
[3]. Genki Ogaki. BC144 F - Fork in the Road考察＋参戦記, <https://www.onakasuitacity.com/abc144-f>, おじさん、今日プロ始
めるってよ
    - O(M)
"""
def solve(n, m, s, t):
    edges = [[] for i in range(n)]
    for i in range(m):
        u, v = s[i], t[i]
        edges[u-1].append(v-1)
    p = [0] * n
    p[0] = 1
    for i in range(n):
        for j in edges[i]:
            p[j] += p[i] / len(edges[i])
    E = [0] * n
    for i in range(n-2, -1, -1):
        v = [E[j] for j in edges[i]]
        E[i] = 1 + sum(v) / len(v)
    res = E[0]
    for i in range(n):
        deg = len(edges[i])
        if deg <= 1:
            continue
        k = max((E[j], j) for j in edges[i])[1]
        v = [E[j] for j in edges[i] if j != k]
        res = min(res, E[0] + p[i] * (sum(v) / (deg-1) - E[k]) / deg)
    return res

n, m = map(int, input().split())
s = [0] * m
t = [0] * m
for i in range(m):
    s[i], t[i] = map(int, input().split())
print(solve(n, m, s, t))

Solution (Python):
import sys
import math
from collections import deque

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,M=LI()
RES = [-1]*(N+1)
RES[N] = 0.0

MP=[[] for i in range(N+1)]
for _ in range(M):
    i, j = LI()
    MP[i].append(j)

for i in range(N-1, 0, -1):
    div = len(MP[i])
    next_E = 0
    for j in MP[i]: next_E += RES[j] + 1
    RES[i] = next_E / div

result = RES[1]
RESN = [0]*(N+1)

for i in range(1, N-1):
    if len(MP[i]) == 1: continue
    max_j = max((RES[w],w) for w in MP[i])[1]

    for k in range(N-1, 0, -1):
        div = len(MP[k])
        next_E = 0
        for j in MP[k]:
            if k != i or j != max_j:
                next_E += RESN[j]
            else:
                div -= 1
        RESN[k] = (next_E / div) + 1.0
    result = min(result, RESN[1])

print(result)

Solution (Python):
def resolve():
    n,m=map(int,input().split())
    edges=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1
        edges[s].append(t)
 
    
    p=[0]*n
    p[0]=1.0
    for v in range(n):
        for nv in edges[v]:
            p[nv]+=p[v]/len(edges[v])
 
    
    E=[0]*n
    for v in range(n-2,-1,-1):
        for nv in edges[v]:
            E[v]+=E[nv]
        E[v]=1+E[v]/len(edges[v])
 
    ans=E[0]
    for v in range(n):
        if(len(edges[v])<=1): continue
        
        w=max(*((E[w],w) for w in edges[v]))[1]
        dE=0
        deg=len(edges[v])
        for nv in edges[v]:
            if(nv==w): dE-=E[nv]/deg
            else: dE+=E[nv]/(deg-1)/deg
        ans=min(ans,E[0]+p[v]*dE)
 
    print(ans)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)

    
    dp=[None]*n
    dp[n-1]=0.0
    for v in range(n-2,-1,-1):
        deg=len(E[v])
        res=0
        for nv in E[v]:
            res+=dp[nv]
        res/=deg
        dp[v]=res+1

    ans=dp[0]

    
    for v0 in range(n-1):
        if(len(E[v0])<=1): continue
        w0=max((dp[w],w) for w in E[v0])[1] 
        dp1=[None]*n
        dp1[n-1]=0.0
        for v in range(n-2,-1,-1):
            deg=len(E[v])
            res=0
            for nv in E[v]:
                if((v,nv)==(v0,w0)):
                    deg-=1
                else:
                    res+=dp1[nv]
            res/=deg
            dp1[v]=res+1
        ans=min(ans,dp1[0])

    print(ans)
resolve()

Solution (Python):
n, m = map(int, input().split())
st = [list(map(int, input().split())) for _ in range(m)]

e = [[] for _ in range(n)]
for s, t in st:
    e[s-1].append(t-1)

ans = float('inf')
for i in range(n-2, -1, -1):
    if len(e[i]) <= 1:
        continue
    dp = [0.0 for _ in range(n)]
    for j in range(n-2, i, -1):
        temp = 0.0
        for x in e[j]:
            temp += dp[x]
        dp[j] = temp / len(e[j]) + 1.0
    temp = 0.0
    mx = 0.0
    for x in e[i]:
        temp += dp[x]
        mx = max(mx, dp[x])
    dp[i] = (temp - mx) / (len(e[i]) - 1) + 1.0
    for j in range(i-1, -1, -1):
        temp = 0.0
        for x in e[j]:
            temp += dp[x]
        dp[j] = temp / len(e[j]) + 1.0
    ans = min(ans, dp[0])

if ans == float('inf'):
    dp = [0.0 for _ in range(n)]
    for j in range(n-2, -1, -1):
        temp = 0.0
        for x in e[j]:
            temp += dp[x]
        dp[j] = temp / len(e[j]) + 1.0
    print(dp[0])
else:
    print(ans)

Solution (Python):
n, m = map(int, input().split())
from collections import defaultdict

g1 = defaultdict(set)
g2 = defaultdict(set)

for _ in range(m):
    s, t = map(int, input().split())
    g1[s].add(t)
    g2[t].add(s)

p = defaultdict(int)
p[1] = 1

for i in range(1, n + 1):
    for j in g1[i]:
        p[j] += p[i]/len(g1[i])

e = defaultdict(int)
for i in range(n, 0, -1):
    for j in g1[i]:
        e[i] += (e[j] + 1) / len(g1[i])
ans = e[1]

for i in range(n, 0, -1):
    ne = 0
    if len(g1[i]) == 1:
        continue
    for j in g1[i]:
        ne += (e[j] + 1) / (len(g1[i]) - 1)

    for j in g1[i]:
        dis = ne - (e[j] + 1) / (len(g1[i]) - 1) - e[i]
        ans = min(ans,e[1] + p[i]*dis)

print(ans)

Solution (Python):
from collections import defaultdict
N,m=map(int,input().split())
graph=defaultdict(list)
edges=[]
passages=[[] for i in range(N-1)]
for _ in range(m):
    u,v=map(int,input().split())
    passages[u-1].append(v-1)
prob=[0]*N
prob[0]=1
for n,dest in enumerate(passages):
    
    for d in dest:
        prob[d]+=prob[n]/len(dest)

e=[0]*N

for n,dest in list(enumerate(passages))[::-1]:
    
    e[n]=sum(e[d] for d in dest)/len(dest)+1
min_e=e[0]

for n,dest in enumerate(passages):
    if len(dest)==1:
        continue
    new_e=((e[n]-1)*len(dest)-max(e[d] for d in dest))/(len(dest)-1)+1
    min_e=min(min_e,e[0]-(e[n]-new_e)*prob[n])
print(min_e)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

N,M = II()
s,t = Line(M,2)

pt = edges_to_pt(s,t,N,True)

dp = [0]*N

for i in range(N-1)[::-1]:
    val_all = 0
    for p in pt[i]:
        val_all += dp[p]+1
    if len(pt[i])==0:
        continue
    else:
        dp[i] = val_all/len(pt[i])

ans = dp[0]

for i in range(N-1)[::-1]:
    if len(pt[i])==1:
        continue
    dp2 = [0]*N
    max_val = -1
    for p in pt[i]:
        if dp[p]>max_val:
            max_val = dp[p]
            max_p = p
    for j in range(i+1,N):
        dp2[j] = dp[j]
    for j in range(i+1)[::-1]:
        val_all = 0
        for p in pt[j]:
            if j==i and p==max_p:
                continue
            else:
                val_all += dp2[p]+1
        if len(pt[j])==0:
            continue
        else:
            if j!=i:
                dp2[j] = val_all/len(pt[j])
            else:
                dp2[j] = val_all/(len(pt[j])-1)
    if dp2[0]<ans and dp2[0]!=0.0:
        ans = dp2[0]

print(ans)

Solution (Python):
import sys
imput=sys.stdin.readline

n,m=map(int,input().split())
x=[[] for _ in range(n)]
y=[[] for _ in range(n)]
z=[]
for _ in range(m):
  s,t=map(int,input().split())
  x[s-1].append(t-1)
  y[t-1].append(s-1)
  z.append((s-1,t-1))
e=[-1]*n
e[-1]=0
for i in range(n-1)[::-1]:
  a=0
  for c in x[i]:
    a+=e[c]+1
  e[i]=a/len(x[i])

p=[0]*n
p[0]=1

for i in range(1,n):
  for _p in y[i]:
    p[i]+=p[_p]/len(x[_p])
    
ma=0
for s,t in z:
  k=len(x[s])
  if k==1: continue
  a,b=e[s],e[t]
  c=k/(k-1)*(a-1-b/k)
  ma=max(ma, (a-c-1)*p[s])
print(e[0]-ma)

Solution (Python):
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
st = []
roadfrom = [set() for _ in range(N)]
for m in range(M):
    s, t = inpl()
    s, t = s-1, t-1
    st.append((s,t))
    roadfrom[s].add(t)
nb_branches = [len(roadfrom[i]) for i in range(N)]
START, GOAL = 0, N-1
exps = [0]*N
for r in range(GOAL-1,START-1,-1):
    exps[r] = 1 + sum(exps[c] for c in roadfrom[r])/nb_branches[r]
probs = [0]*N
probs[START] = 1
for r in range(N):
    for c in roadfrom[r]:
        probs[c] += probs[r]/nb_branches[r]
ans = 0
for r in range(N):
    nb = nb_branches[r]
    if nb <= 1:
        continue
    new_exp = ((exps[r]-1)*nb - max(exps[c] for c in roadfrom[r]))/(nb-1) + 1
    diff_exp = (exps[r] - new_exp) * probs[r]
    if diff_exp > ans:
        ans = diff_exp
print(exps[START] - ans)

Solution (Python):
import numpy as np

n, m = map(int, input().split())
adj = np.zeros((n, n), dtype=np.bool)
for _ in range(m):
  s, t = map(int, input().split())
  adj[s-1, t-1] = True
deg = adj.sum(axis=1)

ev = np.zeros(n, dtype=np.float)
for i in range(n - 2, -1, -1):
  ev[i] = ev[adj[i]].mean() + 1.

prob = np.zeros(n, dtype=np.float)
prob[0] = 1.
for i in range(n - 1):
  prob[adj[i]] += prob[i] / deg[i]

decrease = 0.
for i in np.where(deg > 1)[0]:
  now = ev[adj[i]].mean()
  cut = (ev[adj[i]].sum() - ev[adj[i]].max()) / (deg[i] - 1)
  decrease = np.maximum(decrease, (now - cut) * prob[i])
    
print(ev[0] - decrease)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


def main():
    n, m = map(int, input().split())
    edges = [[] for _ in range(n)]
    for _ in range(m):
        s, t = map(int, input().split())
        edges[s-1].append(t-1)
    
    ans = n + 1
    for i in range(n - 1):
        
        dp = [0 for _ in range(n)]

        for j in range(n - 2, -1, -1):
            totale, maxe = 0, 0
            for e in edges[j]:
                totale += dp[e]
                maxe = max(maxe, dp[e])
        
            if i == j and len(edges[j]) > 1:
                dp[j] = (totale - maxe) / (len(edges[j]) - 1) + 1
            else:
                dp[j] = totale / len(edges[j]) + 1
        
        ans = min(ans, dp[0])
    
    print("%.10f" % ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline


N, M = map(int, input().split())
u = [[] for i in range(N)]

for i in range(M):
    s, t = map(int, input().split())
    u[s-1].append(t-1)



p = [0] * N
p[0] = 1
for v in range(N):
    for i in range(v):
        if v in u[i]:
            p[v] += p[i]/len(u[i])


q = [0] * N
q[N-1] = 0
for v in reversed(range(N)):
    for i in u[v]:
        q[v] += (1 + q[i])/len(u[v])

v = [0] * N
for i in range(N-1):
    a = len(u[i])
    if a > 1:
        b = max(q[c] for c in u[i])
        v[i] = p[i]*(q[i] - (1+b))/(a-1)

print(q[0]+min(v))

Solution (Python):
import sys
input = sys.stdin.readline


N, M = map(int, input().split())
u = [[] for i in range(N-1)]

for i in range(M):
    s, t = map(int, input().split())
    u[s-1].append(t-1)



p = [0] * N
p[0] = 1
for x, y in enumerate(u):
    for z in y:
        p[z] += p[x]/len(y)


q = [0] * N
q[N-1] = 0
for x, y in list(enumerate(u))[::-1]:
    q[x] = sum(q[z] for z in y)/len(y) + 1

v = [0] * N
for i in range(N-1):
    a = len(u[i])
    if a > 1:
        b = max(q[c] for c in u[i])
        v[i] = p[i]*(q[i] - (1+b))/(a-1)

print(q[0]+min(v))

Solution (Python):
N, M = map(int, input().split())
edges = [[] for i in range(N)]
for i in range(M):
    s, t = map(int, input().split())
    edges[s - 1].append(t - 1)

def calc():
    steps = [0 for i in range(N)]
    for i in range(N - 2, -1, -1):
        steps[i] = 1 / len(edges[i]) * sum(steps[node] for node in edges[i]) + 1

    return steps

steps = calc()

best = steps[0]

for i in range(N - 1):
    if len(edges[i]) == 1: continue
    highest = max(edges[i], key=lambda n: steps[n])
    edges[i].remove(highest)
    best = min(best, calc()[0])
    edges[i].append(highest)

print(best)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M = map(int, readline().split())

ST = list(map(int, read().split()))
S = ST[0::2]
T = ST[1::2]
 
edge_out = [[] for i in range(N)] 
edge_in = [[] for i in range(N + 1)] 
 
for i in range(M):
    s, t = S[i], T[i]
    edge_out[s].append(t)
    edge_in[t].append(s)
    

edge_sum = [len(edge_out[i]) for i in range(N)] 

dp = [0.0]*(N + 1) 
dp[N - 1] = 1.0

for i in range(N - 2, 0, - 1):
    dp[i] = 1 + sum(dp[j] for j in edge_out[i])/edge_sum[i]
    
p_to_i = [0]*(N + 1) 
p_to_i[1] = 1
for i in range(2, N + 1):
    p_to_i[i] = sum(p_to_i[j]/edge_sum[j] for j in edge_in[i])


t = 0

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        
    t = max(t, p_to_i[i]*(dp[i] - 1- ((dp[i] - 1)*edge_sum[i] - max(dp[j] for j in edge_out[i]))/(edge_sum[i] - 1)))
    
print(dp[1] - t)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M = map(int, readline().split())

m = map(int,read().split())
ST = zip(m,m)
 
edge_out = [[] for i in range(N)] 
edge_in = [[] for i in range(N + 1)] 
 
for s,t in ST:
    edge_out[s].append(t)
    edge_in[t].append(s)
    

edge_sum = [len(edge_out[i]) for i in range(N)] 

dp = [0.0]*(N + 1) 
dp[N - 1] = 1.0

for i in range(N - 2, 0, - 1):
    dp[i] = 1 + sum(dp[j] for j in edge_out[i])/edge_sum[i]
    
p_to_i = [0]*(N + 1) 
p_to_i[1] = 1
for i in range(2, N + 1):
    p_to_i[i] = sum(p_to_i[j]/edge_sum[j] for j in edge_in[i])


t = 0

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        
    t = max(t, p_to_i[i]*(dp[i] - 1- ((dp[i] - 1)*edge_sum[i] - max(dp[j] for j in edge_out[i]))/(edge_sum[i] - 1)))
    
print(dp[1] - t)

Solution (Python):
N, M = map(int, input().split())
edge_out = [[] for i in range(N)] 
edge_in = [[] for i in range(N + 1)] 
for i in range(M):
    s, t = map(int, input().split())
    edge_out[s].append(t)
    edge_in[t].append(s)

edge_sum = [len(edge_out[i]) for i in range(N)] 

dp = [0.0]*(N + 1) 
dp[N - 1] = 1.0

for i in range(N - 2, 0, - 1):
    dp[i] = 1 + sum(dp[j] for j in edge_out[i])/edge_sum[i]
    
p_to_i = [0]*(N + 1) 
p_to_i[1] = 1
for i in range(2, N + 1):
    p_to_i[i] = sum(p_to_i[j]/edge_sum[j] for j in edge_in[i])


t = 0

for i in range(1, N - 1):
    if edge_sum[i] == 1:
        continue
        
    t = max(t, p_to_i[i]*(dp[i] - 1- ((dp[i] - 1)*edge_sum[i] - max(dp[j] for j in edge_out[i]))/(edge_sum[i] - 1)))
    
print(dp[1] - t)

Solution (Python):
N, M = map(int, input().split())
passages = [[] for i in range(N-1)]
for i in range(M):
    s, t = map(int, input().split())
    passages[s-1].append(t-1)

prob = [0] * N
prob[0] = 1
for n, dest in enumerate(passages):
    for d in dest:
        prob[d] += prob[n] / len(dest)


E = [0] * N
for n, dest in list(enumerate(passages))[::-1]:
    E[n] = sum(E[d] for d in dest) / len(dest) + 1

min_E = E[0]


for n, dest in enumerate(passages):
    if len(dest) == 1:
        continue
    new_E = ((E[n] - 1) * len(dest) - max(E[d] for d in dest)) / (len(dest) - 1) + 1
    min_E = min(min_E, E[0] - (E[n] - new_E) * prob[n])

print(min_E)

Solution (Python):
N, M = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(M)]

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

DP = [0] * N
ans = N
D = [0] * N
for i in range(N - 2, -1, -1):
  ma = 0
  su = 0
  le = len(R[i])
  for j in R[i]:
    su += DP[j]
    ma = max(ma, DP[j])

  DP[i] = su / le + 1 
  if le == 1:
    D[i] = 0
  else:
    D[i] = DP[i] - (((su - ma) / (le - 1)) + 1)

P = [0] * N 
P[0] = 1
ma = 0
man = -1
for i in range(N - 1):
  t = P[i] / len(R[i])
  for j in R[i]:
    P[j] += t 
  t = P[i] * D[i]
  R[i].sort()
  if ma < t:
    ma = t
    man = i
 
if ma == -1:
  print(DP[0])
else:
  print(DP[0] - ma)

Solution (Python):

from collections import defaultdict

N,M=map(int, raw_input().split())
E = defaultdict(list)
for i in xrange(M):
    s,t = map(int, raw_input().split())
    E[s-1].append(t-1)

mn = float('inf')
for b in xrange(N):
    dp = [0 for _ in range(N)]
    dp[N-1] = 0.0
    for i in xrange(N-2, -1, -1):
        s = 0.0
        mx = 0.0
        for e in E[i]:
            s += dp[e]
            if mx < dp[e]:
                mx = dp[e]
        l = len(E[i])
        if b==i and l > 1:
            s -= mx
            l -= 1
        dp[i] = s / l + 1
    if mn > dp[0]:
        mn = dp[0]

print (str(mn))

Solution (Python):
def solve(node):
    global ans
    for i in range(N-1, 0, -1):
        s = 0
        maxi = 0
        num = len(paths[i])-1

        for to in paths[i]:
            s += dp[to]
            if(maxi<dp[to]):
                maxi=dp[to]
        if(i == node and num >= 2):
            num -= 1
            s -= maxi
        
        dp[i] = s / num + 1
    if(ans>dp[1]):
        ans = dp[1]


N, M = map(int, input().split())
paths = [[0]for i in range(N + 1)]
dp = [0 for i in range(N+1)]
ans = 1e12
for i in range(M):
    s, t = map(int, input().split())
    paths[s].append(t)
for i in range(N):
    solve(i)
print(ans)