AtCoder Beginner Contest 144 - Fork in the Road

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: MEDIUM_HARD

Starter code:

Solutions:
(n, m) = map(int, input().split())
E = [[] for _ in range(n)]
for _ in range(m):
	(s, t) = map(int, input().split())
	E[s - 1].append(t - 1)
dp = [0] * n
for s in range(n - 2, -1, -1):
	for t in E[s]:
		dp[s] += dp[t]
	if E[s]:
		dp[s] /= len(E[s])
	dp[s] += 1
ans = dp[0]
for s2 in range(n - 1):
	if len(E[s2]) - 1:
		dp2 = [0] * n
		mxi = 0
		mxt = -1
		for t in E[s2]:
			if mxt < dp[t]:
				mxi = t
				mxt = dp[t]
		if mxt < 0:
			continue
		for s in range(n - 2, -1, -1):
			for t in E[s]:
				dp2[s] += dp2[t]
			if s == s2:
				dp2[s] -= mxt
			if s == s2:
				dp2[s] /= len(E[s]) - 1
			elif E[s]:
				dp2[s] /= len(E[s])
			dp2[s] += 1
		ans = min(ans, dp2[0])
print(ans)


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


import sys
(n, m) = map(int, input().split())
links = [set() for _ in range(n)]
counts = [0] * n
for line in sys.stdin:
	(s, t) = map(int, line.split())
	s -= 1
	t -= 1
	links[s].add(t)
	counts[s] += 1
expected = [0.0] * n
reducible = [0.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.0
probability = [0.0] * n
probability[0] = 1.0
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 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)
main()


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


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.0
		prob = 0.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)


import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
(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))


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)


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)
dp3 = [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):
	for v in g[i]:
		dp2[i] += (dp2[v] + 1) / len(g[i])
		if len(g[i]) != 1:
			dp3[i] += (dp2[v] + 1) / (len(g[i]) - 1)
	for v in g[i]:
		if len(g[i]) != 1:
			pv = dp3[i] - (dp2[v] + 1) / (len(g[i]) - 1)
			df = max(df, dp1[i] * (dp2[i] - pv))
print(dp2[1] - df)


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())
edges = zip(M, M)
edges_from = [[] for _ in range(n)]
edges_to = [[] for _ in range(n)]
for (_from, to) in edges:
	edges_from[_from - 1].append(to - 1)
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]
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]
	cut = max(cut, delta)
ans = initial_ans - cut
print(ans)


import sys
import copy

def main():
	input = sys.stdin.readline
	(N, M) = list(map(int, input().split()))
	st = [list(map(int, input().split())) for i in range(M)]
	neighbor = [[] for i in range(N)]
	for (s, t) in st:
		neighbor[s - 1].append(t - 1)
	INF = 100100100
	ev = [INF] * N
	ev[N - 1] = 0
	for i in range(N - 2, -1, -1):
		dsum = 0
		dcount = 0
		for j in neighbor[i]:
			dsum += ev[j]
			dcount += 1
		ev[i] = dsum / dcount + 1
	ans = ev[0]
	for i in range(N - 1):
		evmax = -1
		if len(neighbor[i]) == 1:
			continue
		for j in neighbor[i]:
			if ev[j] > evmax:
				tn = j
				evmax = ev[j]
		evtmp = [INF] * N
		evtmp[i + 1:] = ev[i + 1:]
		for ii in range(i, -1, -1):
			dsum = 0
			dcount = 0
			for jj in neighbor[ii]:
				if ii == i and jj == tn:
					continue
				dsum += evtmp[jj]
				dcount += 1
			evtmp[ii] = dsum / dcount + 1
		if evtmp[0] < ans:
			ans = evtmp[0]
	print(ans)
main()


import sys
import copy
input = sys.stdin.readline
sys.setrecursionlimit(100000)
import heapq

def getN():
	return int(input())

def getList():
	return list(map(int, input().split()))

def solve():
	return

def hakai(cur_tubusi, rooms, revrooms, ex, n):
	if len(rooms[cur_tubusi]) == 0:
		return 1000000
	elif len(rooms[cur_tubusi]) == 1:
		return 1000000
	else:
		ccost = -1
		for cand_tubusi in rooms[cur_tubusi]:
			tmp = ex[cand_tubusi]
			if tmp > ccost:
				ccost = tmp
				tubusi_index = cand_tubusi
		revrooms[tubusi_index].remove(cur_tubusi)
		ex2 = [0 for i in range(n)]
		npaths2 = [0 for i in range(n)]
		for i in range(n):
			roomnum = n - i - 1
			pcost = ex2[roomnum] + 1
			for par in revrooms[roomnum]:
				ex2[par] = (ex2[par] * npaths2[par] + pcost) / (npaths2[par] + 1)
				npaths2[par] += 1
		revrooms[tubusi_index].append(cur_tubusi)
		return ex2[0]

def main():
	(n, m) = getList()
	rooms = [[] for i in range(n + 1)]
	revrooms = [[] for i in range(n + 1)]
	npaths = [0 for i in range(n)]
	for i in range(m):
		(a, b) = getList()
		revrooms[b - 1].append(a - 1)
		rooms[a - 1].append(b - 1)
	ex = [0 for i in range(n)]
	for i in range(n):
		roomnum = n - i - 1
		pcost = ex[roomnum] + 1
		for par in revrooms[roomnum]:
			ex[par] = (ex[par] * npaths[par] + pcost) / (npaths[par] + 1)
			npaths[par] += 1
	ans = ex[0]
	for i in range(n):
		tsekai = hakai(i, rooms, revrooms, ex, n)
		if tsekai < ans:
			ans = tsekai
	print(ans)
main()


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
ST = [list(map(int, input().split())) for _ in [0] * M]
Ef = [[] for _ in [0] * N]
Eb = [[] for _ in [0] * N]
for (s, t) in ST:
	s -= 1
	t -= 1
	Ef[s].append(t)
	Eb[t].append(s)
V = [0] * N
for i in range(N - 2, -1, -1):
	tmp_sum = 0
	tmp_num = 0
	for j in Ef[i]:
		tmp_num += 1
		tmp_sum += V[j]
	V[i] = tmp_sum / tmp_num + 1.0
bq = []
for bi in range(i, N - 1):
	if len(Ef[bi]) <= 1:
		continue
	bj = 0
	tmp = 0
	for j in Ef[bi]:
		if tmp < V[j]:
			tmp = V[j]
			bj = j
	bq.append((bi, bj))
ans = V[0]
for (bi, bj) in bq:
	V2 = [0] * N
	for i in range(N - 2, -1, -1):
		tmp_sum = 0
		tmp_num = 0
		for j in Ef[i]:
			if i == bi and j == bj:
				continue
			tmp_num += 1
			tmp_sum += V2[j]
		V2[i] = tmp_sum / tmp_num + 1.0
	ans = min(ans, V2[0])
print(ans)


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


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


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


def solve():
	import sys
	input = sys.stdin.readline
	(n, m) = map(int, input().split())
	edges = tuple((set() for _ in range(n)))
	for _ in range(m):
		(s, t) = map(int, input().split())
		edges[s - 1].add(t - 1)
	ans = float('inf')
	for del_vertical in range(n):
		E = [0] * n
		for v in reversed(range(n - 1)):
			mx = -1
			for u in edges[v]:
				E[v] += E[u]
				if mx < E[u]:
					mx = E[u]
			if v == del_vertical and len(edges[v]) > 1:
				E[v] = (E[v] - mx) / (len(edges[v]) - 1) + 1
			else:
				E[v] = E[v] / len(edges[v]) + 1
		ans = min(ans, E[0])
	print(ans)
solve()


import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations, combinations
import fractions
from operator import itemgetter
import sys

def input():
	return sys.stdin.readline().strip()
(N, M) = list(map(int, input().split()))
graph = [[] for _ in range(N)]
for _ in range(M):
	(s, t) = list(map(int, input().split()))
	graph[s - 1].append(t - 1)
base_dist = [-1] * N
base_dist[-1] = 0
for i in range(N - 2, -1, -1):
	total = 0
	for node in graph[i]:
		total += base_dist[node]
	base_dist[i] = total / len(graph[i]) + 1
ans = base_dist[0]
for stop in range(0, N - 1):
	dist = copy.deepcopy(base_dist)
	total = 0
	if len(graph[stop]) == 1:
		continue
	max_d = 0
	for node in graph[stop]:
		max_d = max(max_d, dist[node])
		total += dist[node]
	total -= max_d
	total /= len(graph[stop]) - 1
	total += 1
	dist[stop] = total
	for i in range(stop - 1, -1, -1):
		total = 0
		for node in graph[i]:
			total += dist[node]
		dist[i] = total / len(graph[i]) + 1
	ans = min(ans, dist[0])
print(ans)


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


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)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
graph = [[] for _ in range(n)]
graph_dim_out = [0] * n
for i in range(m):
	(s, t) = map(int, input().split())
	(s, t) = (s - 1, t - 1)
	graph_dim_out[s] += 1
	graph[s].append(t)

def func(x):
	dp = [0] * n
	for i in reversed(range(n - 1)):
		if i != x or graph_dim_out[x] == 1:
			for j in graph[i]:
				dp[i] += dp[j]
			dp[i] = dp[i] / graph_dim_out[i] + 1
		else:
			k = -1
			for j in graph[i]:
				dp[i] += dp[j]
				if k == -1 or dp[k] < dp[j]:
					k = j
			dp[i] -= dp[k]
			dp[i] = dp[i] / (graph_dim_out[i] - 1) + 1
	return dp[0]
ans = func(0)
for x in range(1, n - 1):
	ans = min(ans, func(x))
print(ans)


from sys import setrecursionlimit as SRL, stdin
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
(n, m) = rrd()
g1 = [[] for _i in range(605)]
g2 = [[] for _i in range(605)]
e = [0] * 605
for i in range(m):
	(x, y) = rrd()
	g1[x].append(y)
	g2[y].append(x)
p = [0] * 605
p[1] = 1
for i in range(1, n + 1):
	for j in g1[i]:
		p[j] += p[i] / len(g1[i])
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)


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


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


import sys
import copy
input = sys.stdin.readline
(N, M) = list(map(int, input().split()))
st = [list(map(int, input().split())) for i in range(M)]
neighbor = [[] for i in range(N)]
for (s, t) in st:
	neighbor[s - 1].append(t - 1)
INF = 100100100
ev = [INF] * N
ev[N - 1] = 0
for i in range(N - 2, -1, -1):
	dsum = 0
	dcount = 0
	for j in neighbor[i]:
		dsum += ev[j]
		dcount += 1
	ev[i] = dsum / dcount + 1
prb = [0] * N
prb[0] = 1
for i in range(N - 1):
	for j in neighbor[i]:
		prb[j] += prb[i] / len(neighbor[i])
ans = ev[0]
for (s, t) in st:
	(ss, tt) = (s - 1, t - 1)
	pnum = len(neighbor[ss])
	if pnum == 1:
		continue
	evdif = (ev[ss] - (ev[ss] * pnum - (ev[tt] + 1)) / (pnum - 1)) * prb[ss]
	ans = min(ans, ev[0] - evdif)
print(ans)


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


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
from collections import Counter
INF = float('inf')

class Graph(object):

	def __init__(self, N):
		self.N = N
		self.E = [[] for _ in range(N)]

	def add_edge(self, s, t, w=1):
		self.E[s].append(t)

def solve(N: int, M: int, s: 'List[int]', t: 'List[int]'):
	c = Counter(s)
	g = Graph(N)
	for (ss, tt) in zip(s, t):
		g.add_edge(ss, tt)
	DP = [0] * N
	for i in range(N - 2, -1, -1):
		DP[i] = sum((DP[t] for t in g.E[i])) / c[i] + 1
	gm = DP[0]
	for i in range(N - 2):
		if len(g.E[i]) == 1:
			continue
		dp = DP[:]
		for j in range(i, -1, -1):
			(tot, m) = (0, 0)
			for t in g.E[j]:
				tot += dp[t]
				m = max(dp[t], m)
			if i == j:
				dp[j] = (tot - m) / (c[j] - 1)
			else:
				dp[j] = tot / c[j]
			dp[j] += 1
		gm = min(dp[0], gm)
	print(gm)

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	M = int(next(tokens))
	s = [int()] * M
	t = [int()] * M
	for i in range(M):
		s[i] = int(next(tokens)) - 1
		t[i] = int(next(tokens)) - 1
	solve(N, M, s, t)
main()


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


(N, M) = map(int, input().split())
G = [[] for _ in range(N)]
rG = [[] for _ in range(N)]
for _ in range(M):
	(s, t) = map(int, input().split())
	G[s - 1].append(t - 1)
E = [0] * N
for v in range(N - 1)[::-1]:
	n = len(G[v])
	for nv in G[v]:
		E[v] += (E[nv] + 1) * (1 / n)
ans = E[0]
for v in range(N - 1):
	if len(G[v]) == 1:
		continue
	index = -1
	tmp = -1
	for (i, nv) in enumerate(G[v]):
		if tmp < E[nv]:
			index = nv
			tmp = E[nv]
	n = len(G[v]) - 1
	E[v] = 0
	for nv in G[v]:
		if nv == index:
			continue
		E[v] += (E[nv] + 1) * (1 / n)
	for vv in range(v)[::-1]:
		E[vv] = 0
		n = len(G[vv])
		for nv in G[vv]:
			E[vv] += (E[nv] + 1) * (1 / n)
	ans = min(ans, E[0])
print(ans)


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)


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

def E(stop):
	dp = [-1] * N
	dp[N - 1] = 0
	for i in range(N - 1)[::-1]:
		total = 0
		maxE = 0
		for to in edges[i]:
			total += dp[to]
			if maxE < dp[to]:
				maxE = dp[to]
		size = len(edges[i])
		if size > 1 and stop == i:
			size -= 1
			total -= maxE
		dp[i] = total / size + 1
	return dp[0]
ans = float('inf')
for s in range(N):
	ans = min(ans, E(s))
print(ans)


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)
	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
	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
	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(ev[0] - dx)
main()


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)
	dp = [0] * n
	for y in range(1, n)[::-1]:
		v_[y].sort()
		d = dp[y]
		for x in v_[y]:
			dp[x] += (d + 1) / len(v[x])
	ans = dp[0]
	lx = []
	for a in range(n - 1):
		lx.append(len(v[a]) - 1)
		if len(v[a]) == 1:
			lx[-1] += 1
			continue
		m = max([dp[b] for b in v[a]])
		for b in v[a]:
			if dp[b] == m:
				break
		for i in range(a + 1):
			dp[i] = 0
		for y in range(1, n)[::-1]:
			d = dp[y]
			for x in v_[y]:
				if x > a:
					break
				if (x, y) == (a, b):
					continue
				dp[x] += (d + 1) / lx[x]
		if 0 < dp[0] < ans:
			ans = dp[0]
		lx[-1] += 1
	print(ans)
	return
solve()


(n, m) = map(int, input().split())
edges_from = [[] 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
for node in range(n - 2, -1, -1):
	routes = edges_from[node]
	num_of_routes = len(routes)
	for next_node in routes:
		dist = E_dist_to_goal[next_node] + 1
		E_dist_to_goal[node] += dist / num_of_routes

def recalculate_dist(node, E_dist_to_goal):
	recal_E_dist = [0] * (node + 1)
	routes = edges_from[node]
	num_of_routes = len(routes)
	if num_of_routes == 1:
		return False
	heaviest_route = max((E_dist_to_goal[next_node] + 1 for next_node in routes))
	new_dist = E_dist_to_goal[node] - heaviest_route / num_of_routes
	new_dist *= num_of_routes / (num_of_routes - 1)
	recal_E_dist[node] = new_dist
	for v in range(node - 1, -1, -1):
		routes = edges_from[v]
		num_of_routes = len(routes)
		for nv in routes:
			if nv > node:
				dist = E_dist_to_goal[nv] + 1
			else:
				dist = recal_E_dist[nv] + 1
			recal_E_dist[v] += dist
		recal_E_dist[v] /= num_of_routes
	return recal_E_dist[0]
ans = [E_dist_to_goal[0]]
for i in range(n - 2):
	candidate = recalculate_dist(i, E_dist_to_goal)
	if candidate:
		ans.append(candidate)
print(min(ans))


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


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


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


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)


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)


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


import copy
(N, M) = map(int, input().split())
linked = [set() for i in range(N)]
for i in range(M):
	(s, t) = map(int, input().split())
	linked[s - 1].add(t - 1)

def dp(link):
	dp = [0] * N
	for i in range(N - 1):
		k = N - 2 - i
		size = len(link[k])
		if size == 0:
			continue
		p = 1 / size
		v = 0
		for t in link[k]:
			v = v + p * (dp[t] + 1)
		dp[k] = v
	return dp
all_dp = dp(linked)
ans = all_dp[0]
for i in range(N - 1):
	if len(linked[i]) < 2:
		continue
	cut = 0
	v = 0
	for t in linked[i]:
		if v < all_dp[t]:
			cut = t
			v = all_dp[t]
	linked[i].remove(cut)
	d = dp(linked)
	ans = min(ans, d[0])
	linked[i].add(cut)
print(ans)


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


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


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


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


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.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)
main()


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


import sys
(n, m) = map(int, input().split())
links = [set() for _ in range(n)]
counts = [0] * n
for line in sys.stdin:
	(s, t) = map(int, line.split())
	s -= 1
	t -= 1
	links[s].add(t)
	counts[s] += 1
not_omitted = [0.0] * n
exp_get = not_omitted.__getitem__
for j in range(n - 2, -1, -1):
	not_omitted[j] = sum(map(exp_get, links[j])) / counts[j] + 1
ans = 1000000.0
for i in range(n - 1):
	expected = [0.0] * n
	expected[i + 1:] = not_omitted[i + 1:]
	e_get = expected.__getitem__
	if counts[i] == 1:
		expected[i] = sum(map(e_get, links[i])) / counts[i] + 1
	else:
		exp = list(map(e_get, links[i]))
		expected[i] = (sum(exp) - max(exp)) / (counts[i] - 1) + 1
	for j in range(i - 1, -1, -1):
		expected[j] = sum(map(e_get, links[j])) / counts[j] + 1
	ans = min(ans, expected[0])
print(ans)


(n, m) = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]
for i in range(m):
	(a, b) = info[i]
	a -= 1
	b -= 1
	graph[a].append(b)

def dfs(pos):
	if dp[pos] != -1:
		return dp[pos]
	p = len(graph[pos])
	dp[pos] = 0
	if p == 0:
		return dp[pos]
	for next_pos in graph[pos]:
		dp[pos] += dfs(next_pos) / p
	dp[pos] += 1
	return dp[pos]
dp = [-1] * n
dfs(0)
ans = dp[0]

def dfs_1(pos):
	if dq[pos] != -1:
		return dq[pos]
	p = len(graph[pos])
	if pos == i:
		p -= 1
	dq[pos] = 0
	if p == 0:
		return dq[pos]
	for next_pos in graph[pos]:
		if pos == i and next_pos == ind:
			continue
		dq[pos] += dfs_1(next_pos) / p
	dq[pos] += 1
	return dq[pos]
for i in range(n):
	num = 0
	ind = 0
	if len(graph[i]) <= 1:
		continue
	for j in graph[i]:
		if num < dp[j]:
			num = dp[j]
			ind = j
	dq = [-1] * n
	dfs_1(0)
	ans = min(dq[0], ans)
print(ans)


import sys
import math
from collections import deque
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
INF = 10 ** 15
(n, m) = [int(item) for item in input().split()]
possibility = [0] * n
possibility[0] = 1.0

class DirectedGraph:

	def __init__(self, adj):
		self.n = len(adj)
		self.adj = adj
		self.is_asyclic = False
		self.max_path_len = None

	def topological_sort(self):
		indegree = [0] * self.n
		for (i, vs) in enumerate(self.adj):
			for dest in vs:
				indegree[dest] += 1
		zero_v = []
		for (v, indeg) in enumerate(indegree):
			if indeg == 0:
				zero_v.append(v)
		max_path_len = 1
		tp_sorted = []
		to_be_added = []
		while True:
			while zero_v:
				v = zero_v.pop()
				if len(self.adj[v]):
					p = possibility[v] / len(self.adj[v])
				tp_sorted.append(v)
				for dest in self.adj[v]:
					indegree[dest] -= 1
					possibility[dest] += p
					if indegree[dest] == 0:
						to_be_added.append(dest)
			if len(to_be_added) > 0:
				zero_v.extend(to_be_added)
				to_be_added = []
				max_path_len += 1
			else:
				break
		if len(tp_sorted) == self.n:
			self.is_asyclic = True
			self.max_path_len = max_path_len
			return tp_sorted
		else:
			self.is_asyclic = False
			return None
edge = [[] for _ in range(n)]
for i in range(m):
	(s, t) = [int(item) - 1 for item in input().split()]
	edge[s].append(t)
dag = DirectedGraph(edge)
tps = dag.topological_sort()
distance = [0] * n
mdist = []
for item in tps[::-1]:
	if item == n - 1:
		continue
	dist = 0.0
	max_dist = 0.0
	for dest in edge[item]:
		dist += distance[dest] + 1
		max_dist = max(max_dist, distance[dest] + 1)
	distance[item] = dist / len(edge[item])
	if len(edge[item]) > 1:
		diff = distance[item] - (dist - max_dist) / (len(edge[item]) - 1)
		mdist.append((diff * possibility[item], item))
mdist.sort(reverse=True)
if len(mdist) > 0:
	print(distance[0] - mdist[0][0])
else:
	print(distance[0])


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())
	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]
		E_dash = 0
		for nv in edges[v]:
			if nv == w:
				continue
			E_dash += E[nv]
		E_dash = 1 + E_dash / (len(edges[v]) - 1)
		dE = E_dash - E[v]
		ans = min(ans, E[0] + p[v] * dE)
	print(ans)
resolve()


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)


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)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, atan2, degrees
from operator import mul
from functools import reduce
sys.setrecursionlimit(10 ** 8)
INF = float('inf')

def LI():
	return list(map(int, sys.stdin.readline().split()))

def I():
	return int(sys.stdin.readline())

def LS():
	return sys.stdin.readline().split()

def S():
	return sys.stdin.readline().strip()

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

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
(n, m) = LI()
G = [[] for _ in range(n)]
for _ in range(m):
	(s, t) = LI()
	G[s - 1] += [t - 1]
route_len = [0] * n
for u in range(n - 2, -1, -1):
	route_len[u] = sum([route_len[v] + 1 for v in G[u]]) / len(G[u])
prob = [0] * n
prob[0] = 1
for u in range(n - 1):
	for v in G[u]:
		prob[v] += prob[u] / len(G[u])
ans = route_len[0]
for u in range(n - 1):
	if len(G[u]) == 1:
		continue
	new_route_len = (sum([route_len[v] + 1 for v in G[u]]) - max([route_len[v] + 1 for v in G[u]])) / (len(G[u]) - 1)
	ans = min(ans, route_len[0] - prob[u] * (route_len[u] - new_route_len))
print(ans)


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


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


def main():
	(n, m) = map(int, input().split())
	st = [list(map(int, input().split())) for _ in range(m)]
	g = [[] for _ in range(n)]
	for (s, t) in st:
		s -= 1
		t -= 1
		g[s].append(t)
	deg = [len(x) for x in g]
	dp = [0] * n
	for u in range(n - 1)[::-1]:
		now = 0
		for v in g[u]:
			now += dp[v]
		now /= deg[u]
		now += 1
		dp[u] = now
	ans = dp[0]
	for u in range(n - 1):
		if deg[u] == 1:
			continue
		d = g[u][0]
		for v in g[u]:
			if dp[d] < dp[v]:
				d = v
		dp2 = [0] * n
		for x in range(n - 1)[::-1]:
			now = 0
			for y in g[x]:
				if x == u and y == d:
					continue
				now += dp2[y]
			if x == u:
				now /= deg[x] - 1
			else:
				now /= deg[x]
			now += 1
			dp2[x] = now
		ans = min(ans, dp2[0])
	print(ans)
main()


(N, M) = map(int, input().split())
lis = [[] for i in range(N)]
rlis = [[] for i in range(N)]
mlis = [0] * N
for i in range(M):
	(s, t) = map(int, input().split())
	s -= 1
	t -= 1
	lis[s].append(t)
	rlis[t].append(s)
odp = [0] * N
for i in range(N):
	i = N - 1 - i
	for j in lis[i]:
		odp[i] += (odp[j] + 1) / len(lis[i])
ans = odp[0]
for k in range(N):
	dp = [0] * N
	flag = True
	for i in range(N):
		i = N - 1 - i
		if i != k:
			if k < i:
				dp[i] = odp[i]
			else:
				for j in lis[i]:
					dp[i] += (dp[j] + 1) / len(lis[i])
		else:
			maxi = 0
			for j in lis[i]:
				maxi = max(maxi, dp[j])
				dp[i] += dp[j] + 1
			if len(lis[i]) > 1:
				dp[i] = (dp[i] - (maxi + 1)) / (len(lis[i]) - 1)
			else:
				flag = False
	if flag:
		ans = min(ans, dp[0])
print(ans)


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)


import sys
input = 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)


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.0
prob = np.zeros(n, dtype=np.float)
prob[0] = 1.0
for i in range(n - 1):
	prob[adj[i]] += prob[i] / deg[i]
decrease = 0.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())
ST = [list(map(int, input().split())) for _ in range(M)]
ST.sort()
Edge_out = [[] for _ in range(N + 1)]
Edge_in = [[] for _ in range(N + 1)]
for (s, t) in ST:
	Edge_out[s].append(t)
	Edge_in[t].append(s)
P_node = [0] * (N + 1)
P_edge = [0] * (N + 1)
P_node[1] = 1
for (v, edge_out) in enumerate(Edge_out[1:-1], 1):
	deg = len(edge_out)
	p = P_node[v] / deg
	P_edge[v] = p
	for u in edge_out:
		P_node[u] += p
E_node_out = [0] * (N + 1)
for v in range(N - 1, 0, -1):
	edge_out = Edge_out[v]
	su = 0
	for u in edge_out:
		su += E_node_out[u]
	su /= len(edge_out)
	su += 1
	E_node_out[v] = su
ans = 0
for (s, t) in ST:
	p_s = P_node[s]
	deg = len(Edge_out[s])
	if deg == 1:
		continue
	e = (E_node_out[s] - (1 + E_node_out[t]) / deg) * (deg / (deg - 1))
	a = p_s * (e - E_node_out[s])
	ans = min(ans, a)
print(ans + E_node_out[1])


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


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 = [0.0] * n
exp_get = expected.__getitem__
reducible = [0.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.0
probability = [0.0] * n
probability[0] = 1.0
rdc = 0.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
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):
		(s, t) = map(int, input().split())
		s -= 1
		t -= 1
		E[s].append(t)
	dp = [0] * n
	for v in range(n - 2, -1, -1):
		res = 0
		for nv in E[v]:
			res += dp[nv]
		dp[v] = 1 + res / len(E[v])
	ans = dp[0]
	for v in range(n - 1):
		if len(E[v]) == 1:
			continue
		u = max(*((dp[nv], nv) for nv in E[v]))[1]
		dp2 = [0] * n
		for x in range(n - 2, -1, -1):
			res = 0
			for nx in E[x]:
				if x == v and nx == u:
					continue
				res += dp2[nx]
			if v != x:
				dp2[x] = 1 + res / len(E[x])
			else:
				dp2[x] = 1 + res / (len(E[x]) - 1)
		ans = min(ans, dp2[0])
	print(ans)
resolve()


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


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)


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 = 1000000000000.0
for i in range(M):
	(s, t) = map(int, input().split())
	paths[s].append(t)
for i in range(N):
	solve(i)
print(ans)


from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
mod = 10 ** 9 + 7
eps = 10 ** (-7)

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_str():
	return list(sys.stdin.readline().split())
(N, M) = inpl()
if M == N - 1:
	for _ in range(M):
		(s, t) = inpl()
	print(M)
else:
	lines = defaultdict(set)
	LL = [0] * N
	for _ in range(M):
		(s, t) = inpl()
		s -= 1
		t -= 1
		lines[s].add(t)
		LL[s] += 1

	def dfs(s):
		global MEMO
		if MEMO[s] != -1:
			return MEMO[s]
		else:
			tmp = 0
			for t in lines[s]:
				if MEMO[t] != -1:
					tmp += MEMO[t] + 1
				else:
					tmp += dfs(t) + 1
			MEMO[s] = tmp / LL[s]
			return MEMO[s]
	MEMO = [-1] * N
	MEMO[-1] = 0
	dfs(0)
	koho = [-1] * N
	for s in range(N):
		x = -1
		for t in lines[s]:
			if x < MEMO[t]:
				x = MEMO[t]
				koho[s] = t
	ans = 10 ** 10
	for s in range(N - 1):
		t = koho[s]
		if LL[s] == 1 or t == -1:
			continue
		MEMO = [-1] * N
		MEMO[-1] = 0
		lines[s].remove(t)
		LL[s] -= 1
		ans = min(ans, dfs(0))
		lines[s].add(t)
		LL[s] += 1
	print(ans)


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


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)
out_edge = [[] for _ in range(N + 1)]
in_edge = [[] for _ in range(N + 1)]
for (s, t) in ST:
	out_edge[s].append(t)
	in_edge[t].append(s)
out_deg = [len(x) for x in out_edge]
achieve_prob = [0] * (N + 1)
achieve_prob[1] = 1.0
for n in range(2, N + 1):
	achieve_prob[n] = sum((achieve_prob[p] / out_deg[p] for p in in_edge[n]))
expected_from = [0] * (N + 1)
for n in range(N - 1, 0, -1):
	expected_from[n] = 1 + sum((expected_from[c] for c in out_edge[n])) / out_deg[n]
current_time = expected_from[1]
improve = 0
for n in range(1, N):
	if out_deg[n] == 1:
		continue
	x = expected_from[n]
	d = out_deg[n]
	y = (d * (x - 1) - max((expected_from[c] for c in out_edge[n]))) / (d - 1) + 1
	value = (x - y) * achieve_prob[n]
	if improve < value:
		improve = value
answer = current_time - improve
print(answer)


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)


def calc(N, adj, dp, ignore):
	(s, t) = ignore
	for i in range(N - 1, -1, -1):
		dp[i] = 0.0
		n = len(adj[i])
		if i == s:
			n -= 1
		for nxt in adj[i]:
			if i == s and nxt == t:
				continue
			dp[i] += (dp[nxt] + 1) / n
	return dp[0]

def main():
	(N, M) = map(int, input().split())
	adj = [set() for _ in range(N)]
	for _ in range(M):
		(s, t) = map(int, input().split())
		adj[s - 1].add(t - 1)
	dp1 = [0.0] * N
	ans = calc(N, adj, dp1, (-1, -1))
	dp2 = [0.0] * N
	for i in range(N - 1, -1, -1):
		if len(adj[i]) <= 1:
			continue
		j = i
		mx = -1
		for nxt in adj[i]:
			if dp1[nxt] > mx:
				j = nxt
				mx = dp1[nxt]
		tmp = calc(N, adj, dp2, (i, j))
		ans = min(ans, tmp)
	print(ans)
main()


def solve_f(n, g):
	e_base = [0.0] * (n + 1)
	p_base = [0.0] * (n + 1)
	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[1] = 1.0
	for i in range(1, n):
		for j in g[i]:
			p_base[j] += p_base[i] / len(g[i])
	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():
	(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) < 1e-06
	assert abs(solve_f(3, [[], [2], [3]]) - 2.0) < 1e-06

def __starting_point():
	test()
	main()
__starting_point()


((n, m), *d) = [list(map(int, s.split())) for s in open(0)]
d.sort()
for i in range(m):
	d[i] = [d[i][0] - 1, d[i][1] - 1]
l = [0] * n
for x in d:
	l[x[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
		if index == -1:
			break
	max_in_index = max(max_in_index, e[x[1]] + 1)
	e[x[0]] += e[x[1]] + 1
print(e[0] - max_reduce_e)


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


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
v = [[] for _ in range(N)]
for i in range(M):
	(s, t) = map(int, input().split())
	v[s - 1].append(t - 1)
dp = [0] * N
for i in range(N - 1, -1, -1):
	if len(v[i]) == 0:
		continue
	for j in v[i]:
		dp[i] += dp[j]
	dp[i] = 1 + dp[i] / len(v[i])
ret = dp[0]
for i in range(N - 1):
	if len(v[i]) <= 1:
		continue
	dp[i] = 0
	M = -1
	for j in v[i]:
		dp[i] += dp[j]
		M = max(M, dp[j])
	dp[i] = 1 + (dp[i] - M) / (len(v[i]) - 1)
	for j in range(i - 1, -1, -1):
		if len(v[j]) == 0:
			continue
		dp[j] = 0
		for k in v[j]:
			dp[j] += dp[k]
		dp[j] = 1 + dp[j] / len(v[j])
	ret = min(ret, dp[0])
print(ret)


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)


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


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


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)


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)


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


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


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


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


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)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

def main():
	(n, m) = map(int, input().split())
	g = [[] for i in range(n)]
	deg2 = [0] * n
	atode = []
	for i in range(m):
		(s, t) = map(int, input().split())
		g[s - 1].append(t - 1)
		deg2[s - 1] += 1
		atode.append((s - 1, t - 1))
	ee = [-1] * n

	def rec2(cur, s, t):
		if ee[cur] != -1:
			return ee[cur]
		res = 0
		cnt = 0
		for to in g[cur]:
			if cur == s and to == t:
				continue
			res += rec2(to, s, t) + 1
			cnt += 1
		if cnt:
			res /= cnt
		ee[cur] = res
		return ee[cur]
	rec2(0, -1, -1)
	ret = ee[0]
	use = [[-1, -1] for i in range(n)]
	for (s, t) in atode:
		if deg2[s] < 2:
			continue
		if use[s][1] < ee[t]:
			use[s][0] = t
			use[s][1] = ee[t]
	for (s, (t, cost)) in enumerate(use):
		if s == -1:
			continue
		ee = [-1] * n
		rec2(0, s, t)
		ret = min(ret, ee[0])
	print(ret)
main()


import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
	(n, m) = map(int, input().split())
	to = defaultdict(list)
	for _ in range(m):
		(s, t) = map(int, input().split())
		(s, t) = (s - 1, t - 1)
		to[s].append(t)
	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
	ans = ev[0]
	for nu in range(n - 1):
		if len(to[nu]) == 1:
			continue
		mx = 0
		mv = 0
		for nv in to[nu]:
			if ev[nv] > mx:
				mx = ev[nv]
				mv = nv
		for u in range(nu, -1, -1):
			s = 0
			for ku in to[u]:
				if (u, ku) == (nu, mv):
					continue
				s += ev[ku]
			od = len(to[u])
			if u == nu:
				od -= 1
			ev[u] = s / od + 1
		ans = min(ans, ev[0])
	print(ans)
main()


import sys
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().rstrip()
(n, m) = na()
g = []
for i in range(n):
	g.append([])
for i in range(m):
	(s, t) = na()
	g[s - 1].append(t - 1)
es = [0] * n
for i in range(n - 2, -1, -1):
	s = 0
	for e in g[i]:
		s += es[e]
	s = s / len(g[i]) + 1
	es[i] = s
cont = [0] * n
for i in range(n):
	ees = [0] * (i + 1)
	ees[-1] = 1.0
	for j in range(i - 1, -1, -1):
		t = 0
		for e in g[j]:
			if e <= i:
				t += ees[e]
		ees[j] = t / len(g[j])
	cont[i] = ees[0]
ans = es[0]
for i in range(n):
	if len(g[i]) == 1:
		continue
	s = 0
	for e in g[i]:
		s += es[e]
	minto = es[i]
	for e in g[i]:
		to = (s - es[e]) / (len(g[i]) - 1) + 1
		minto = min(minto, to)
	ans = min(ans, es[0] - (es[i] - minto) * cont[i])
print('{:.14f}\n'.format(ans))


(N, M) = map(int, input().split())
E = [set() for i in range(N)]
for i in range(M):
	(s, t) = map(int, input().split())
	(s, t) = (s - 1, t - 1)
	E[s].add(t)
Vs = [1000000.0] * N
Vs[-1] = 0
for i in reversed(range(N - 1)):
	js = E[i]
	v = 0
	for j in js:
		v += Vs[j]
	v = 1 + v / len(js)
	Vs[i] = v
r = Vs[0]
rs = [r]
Vs0 = Vs
for n in range(N - 1):
	Vs = [1000000.0] * N
	for i in range(n + 1, N):
		Vs[i] = Vs0[i]
	for i in reversed(range(n + 1)):
		js = E[i]
		if i == n:
			jmin = max(js, key=lambda j: Vs[j])
			js = js - {jmin}
		if len(js) == 0:
			break
		v = 0
		for j in js:
			v += Vs[j]
		v = 1 + v / len(js)
		Vs[i] = v
	r = Vs[0]
	rs.append(r)
r = min(rs)
print(r)


(N, M) = map(int, input().split())
l = [[] for i in range(N)]
for i in range(M):
	(s, t) = map(int, input().split())
	s -= 1
	t -= 1
	l[s].append(t)
dp = [0] * N
for i in range(N - 2, -1, -1):
	dp[i] = 0
	for j in l[i]:
		dp[i] += dp[j]
	dp[i] /= len(l[i])
	dp[i] += 1
ans = dp[0]
for s in range(N - 1):
	if len(l[s]) == 1:
		continue
	M = 0
	t = 0
	for j in l[s]:
		if M < dp[j]:
			M = dp[j]
			t = j
	dp_ = [0] * N
	for i in range(N - 2, -1, -1):
		dp_[i] = 0
		for j in l[i]:
			if i != s or j != t:
				dp_[i] += dp_[j]
		if i != s:
			dp_[i] /= len(l[i])
		else:
			dp_[i] /= len(l[i]) - 1
		dp_[i] += 1
	ans = min(ans, dp_[0])
print(ans)


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


def f_fork_in_the_road():
	(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)
	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_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())


(N, M) = list(map(int, input().split()))
e_list = [[] for i in range(N)]
for i in range(M):
	(s, t) = list(map(int, input().split()))
	(s, t) = (s - 1, t - 1)
	e_list[s].append(t)
DP = [0 for i in range(N)]
dp0_min = 10 ** 27
for x in range(N - 1):
	for i in range(N - 1):
		if i == x:
			if len(e_list[N - i - 2]) == 1:
				DP[N - i - 2] = DP[e_list[N - i - 2][0]] + 1
			else:
				max_room = -1
				max_path = 0
				for j in e_list[N - i - 2]:
					if max_path < DP[j]:
						max_room = j
						max_path = DP[j]
					DP[N - i - 2] += DP[j]
				DP[N - i - 2] -= DP[max_room]
				DP[N - i - 2] /= len(e_list[N - i - 2]) - 1
				DP[N - i - 2] += 1
		else:
			for j in e_list[N - i - 2]:
				DP[N - i - 2] += DP[j]
			DP[N - i - 2] /= len(e_list[N - i - 2])
			DP[N - i - 2] += 1
	dp0_min = min(dp0_min, DP[0])
	DP = [0 for i in range(N)]
print(dp0_min)


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


import sys
input = sys.stdin.readline

def main():
	(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)
	DP = [0] * n
	for v in reversed(range(n - 1)):
		tmp = 0
		for to in Edges[v]:
			tmp += DP[to]
		DP[v] = tmp / len(Edges[v]) + 1
	ans = DP[0]
	for v in range(n - 1):
		if len(Edges[v]) == 1:
			continue
		u = max(((DP[to], to) for to in Edges[v]))[1]
		DP2 = [0] * n
		for w in reversed(range(n - 1)):
			tmp = 0
			for to in Edges[w]:
				if w == v and to == u:
					continue
				tmp += DP2[to]
			if w == v:
				DP2[w] = tmp / (len(Edges[w]) - 1) + 1
			else:
				DP2[w] = tmp / len(Edges[w]) + 1
		ans = min(ans, DP2[0])
	print(ans)
main()


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
R = [tuple(map(int, input().split())) for i in range(M)]
E = [set() for i in range(N)]
for (x, y) in R:
	E[x - 1].add(y - 1)
DP = [M] * N
DP[N - 1] = 0
for i in range(N - 2, -1, -1):
	score = 0
	for x in E[i]:
		score += 1 + DP[x]
	DP[i] = score / len(E[i])
ANS = DP[0]
for i in range(N - 2):
	rem = -1
	remsc = 0
	for j in E[i]:
		if DP[j] > remsc:
			rem = j
			remsc = DP[j]
	if remsc == 0:
		continue
	E[i].remove(rem)
	NDP = [M] * N
	NDP[N - 1] = 0
	for l in range(N - 2, -1, -1):
		score = 0
		if len(E[l]) == 0:
			continue
		for x in E[l]:
			score += 1 + NDP[x]
		NDP[l] = score / len(E[l])
	ANS = min(ANS, NDP[0])
	E[i].add(rem)
print(ANS)


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)


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)