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):
import sys
sys.setrecursionlimit(10**7)
inf=float('inf')

def main(n,m,g,uv):
    
    eary=[inf]*m
    vary=[inf]*n
    vary[-1]=0
    todo=[n-1]
    def dfs(v,x):
        if vary[v]<inf:return vary[v]
        ret=0
        cnt=0
        for i,nv in g[v]:
            if i==x:continue
            tmp=dfs(nv,x)+1
            eary[i]=tmp
            ret+=tmp
            cnt+=1
        if cnt==0:
            for i in range(n):
                vary[i]=inf
            return inf
        vary[v]=ret/cnt
        return ret/cnt
    e0=dfs(0,-1)
    ary=[-1]*m
    bary=[0]*n
    bary[0]=1
    for v in range(n):
        k=len(g[v])
        e=vary[v]
        for i,nv in g[v]:
            bary[nv]+=1/k*bary[v]
            if k>1 and bary[v]:
                ary[i]=max(0,e-(e*k-eary[i])/(k-1))
                ary[i]*=bary[v]
    return e0-max(0,max(ary))

n,m=map(int,input().split())
uv=[list(map(int,input().split())) for _ in range(m)]
g=[[] for _ in range(n)]
for i,(u,v) in enumerate(uv):
    u,v=u-1,v-1
    g[u].append((i,v))
print(main(n,m,g,uv))

Solution (Python):
n, m = map(int, input().split())
G = [[] for _ in range(n)]
ST = tuple(tuple(map(lambda x:int(x)-1, input().split())) for _ in range(m))
for s, t in ST:
  G[s].append(t)

def f(s, t):
  dp = [0]*n 
  for i in range(n-2, -1, -1):
    temp = 0
    for v in G[i]:
      temp += dp[v]
    if i==s:
      temp -= dp[t]
      dp[i] = temp/(len(G[i])-1) + 1
    else:
      dp[i] = temp/len(G[i]) + 1
  return dp
T = f(-1, -1)
ans = T[0]
for i in range(n-1):
  if len(G[i]) == 1:
    continue
  m = 0
  t = -1
  for v in G[i]:
    if T[v] > m:
      m = T[v]
      t = v
  temp = f(i, t)[0]
  ans = min(ans, temp)
print(ans)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import queue
    mod=10**9+7
    N,M=MI()
    adj=[[]for _ in range(N)]
    for i in range(M):
        s,t=MI()
        s-=1
        t-=1
        adj[s].append(t)
    
    """    
    逆向きに見ればO(M)，全ての通路で試すとO(M^2)
    切るルートをある程度まとめたい，i番目から出る通路のなかで一番でかいやつを無視する，というのをN回
    """
    
    ans=10**10
    
    for i in range(N-1):
        dp=[0]*N
        for j in range(N-2,-1,-1):
            cnt=0
            if j!=i:
                for k in adj[j]:
                    dp[j]+=dp[k]+1
                    cnt+=1
                dp[j]/=cnt
                    
            else:
                max_d=0
                for k in adj[j]:
                    dp[j]+=dp[k]+1
                    cnt+=1
                    max_d=max(max_d,dp[k])
                
                
                if cnt==1:
                    pass
                else:
                    cnt-=1
                    dp[j]-=(max_d+1)
                    dp[j]/=cnt
        
        if dp[0]!=0:
            ans=min(ans,dp[0])
            
    print(ans)
        

                
        
        
        
        
        
        
            
            
    
    

main()

Solution (Python):
int1 = lambda x: int(x) - 1

N, M = map(int, input().split())
edges = [tuple(map(int1, input().split())) for _ in range(M)]
G = [set() for _ in range(N)]
for s, t in edges:
    G[s].add(t)


def E(dp, i):
    return sum(dp[x] for x in G[i]) / len(G[i]) + 1


dp0 = [0] * N
for i in range(N - 2, -1, -1):
    dp0[i] = E(dp0, i)

ans = dp0[0]
for i in range(N - 1):
    if len(G[i]) == 1:
        continue

    maxE = 0
    maxE_ind = None
    for x in G[i]:
        if dp0[x] > maxE:
            maxE_ind = x
            maxE = dp0[x]

    dp = dp0.copy()
    G[i].remove(maxE_ind)
    for j in range(i, -1, -1):
        dp[j] = E(dp, j)
    ans = min(ans, dp[0])
    G[i].add(maxE_ind)

print(ans)

Solution (Python):
N,M=map(int,input().split())
s,t=0,0
G=[[] for i in range(N)]
for i in range(M):
  s,t=map(int,input().split())
  G[s-1].append(t-1)
A=1000
for x in range(N):
  DP=[0]*N
  for i in range(N-2,-1,-1):
    s=0
    for j in range(len(G[i])):
      s=max(s,DP[G[i][j]])
      DP[i]+=DP[G[i][j]]
    if i==x and len(G[i])!=1:
      DP[i]-=s
      DP[i]/=(len(G[i])-1)
    else:
      DP[i]/=len(G[i])
    DP[i]+=1
  A=min(A,DP[0])
print(A)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
ins = defaultdict(set)
ds = [0]*n
sts = [None]*m
for i in range(m):
    s,t = map(int, input().split())
    s -= 1
    t -= 1
    ns[t].add(s)
    ins[s].add(t)
    ds[s] += 1
    sts[i] = (s,t)
ts = [None]*n

def sub(x):
    global ts
    if x is not None:
        s,t = x

        if ds[s]<=1:
            return None
        ns[t].remove(s)
        ins[s].remove(t)
        ds[s] -= 1
    ts[n-1] = 0
    for i in range(n-2, -1, -1):
        tt = 0
        for v in ins[i]:
            tt += (ts[v])
        ts[i] = tt/len(ins[i]) + 1
    if x is not None:
        ns[t].add(s)
        ins[s].add(t)
        ds[s] += 1
    return ts[0]
ans = sub(None)
its = ts[:]
for i in range(n):
    if len(ins[i])>=2:
        mm = max(its[j] for j in ins[i])
        for j in ins[i]:
            if its[j]==mm:
                break
        res = sub((i,j))
        if res is not None:
            ans = min(ans, res)
print(ans)

Solution (Python):
from collections import defaultdict


def main():
    N, M = list(map(int, input().split()))
    adj_from = defaultdict(list)
    adj_to = defaultdict(list)
    for _ in range(M):
        s, t = list(map(lambda x: int(x) - 1, input().split()))
        adj_from[t].append(s)
        adj_to[s].append(t)
    
    prob = [[0] * N for _ in range(N)]
    for t in adj_to[0]:
        prob[0][t] = 1 / len(adj_to[0])
    for s in range(1, N - 1):
        
        prob_sum = sum([prob[n][s] for n in adj_from[s]])
        for t in adj_to[s]:
            prob[s][t] += prob_sum / len(adj_to[s])
    
    expect = [[0] * N for _ in range(N)]
    for s in adj_from[N - 1]:
        expect[s][N - 1] = 1
    for t in range(N - 2, 0, -1):
        
        e = sum([expect[t][n] for n in adj_to[t]]) / len(adj_to[t])
        for s in adj_from[t]:
            expect[s][t] += e + 1
    
    expect_all = sum([p * e for p, e in zip(prob[0], expect[0])])
    
    diff_min = 0  
    for s in range(N - 1):
        if len(adj_to[s]) <= 1:
            continue
        s_prob = 1 if s == 0 else sum([prob[n][s] for n in adj_from[s]])
        
        expect_max, target = 0, None
        for t in adj_to[s]:
            if expect[s][t] > expect_max:
                expect_max = expect[s][t]
                target = t
        
        d = - prob[s][target] * expect[s][target]
        for t in adj_to[s]:
            if t == target:
                continue
            d += ((s_prob / (len(adj_to[s]) - 1)) - prob[s][t]) * expect[s][t]
        diff_min = min(diff_min, d)
    
    print(expect_all + diff_min)


if __name__ == '__main__':
    main()

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    way = [[] for _ in range(n)]
    for _ in range(m):
        s,t = map(int, ipt().split())
        way[s].append(t)

    cos = [0]*(n+1)
    cos[n] = 0 * n
    for i in range(n-1,0,-1):
        nm = 0
        sm = 0
        for j in way[i]:
            nm += 1
            sm += 1+cos[j]
        cos[i] = sm/nm

    gm = cos[1]
    for i in range(1,n-1):
        nm = 0
        ma = 0
        sm = 0
        for j in way[i]:
            nm += 1
            sm += 1+cos[j]
            if ma < 1+cos[j]:
                ma = 1+cos[j]
        if nm == 1:
            continue
        else:
            cos[i] = (sm-ma)/(nm-1)
        for j in range(i-1,0,-1):
            nm = 0
            sm = 0
            for k in way[j]:
                nm += 1
                sm += 1+cos[k]
            cos[j] = sm/nm

        if cos[1] < gm:
            gm = cos[1]

    print(gm)


    return

if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    s, t = map(int, input().split())
    edges[n - s].append(n - t)

dp = [0.0] * n
for i in range(1, n):
    dp[i] = sum(dp[s] + 1.0 for s in edges[i]) / len(edges[i])

ret = dp[-1]
for j in range(n - 1, 0, -1):
    if len(edges[j]) > 1:
        values = sorted(dp[s] + 1.0 for s in edges[j])
        dp[j] = (sum(values) - values[-1]) / (len(edges[j]) - 1)
        for i in range(j + 1, n):
            dp[i] = sum(dp[s] + 1.0 for s in edges[i]) / len(edges[i])
        ret = min(ret, dp[-1])

print(ret)

Solution (Python):
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    s, t = map(int, input().split())
    edges[n - s].append(n - t)

dp1 = [0.0]
for i in range(1, n):
    values = [dp1[s] + 1.0 for s in edges[i]]
    dp1.append(sum(values) / len(values))

ret = 10 ** 10
for j in range(1, n):
    dp2 = dp1[0:j]
    for i in range(j, n):
        if i == j and len(edges[i]) > 1:
            values = [dp1[s] + 1.0 for s in edges[i]]
            values.sort()
            dp2.append((sum(values) - values[-1]) / (len(values) - 1))
        else:
            values = [dp2[s] + 1.0 for s in edges[i]]
            dp2.append(sum(values) / len(values))
    ret = min(ret, dp2[-1])

print(ret)

Solution (Python):
from collections import deque, defaultdict
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

dp = [0.0] * (N + 1)
for s in reversed(range(1, N)):
    dp[s] = sum(dp[t] + 1.0 for t in edge[s]) / len(edge[s])
ans = dp[1]


cut = set()
for s in range(1, N):
    if len(edge[s]) > 1:
        i = edge[s][0]
        for j in edge[s]:
            if dp[i] < dp[j]:
                i = j
        cut.add((s, i))

for ng in cut:
    dp = [0.0] * (N + 1)
    for s in reversed(range(1, N)):
        E = 0.
        prob = 0.
        for t in edge[s]:
            if (s, t) == ng:
                continue
            prob += 1.0
            E += dp[t] + 1.0
        dp[s] = E / prob
    ans = min(ans, dp[1])

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
e = [[] for _ in range(N + 1)]
for _ in range(M):
  x, y = map(int, input().split())
  e[x].append(y)

dp = [0] * (N + 1)
for x in range(N, 0, -1):
  for y in e[x]:
    dp[x] += (dp[y] + 1) / len(e[x])

table = [0] * (N + 1)
table[1] = 1
for x in range(1, N + 1):
  for y in e[x]:
    table[y] += table[x] / len(e[x])
res = 0
for x in range(1, N + 1):
  for y in e[x]:
    if len(e[x]) == 1: break
    u = dp[x] * table[x]
    v = (dp[x] - (dp[y] + 1) / len(e[x])) * len(e[x]) / (len(e[x]) - 1) * table[x]
    res = max(res, u - v)
print(dp[1] - res)

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

def solve():
    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)):
        e = 0
        for v2 in adjL[v]:
            e += dp[v2]
        dp[v] = e/outdegs[v] + 1

    ans = dp[0]
    for vNow in range(N-1):
        if outdegs[vNow] == 1: continue
        maxDP = 0
        vMax = -1
        for v2 in adjL[vNow]:
            if dp[v2] > maxDP:
                maxDP = dp[v2]
                vMax = v2
        e = 0
        for v2 in adjL[vNow]:
            if v2 == vMax: continue
            e += dp[v2]
        dp[vNow] = e/(outdegs[vNow]-1) + 1

        for v in reversed(range(vNow)):
            e = 0
            for v2 in adjL[v]:
                e += dp[v2]
            dp[v] = e/outdegs[v] + 1

        ans = min(ans, dp[0])

    print(ans)


solve()

Solution (Python):
N,M = map(int,input().split())
ST = [tuple(map(int,input().split())) for i in range(M)]

es = [[] for _ in range(N)]
for s,t in ST:
    s,t = s-1,t-1
    es[s].append(t)

dp = [0] * N
for i in range(N-2,-1,-1):
    s = 0
    for to in es[i]:
        s += dp[to]
    dp[i] = 1 + s / len(es[i])

pp = [0] * N
pp[0] = 1.0
for i in range(N-1):
    l = len(es[i])
    for to in es[i]:
        pp[to] += pp[i] / l

ans = dp[0]
for i in range(N-1):
    l = len(es[i])
    if l < 2: continue
    before = 0
    after_whole = 0
    for to in es[i]:
        before += dp[to] / l
        after_whole += dp[to] / (l-1)
    for to in es[i]:
        after = after_whole - dp[to] / (l-1)
        diff = (before - after) * pp[i]
        ans = min(ans, dp[0] - diff)
print(ans)

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

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

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

ans = 10000

for block in range(-1, N-1):
    dp = [0]*N
    
    for v in range(N-2, -1, -1):
        M = 0
        cnt = 0
        
        for nv in G[v]:
            if dp[nv]>M:
                M = dp[nv]
                
            dp[v] += dp[nv]
            cnt += 1
        
        if block==v and cnt>=2:
            dp[v] -= M
            cnt -= 1
        
        dp[v] /= cnt
        dp[v] += 1
    
    if dp[0]<ans:
        ans = dp[0]

print(ans)

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

def calc(ban_s, ban_t):
    dp2 = [0]*N
    dp2[N-1] = 0
    
    for v in range(N-2, -1, -1):
        cnt = 0
        
        for nv in G[v]:
            if v==ban_s and nv==ban_t:
                continue
            
            dp2[v] += dp2[nv]+1
            cnt += 1
        
        if cnt==0:
            dp2[v] = 100000
        else:
            dp2[v] /= cnt
        
    return dp2[0]
    
N, M = map(int, input().split())
G = [[] for _ in range(N)]

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

dp = [0]*N
dp[N-1] = 0

for v in range(N-2, -1, -1):
    for nv in G[v]:
        dp[v] += dp[nv]+1
    
    dp[v] /= len(G[v])

ans = dp[0]

for v in range(N):
    M = 0
    mark = -1
    
    for nv in G[v]:
        if dp[nv]>M:
            M = dp[nv]
            mark = nv
    
    ans = min(ans, calc(v, mark))

print(ans)

Solution (Python):
def main():
    n, m = map(int, input().split())
    st = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in st]
    toP = [0]*n
    toE = [0]*n
    fromE = [0]*n
    toP[0] = 1
    for i in range(n-1):
        p = toP[i]
        if p > 0:
            toE[i] /= toP[i]
        e = toE[i]
        l = len(g[i])
        for j in g[i]:
            toP[j] += p/l
            toE[j] += (e+1)*p/l
    for i in range(n-2, -1, -1):
        l = len(g[i])
        for j in g[i]:
            fromE[i] += (fromE[j]+1)/l
    allE = fromE[0]
    ans = fromE[0]
    tf = [toP[i]*((toE[i]+1)*len(g[i])+sum([fromE[j] for j in g[i]]))
          for i in range(n)]
    for s, t in st:
        if g[s-1]:
            l = len(g[s-1])
            if l > 1:
                ans = min(allE+tf[s-1]*(1/(l-1)-1/l)-toP[s-1] *
                          (toE[s-1]+1+fromE[t-1])/(l-1), ans)
    print(ans)


main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    st = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in st]
    toP = [0]*n
    toE = [0]*n
    fromE = [0]*n
    toP[0] = 1
    for i in range(n-1):
        p = toP[i]
        if p > 0:
            toE[i] /= toP[i]
        e = toE[i]
        l = len(g[i])
        for j in g[i]:
            toP[j] += p/l
            toE[j] += (e+1)*p/l
    for i in range(n-2, -1, -1):
        l = len(g[i])
        for j in g[i]:
            fromE[i] += (fromE[j]+1)/l
    allE = fromE[0]
    ans = fromE[0]
    for s, t in st:
        if g[s-1]:
            temp = allE
            l = len(g[s-1])
            if l < 2:
                continue
            p = toP[s-1]
            temp = allE
            for j in g[s-1]:
                temp -= p*(toE[s-1]+1+fromE[j])/l
                if j != t-1:
                    temp += p*(toE[s-1]+1+fromE[j])/(l-1)
            ans = min(temp, ans)
    print(ans)


main()

Solution (Python):
def iig(vn, en):
    res = [[] for _ in range(vn)]
    for _ in range(en):
        ai, bi = map(lambda x: int(x) - 1, input().split())
        res[ai].append(bi)
    return res

n, m = map(int, input().split())
v = iig(n, m)

nxtsum = [0] * n
e = [0] * n
for i, adjl in reversed(list(enumerate(v))):
	count = len(adjl)
	if count == 0:
		continue
	nxtsum[i] = sum(e[nxt] for nxt in adjl)
	e[i] = 1 + nxtsum[i] / len(adjl)

v_prob = [0] * n
v_prob[0] = 1
for i, adjl in enumerate(v):
	count = len(adjl)
	for nxt in adjl:
		v_prob[nxt] += v_prob[i] / count

loss_max = 0
for i, adjl in enumerate(v):
	count = len(adjl)
	if count <= 1:
		continue
	for j in adjl:
		loss = e[i] - (1 + (nxtsum[i] - e[j]) / (count - 1))
		loss *= v_prob[i]
		if loss > loss_max:
			loss_max = loss

print(e[0] - loss_max)

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

N, M = map(int, readline().split())
Edge = [[] for _ in range(N)]
for _ in range(M):
    s, t = map(int, readline().split())
    s -= 1
    t -= 1
    Edge[s].append(t)

E = [0]*N
for i in range(N-2, -1, -1):
    res = 0
    for j in Edge[i]:
        res += E[j]
    E[i] = 1 + res/len(Edge[i])

p = [0]*N
p[0] = 1
for i in range(N):
    pi = p[i]
    cnt = len(Edge[i])
    for j in Edge[i]:
        p[j] += pi/cnt

ans = E[0]
for i in range(N):
    if len(Edge[i]) <= 1:
        continue
    mj = max(Edge[i], key = lambda x: E[x])
    
    res = 0
    for j in Edge[i]:
        if mj != j:
            res += E[j]
    ans = min(ans, E[0] + p[i]*(1+res/(len(Edge[i])-1)-E[i]))
print(ans)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

def main():
    n,m = mi()
    tree = [[] for _ in range(n)]
    for i in range(m):
        s,t = mi()
        tree[s-1].append(t-1)
    dp = [0]*n
    dpl = [0]*n
    for i in range(n-1):
        dpl[i] = len(tree[i])
    for i in reversed(range(n-1)):
        for k in tree[i]:
            dp[i] += dp[k] 
        dp[i] /= dpl[i]
        dp[i] += 1
    ans = dp[0]
    
    def func(ss,tt):
        tmp = 0
        for l in tree[ss]:
            if l == tt:
                continue
            tmp += dp[l]
        tmp = tmp/(dpl[ss] -1) + 1
        if tmp > dp[ss]:
            return dp[0]
        else:
            dp[ss] = tmp
        
        for a in reversed(range(ss)):
            tmp = 0
            for b in tree[a]:
                tmp += dp[b]
            dp[a] = tmp/dpl[a] + 1
        
        return dp[0]
    
    for i in range(n-1):
        if len(tree[i]) == 1:
            continue
        for k in tree[i]:
            ans = min(ans,func(i,k))
    print(ans)

main()

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

def main():
    n,m = mi()
    tree = [[] for _ in range(n)]
    for i in range(m):
        s,t = mi()
        tree[s-1].append(t-1)
    dp = [0]*n
    for i in reversed(range(n-1)):
        size = len(tree[i])
        for k in tree[i]:
            dp[i] += dp[k] 
        dp[i] /= size
        dp[i] += 1
    ans = dp[0]
    
    def func(ss,tt):
        tmp = 0
        for l in tree[ss]:
            if l == tt:
                continue
            tmp += dp[l]
        tmp = tmp/(len(tree[ss])-1) + 1
        if tmp > dp[ss]:
            return dp[0]
        else:
            dp[ss] = tmp
        
        for a in reversed(range(ss)):
            tmp = 0
            for b in tree[a]:
                tmp += dp[b]
            dp[a] = tmp/len(tree[a]) + 1
        
        return dp[0]
    
    for i in range(n-1):
        if len(tree[i]) == 1:
            continue
        for k in tree[i]:
            ans = min(ans,func(i,k))
    print(ans)

main()

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
tree = [[] for _ in range(n)]
for i in range(m):
    s,t = mi()
    tree[s-1].append(t-1)
dp = [0]*n
for i in reversed(range(n-1)):
    size = len(tree[i])
    for k in tree[i]:
        dp[i] += dp[k] 
    dp[i] /= size
    dp[i] += 1
ans = dp[0]

def func(ss,tt):
    tmp = 0
    for l in tree[ss]:
        if l == tt:
            continue
        tmp += dp[l]
    tmp = tmp/(len(tree[ss])-1) + 1
    if tmp > dp[ss]:
        return dp[0]
    else:
        dp[ss] = tmp
    
    for a in reversed(range(ss)):
        tmp = 0
        for b in tree[a]:
            tmp += dp[b]
        dp[a] = tmp/len(tree[a]) + 1
    
    return dp[0]

for i in range(n-1):
    if len(tree[i]) == 1:
        continue
    for k in tree[i]:
        ans = min(ans,func(i,k))
print(ans)

Solution (Python):
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
go = [[] for i in range(n+1)]
come = [[] for i in range(n+1)]
for a,b in ab:
  go[a].append(b)
  come[b].append(a)
dpe = [0]*(n+1)
for i in range(1,n+1)[::-1]:
  if i < n and go[i]:
    dpe[i] /= len(go[i])
  for j in come[i]:
    dpe[j] += 1+dpe[i]
dpp = [0]*(n+1)
dpp[1] = 1
for i in range(1,n+1):
  for j in go[i]:
    dpp[j] += dpp[i]/len(go[i])
ans = dpe[1]
for a,b in ab:
  pa = dpp[a]
  if len(go[a]) == 1:
    continue
  ea = dpe[a]-1-((dpe[a]-1)*len(go[a])-dpe[b])/(len(go[a])-1)
  ans = min(ans,dpe[1]-pa*ea)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
EPS = 10**(-8)
INF = 10**16

N, M = map(int, input().split())
graph = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].add(b-1)

dp = [0]*N
dps = [0]*N
dpl = [0]*N
for n in reversed(range(N-1)):
    for p in graph[n]:
        if dp[p] != -1:
            dps[n] += dp[p]
            dpl[n] += 1
    if dpl[n] > 0:
        dp[n] = dps[n]/dpl[n] + 1
    else:
        dp[n] = -1

Weight = [0]*N
Weight[0] = 1
for n in range(N):
    for p in graph[n]:
        Weight[p] += Weight[n]/dpl[n]

ans = dp[0]
for n1 in range(N):
    if len(graph[n1]) != 1:
        for n2 in graph[n1]:
            newE = (dps[n1]-dp[n2])/(dpl[n1]-1) + 1
            tmp = dp[0] - Weight[n1]*dp[n1] + Weight[n1]*newE
            if tmp < ans:
                ans = tmp

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
EPS = 10**(-8)
INF = 10**16

N, M = map(int, input().split())
graph = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].add(b-1)

dp = [0]*N
dps = [0]*N
dpl = [0]*N
for n in reversed(range(N-1)):
    for p in graph[n]:
        if dp[p] != -1:
            dps[n] += dp[p]
            dpl[n] += 1
    if dpl[n] > 0:
        dp[n] = dps[n]/dpl[n] + 1
    else:
        dp[n] = -1

Weight = [0]*N
Weight[0] = 1
for n in range(N):
    for p in graph[n]:
        Weight[p] += Weight[n]/dpl[n]

ans = dp[0]
for n1 in range(N):
    if len(graph[n1]) != 1:
        for n2 in graph[n1]:
            newE = (dps[n1]-dp[n2])/(dpl[n1]-1) + 1
            ans = min(ans, dp[0] - Weight[n1]*dp[n1] + Weight[n1]*newE)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
EPS = 10**(-8)
INF = 10**16

N, M = map(int, input().split())
graph = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].add(b-1)

dp = [0]*N
dps = [0]*N
dpl = [0]*N
for n in reversed(range(N-1)):
    for p in graph[n]:
        if dp[p] != -1:
            dps[n] += dp[p]
            dpl[n] += 1
    if dpl[n] > 0:
        dp[n] = dps[n]/dpl[n] + 1
    else:
        dp[n] = -1

Weight = [0]*N
Weight[0] = 1
for n in range(N):
    for p in graph[n]:
        Weight[p] += Weight[n]/dpl[n]

def solve(n):
    dpt = dp[:]
    dpts = [0]*(n+1) + dps[n+1:]
    dptl = [0]*(n+1) + dpl[n+1:]
    dpt[n] = -1
    for p in reversed(range(n)):
        for q in graph[p]:
            if dpt[q] != -1:
                dpts[p] += dpt[q]
                dptl[p] += 1
        if dptl[p] > 0:
            dpt[p] = dpts[p]/dptl[p] + 1
        else:
            dpt[p] = -1
    if dpt[0] == -1: return INF
    return dpt[0]

ans = dp[0]
for n1 in range(N):
    if len(graph[n1]) == 1:
        continue
        
    else:
        for n2 in graph[n1]:
            newE = (dps[n1]-dp[n2])/(dpl[n1]-1) + 1
            ans = min(ans, dp[0] - Weight[n1]*dp[n1] + Weight[n1]*newE)

print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
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():
    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
    p = [0]*n
    p[0] = 1
    for x in range(n):
        for y in v[x]:
            p[y] += p[x]/len(v[x])
    e = [0]*n
    e_ = [0]*n
    for x in range(n)[::-1]:
        s = 0
        for y in v[x]:
            s += e[y]
        if v[x]:
            e[x] = e_[x] = 1+s/len(v[x])
        if len(v[x]) > 1:
            e_[x] = 1+(s-max([e[y] for y in v[x]]))/(len(v[x])-1)
    ans = e[0]
    print(ans+min(list(map(lambda x:x[0]*(x[2]-x[1]), zip(p,e,e_)))))
    return


if __name__ == "__main__":
    solve()

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():
    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
    p = [0]*n
    p[0] = 1
    for x in range(n):
        for y in v[x]:
            p[y] += p[x]/len(v[x])
    e = [0]*n
    e_ = [0]*n
    for x in range(n)[::-1]:
        s = 0
        for y in v[x]:
            s += e[y]
        if v[x]:
            e[x] = e_[x] = 1+s/len(v[x])
        if len(v[x]) > 1:
            e_[x] = 1+(s-max([e[y] for y in v[x]]))/(len(v[x])-1)
    ans = e[0]
    print(ans+min(list(map(lambda x:x[0]*(x[2]-x[1]), zip(p,e,e_)))))
    return


if __name__ == "__main__":
    solve()

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():
    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)
    p = [0]*n
    p[0] = 1
    for x in range(n):
        for y in v[x]:
            p[y] += p[x]/len(v[x])
    e = [0]*n
    e_ = [0]*n
    for x in range(n)[::-1]:
        s = 0
        for y in v[x]:
            s += e[y]
        if v[x]:
            e[x] = e_[x] = 1+s/len(v[x])
        if len(v[x]) > 1:
            e_[x] = 1+(s-max([e[y] for y in v[x]]))/(len(v[x])-1)
    ans = e[0]
    print(ans+min(list(map(lambda x:x[0]*(x[2]-x[1]), zip(p,e,e_)))))
    return


if __name__ == "__main__":
    solve()