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-----
4 6
1 4
2 3
1 3
1 2
3 4
2 4

-----Sample Output-----
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.

Difficulty: interview

Starter code:

Solutions:
n, m = list(map(int, input().split()))
edges_from = [[] for _ in range(n)]
edges_to = [[] for _ in range(n)]

for _ in range(m):
    _from, to = [int(x)-1 for x in input().split()]
    edges_from[_from].append(to)

E_dist_to_goal = [0] * n
P_of_reaching = [0] * n
P_of_reaching[0] = 1

for v in range(n-2, -1, -1):
    routes = edges_from[v]
    for next_v in routes:
        E_dist_to_goal[v] += E_dist_to_goal[next_v] + 1
    E_dist_to_goal[v] /= len(routes)

for v in range(n-1):
    P_now = P_of_reaching[v]
    routes = edges_from[v]
    P_next = P_now / len(routes)
    for next_v in routes:
        P_of_reaching[next_v] += P_next

initial_ans = E_dist_to_goal[0]
answers = [initial_ans]
for v in range(n-2):
    routes = edges_from[v]
    num_of_routes = len(routes)
    if num_of_routes == 1:
        continue
    not_cut_dist = E_dist_to_goal[v]
    longest_dist = max([E_dist_to_goal[next_v]+1 for next_v in routes])
    after_cut_dist = (not_cut_dist - longest_dist/num_of_routes) * num_of_routes / (num_of_routes-1)
    delta = not_cut_dist - after_cut_dist
    candidate = initial_ans - delta * P_of_reaching[v]
    answers.append(candidate)

print((min(answers)))


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

    N, M = list(map(int, input().split()))
    adjL = [[] for _ in range(N)]
    adjLRev = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = list(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(list(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()


import sys

n, m = list(map(int, input().split()))
links = [set() for _ in range(n)]
counts = [0] * n
for line in sys.stdin:
    s, t = list(map(int, line.split()))
    s -= 1
    t -= 1
    links[s].add(t)
    counts[s] += 1

# Expected number of edges passing from i to N
expected = [0.] * n
exp_get = expected.__getitem__

# i から伸びる辺を1本消すことで削減できる"iからNまでの辺数の期待値"の最大量
reducible = [0.] * n

for i in range(n - 2, -1, -1):
    nxt_exp = list(map(exp_get, links[i]))
    sum_exp = sum(nxt_exp)
    cnt = counts[i]

    expected[i] = sum_exp / cnt + 1

    if cnt > 1:
        reduced_exp = (sum_exp - max(nxt_exp)) / (cnt - 1) + 1
        reducible[i] = expected[i] - reduced_exp
    else:
        reducible[i] = 0.

# Probability of visiting i when starting from 1
probability = [0.] * n
probability[0] = 1.

rdc = 0.

for i in range(n - 1):
    fp = probability[i]
    jp = fp / counts[i]
    for j in links[i]:
        probability[j] += jp
    rdc = max(rdc, fp * reducible[i])

print((expected[0] - rdc))


import sys
input = sys.stdin.readline


n, m = map(int, input().split())
edges_from = [[] for _ in range(n)]
edges_to = [[] for _ in range(n)]

for _ in range(m):
    _from, to = map(lambda x: int(x)-1, input().split())
    edges_from[_from].append(to)

E_dist_to_goal = [0] * n
P_of_reaching = [0] * n
P_of_reaching[0] = 1

for v in range(n-2, -1, -1):
    routes = edges_from[v]
    for next_v in routes:
        E_dist_to_goal[v] += E_dist_to_goal[next_v] + 1
    E_dist_to_goal[v] /= len(routes)

for v in range(n-1):
    P_now = P_of_reaching[v]
    routes = edges_from[v]
    P_next = P_now / len(routes)
    for next_v in routes:
        P_of_reaching[next_v] += P_next

initial_ans = E_dist_to_goal[0]
short_cut = 0
for v in range(n-2):
    routes = edges_from[v]
    num_of_routes = len(routes)
    if num_of_routes == 1:
        continue
    not_cut_dist = E_dist_to_goal[v]
    longest_dist = max([E_dist_to_goal[next_v]+1 for next_v in routes])
    after_cut_dist = (not_cut_dist - longest_dist/num_of_routes) * num_of_routes / (num_of_routes-1)
    delta = (not_cut_dist - after_cut_dist) * P_of_reaching[v]
    short_cut = max(short_cut, delta)

ans = initial_ans - short_cut
print(ans)

def solve_f(n, g):
    e_base = [0.0] * (n + 1)
    p_base = [0.0] * (n + 1)

    # e_base
    for i in range(n - 1, 0, -1):
        e_base[i] = sum([e_base[j] for j in g[i]]) / len(g[i]) + 1.0

    # p_base
    p_base[1] = 1.0
    for i in range(1, n):
        for j in g[i]:
            p_base[j] += p_base[i] / len(g[i])

    # print(p_base, e_base)

    # find maximal gap
    gap = 0.0
    for i in range(1, n):
        if len(g[i]) == 1:
            continue
        total = sum([e_base[j] + 1 for j in g[i]])
        maxim = max([e_base[j] + 1 for j in g[i]])
        gap_i = (total / len(g[i]) - (total - maxim) / (len(g[i]) - 1)) * p_base[i]
        gap = max(gap_i, gap)

    return e_base[1] - gap


def main():
    # input
    n, m = list(map(int, input().split()))
    g = [[] for _ in range(n)]
    for _ in range(m):
        s, t = list(map(int, input().split()))
        g[s].append(t)
    res = solve_f(n, g)
    print(res)


def test():
    assert abs(solve_f(4, [[], [2, 3, 4], [3, 4], [4]]) - 1.5) < 0.000001
    assert abs(solve_f(3, [[], [2], [3]]) - 2.0) < 0.000001


def __starting_point():
    test()
    main()

__starting_point()

import sys

n, m = list(map(int, input().split()))
links = [set() for _ in range(n)]
counts = [0] * n
for line in sys.stdin:
    s, t = list(map(int, line.split()))
    s -= 1
    t -= 1
    links[s].add(t)
    counts[s] += 1

# Expected number of edges passing from i to N
expected = [0.] * n
exp_get = expected.__getitem__

# i から伸びる辺を1本消すことで削減できる"iからNまでの辺数の期待値"の最大量
reducible = [0.] * n

for i in range(n - 2, -1, -1):
    nxt_exp = list(map(exp_get, links[i]))
    sum_exp = sum(nxt_exp)
    cnt = counts[i]

    expected[i] = sum_exp / cnt + 1

    if cnt > 1:
        reduced_exp = (sum_exp - max(nxt_exp)) / (cnt - 1) + 1
        reducible[i] = expected[i] - reduced_exp
    else:
        reducible[i] = 0.

# Probability of visiting i when starting from 1
probability = [0.] * n
probability[0] = 1.

for i in range(n - 1):
    jp = probability[i] / counts[i]
    for j in links[i]:
        probability[j] += jp

print((expected[0] - max(p * r for p, r in zip(probability, reducible))))


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))


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)

import numpy as np

n, m = list(map(int, input().split()))
adj = np.zeros((n, n), dtype=np.bool)
for _ in range(m):
  s, t = list(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))


n,m = map(int,input().split())
g = [list() for _ in range(n)]
for _ in range(m):
  s,t = map(int,input().split())
  g[s-1].append(t-1)
prop = [0]*n
expc = [10**6]*n
prop[0] = 1
expc[-1] = 0
for i in range(n):
  if not g[i]:
    continue
  t = len(g[i])
  for x in g[i]:
    prop[x] += prop[i]/t
for i in range(n-1,-1,-1):
  if not g[i]:
    continue
  t = len(g[i])
  f = 0
  for x in g[i]:
    f += expc[x] + 1.0
  f /= t
  expc[i] = f

cans = expc[0]
for i in range(n-1):
  t = len(g[i])
  if t < 2:
    continue
  c = max(expc[x] for x in g[i])
  ne = (expc[i]*t - (c+1))/(t-1)
  de = expc[i] - ne
  na = expc[0] - de*prop[i]
  if cans > na:
    cans = na
print(cans)

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)

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)

(n,m),*d = [list(map(int, s.split())) for s in open(0)]

d.sort()
l = [0] * n
for i in range(m):
    d[i] = [d[i][0]-1, d[i][1]-1]
    l[d[i][0]] += 1

p = [0] * n
p[0] = 1
for x in d:
    p[x[1]] += p[x[0]]/l[x[0]]

e = [0] * n
index = d[-1][0]
max_in_index = 0
max_reduce_e = 0

for x in d[::-1] + [[-1, -1]]:
    if index != x[0]:
        if l[index] > 1:
            max_reduce_e = max(max_reduce_e, 
                               p[index] * (e[index]/l[index] - (e[index] - max_in_index)/(l[index] - 1)))
        e[index] /= l[index]
        index = x[0]
        max_in_index = 0
    max_in_index = max(max_in_index, e[x[1]] + 1)
    e[x[0]] += e[x[1]] + 1

print(e[0] - max_reduce_e)

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

#n = int(input())
n,m = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
for _ in range(m):
    s,t = [int(i)-1 for i in readline().split()]
    g[s].append(t)

L = [len(gi) for gi in g]

p = [0]*n
p[0] = 1
for i in range(n-1):
    c = p[i]/L[i]
    for v in g[i]:
        p[v] += c

dp0 = [0]*(n)
dp1 = [1000000]*(n)

for i in range(n-2,-1,-1):
    res = 0
    m = 0
    for v in g[i]:
        res += dp0[v]
        if m<dp0[v]: m = dp0[v]
    dp0[i] = 1 + res/L[i]

    if L[i] >= 2:
        dp1[i] = 1 + (res-m)/(L[i]-1)
    
res = max((dp0[i] - dp1[i])*p[i] for i in range(n))

print((dp0[0]-max(0,res)))












def f_fork_in_the_road():
    # 参考: https://www.onakasuitacity.com/abc144-f/
    N, M = [int(i) for i in input().split()]
    Nodes = [[int(i) for i in input().split()] for j in range(M)]

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

    # editorial の DP テーブルの確率部分
    probability = [0] * N
    probability[0] = 1.0
    for v in range(N):
        for next_vertex in edges[v]:
            probability[next_vertex] += probability[v] / len(edges[v])

    # 期待値
    expected_value = [0] * N
    for v in range(N - 2, -1, -1):
        for next_vertex in edges[v]:
            expected_value[v] += expected_value[next_vertex]
        expected_value[v] = 1 + expected_value[v] / len(edges[v])

    ans = expected_value[0]
    for v in range(N):
        if len(edges[v]) <= 1:
            continue
        # 各頂点 v に対して、v から出る辺 vw のうち
        # w での期待値が最大のものの分を差分から引く。残りは足す
        v_max_expected = max(((expected_value[w], w) for w in edges[v]))[1]
        expected_diff = 0.0
        outdegree = len(edges[v])
        for next_vertex in edges[v]:
            if next_vertex == v_max_expected:
                expected_diff -= expected_value[next_vertex] / outdegree
            else:
                expected_diff += expected_value[next_vertex] / (outdegree * (outdegree - 1))
        ans = min(ans, expected_value[0] + probability[v] * expected_diff)
    return round(ans, 10)

print(f_fork_in_the_road())

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

    N, M = list(map(int, input().split()))
    adjL = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = list(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(list(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()


# reference: https://www.onakasuitacity.com/abc144-f/

import numpy as np

n, m = map(int, input().split())
outgoing = [[] for _ in range(n)]
incoming = [[] for _ in range(n)]
for _ in range(m):
    si, ti = map(int, input().split())
    outgoing[si-1].append(ti-1)
    incoming[ti-1].append(si-1)


ex_dp = np.zeros(n)
for v in reversed(range(n-1)):   # O(m)
    outgoing_degree = len(outgoing[v])
    ex_dp[v] = 1 + sum(ex_dp[post] for post in outgoing[v])/outgoing_degree if outgoing_degree!=0 else np.inf

p_dp = np.ones(n)
for v in range(1,n):      # O(m)
    p_dp[v] = sum(p_dp[prev]/len(outgoing[prev]) for prev in incoming[v])

min_ex = ex_dp[0]
for v, posts in enumerate(outgoing):      # O(m)
    outgoing_degree = len(outgoing[v])
    if outgoing_degree <= 1:
        continue

    max_post = max(posts, key= lambda pos: ex_dp[pos])
    diff_v_ex = 0
    for w in posts:
        if w == max_post:
            diff_v_ex -= 1/outgoing_degree * ex_dp[w]
        else:
            diff_v_ex += 1/(outgoing_degree*(outgoing_degree-1)) * ex_dp[w]
    min_ex = min(ex_dp[0] + p_dp[v] * diff_v_ex, min_ex)

print(min_ex)

import sys
input = sys.stdin.readline

#input
N, M = list(map(int, input().split()))
u = [[] for i in range(N)]
#（便宜的に地点から-1としておく）
for i in range(M):
    s, t = list(map(int, input().split()))
    u[s-1].append(t-1)

#output
#地点vにたどり着く確率をp[v]とする。
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])

#期待値をゴールから逆順に求めていく。点vからゴールまでの移動距離の期待値をq[v]とする。
q = [0] * N
q[N-1] = 0
for v in reversed(list(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)))


"""
References
----------
[0]. 解説(公式), https://img.atcoder.jp/abc144/editorial.pdf, AtCoder
    - O(NM)
[1]. kmjp. AtCoder ABC #144 : F - Fork in the Road, <http://kmjp.hatenablog.jp/entry/2019/10/28/0930>, kmjp's blog
    - 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))

import sys
sys.setrecursionlimit(10**7)
inf=float('inf')

def main(n,m,g,uv):
    # 1<=E<=n-1
    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=list(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)))


N, M = list(map(int, input().split()))
passages = [[] for i in range(N-1)]
for i in range(M):
    s, t = list(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)

# no blocking
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]

# with blocking
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)


def main():
    n, m = list(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()


N,M=map(int,input().split())
st=[list(map(int,input().split())) for i in range(M)]
way=[[] for i in range(N)]
for s,t in st:
    way[s-1].append(t-1)
dp=[0]*N
dp_reducable=[0]*N
pr=[0]*N
pr[0]=1
for i in range(N-1,-1,-1):
    l=len(way[i])
    if l>1:
        MAX=0
        x=0
        for j in way[i]:
            x+=dp[j]
            if dp[j]>MAX:
                MAX=dp[j]
        x_r=(x-MAX)/(l-1)+1
        x=x/l+1
        x_r=x-x_r
    elif l==0:
        continue
    else:
        x=dp[way[i][0]]+1
        x_r=0
    dp[i]=x
    dp_reducable[i]=x_r
    i=N-1-i-1
    l=len(way[i])
    for j in way[i]:
        pr[j]+=pr[i]/l
print(dp[0] - max(p * r for p, r in zip(pr, dp_reducable)))

from collections import defaultdict
N,m=list(map(int,input().split()))
graph=defaultdict(list)
edges=[]
passages=[[] for i in range(N-1)]
for _ in range(m):
    u,v=list(map(int,input().split()))
    passages[u-1].append(v-1)
prob=[0]*N
prob[0]=1
for n,dest in enumerate(passages):
    #print(n,dest,'ndest')
    for d in dest:
        prob[d]+=prob[n]/len(dest)
# no blocking
e=[0]*N
#print(prob)
for n,dest in list(enumerate(passages))[::-1]:
    #print(dest,n,'n dess t')
    e[n]=sum(e[d] for d in dest)/len(dest)+1
min_e=e[0]
#with blocking
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)
    

        



import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n, m = list(map(int, input().split()))
    to = defaultdict(list)
    ot = defaultdict(list)
    for _ in range(m):
        s, t = list(map(int, input().split()))
        s, t = s - 1, t - 1
        to[s].append(t)
        ot[t].append(s)
    # print(to)
    # 各頂点からゴールまでの期待値
    ev = [0] * n
    for u in range(n - 2, -1, -1):
        s = 0
        for ku in to[u]:
            s += ev[ku]
        ev[u] = s / len(to[u]) + 1
    # print(ev)
    # 各辺を通る確率
    pe = [[0] * n for _ in range(n)]
    # 各頂点を通る確率
    pn = [0] * n
    # 各頂点を通る確率を計算
    for u in range(n):
        p = 0
        for ou in ot[u]:
            p += pe[ou][u]
        if u == 0: p = 1
        pn[u] = p
        sz = len(to[u])
        for ku in to[u]:
            pe[u][ku] = p / sz
    # print(pn)
    # 変化量の最大値
    dx = 0
    for u in range(n - 1):
        sz = len(to[u])
        if sz == 1: continue
        mx = 0
        for ku in to[u]:
            mx = max(ev[ku], mx)
        nev = ((ev[u] - 1) * sz - mx) / (sz - 1) + 1
        de = pn[u] * (ev[u] - nev)
        dx = max(dx, de)
        # print(u, mx, de, nev)
    print((ev[0] - dx))

main()


import sys
input = sys.stdin.readline

#input
N, M = map(int, input().split())
u = [[] for i in range(N-1)]
#（便宜的に地点から-1としておく）
for i in range(M):
    s, t = map(int, input().split())
    u[s-1].append(t-1)

#output
#地点vにたどり着く確率をp[v]とする。
p = [0] * N
p[0] = 1
for x, y in enumerate(u):
    for z in y:
        p[z] += p[x]/len(y)

#期待値をゴールから逆順に求めていく。点vからゴールまでの移動距離の期待値をq[v]とする。
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))

import sys

n, m = list(map(int, input().split()))
links = [set() for _ in range(n)]
counts = [0] * n
for line in sys.stdin:
    s, t = list(map(int, line.split()))
    s -= 1
    t -= 1
    links[s].add(t)
    counts[s] += 1

# Expected number of edges passing from i to N
expected = [0.] * n

# i から伸びる辺を1本消すことで削減できる"iからNまでの辺数の期待値"の最大量
reducible = [0.] * n

for i in range(n - 2, -1, -1):
    nxt_exp = [expected[j] for j in links[i]]
    sum_exp = sum(nxt_exp)
    cnt = counts[i]

    expected[i] = sum_exp / cnt + 1

    if cnt > 1:
        reduced_exp = (sum_exp - max(nxt_exp)) / (cnt - 1) + 1
        reducible[i] = expected[i] - reduced_exp
    else:
        reducible[i] = 0.

# Probability of visiting i when starting from 1
probability = [0.] * n
probability[0] = 1.

for i in range(n - 1):
    jp = probability[i] / counts[i]
    for j in links[i]:
        probability[j] += jp

print((expected[0] - max(p * r for p, r in zip(probability, reducible))))


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)

N, M = map(int, input().split())
edge_out = [[] for i in range(N)] #edge_out[i]はiから出ている道
edge_in = [[] for i in range(N + 1)] # edge_in[i]はiに行く道
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)] # edge_sum[i] = iから出ている道の本数

dp = [0.0]*(N + 1) # dp[i]はiからNへの距離の期待値
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[i]は1から各iへ到達する確率
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
        # iから出ている道の先にある部屋のうち、その部屋からNまでの距離の期待値が最も大きいものへ通ずる道を塞ぐ
    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)

import math

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

forward_edges = {n+1:[] for n in range(N)}
reverse_edges = {n+1:[] for n in range(N)}
for e in edges:
  forward_edges[e[0]].append(e[1])
  reverse_edges[e[1]].append(e[0])
# print(  forward_edges)
# print(  reverse_edges)
estimated_distance = {n+1:None for n in range(N)}
estimated_distance[N] = 0
probability = {n+1:None for n in range(N)}
probability[1] = 1
def get_probability(n):
  if probability[n] is not None:
    return probability[n]
  prob = 0
  for m in reverse_edges[n]:
    prob += get_probability(m) / len(forward_edges[m])
  probability[n] = prob
  return prob
  
def get_distance(n):
  if estimated_distance[n] is not None:
    return estimated_distance[n]
  total_distance = 0
  for m in forward_edges[n]:
    total_distance += get_distance(m)
  estimated_distance[n] = 1 + total_distance / len(forward_edges[n])
  return estimated_distance[n]


before_distance = get_distance(1)
max_decrease = 0
for n in range(1, N):
  if len(forward_edges[n]) == 1:
    continue
  distances = [get_distance(m) for m in forward_edges[n]]
  distance_diff = sum(distances) / len(distances) - (
    sum(distances)-max(distances))/(len(distances)-1)
  decrease = get_probability(n) * distance_diff
  max_decrease = max(max_decrease, decrease)

print((before_distance - max_decrease))
    


import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
ST = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

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

# 解説AC
# 閉路ないから後ろから見てけばOK


# dp[v][u]: u からの出口を塞いだときの、v から N までのステップ数の期待値の最小値
dp = np.full((N + 1, N + 1), IINF, dtype=float)
dp[N] = 0.0
for v in reversed(list(range(1, N))):
    # 塞がない
    dp[v, :] = dp[graph[v], :].sum(axis=0) / len(graph[v]) + 1
    if len(graph[v]) >= 2:
        # 塞ぐ
        s = dp[graph[v], v].sum() - dp[graph[v], v].max()
        dp[v, v] = s / (len(graph[v]) - 1) + 1
print((dp[1].min()))


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)