Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import deque

import sys
input = sys.stdin.buffer.readline

N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

dist = [10**10] * N
que = deque([(0, 0)])
while que:
    now, d = que.popleft()

    if dist[now] <= d:
        continue
    dist[now] = d

    for to in edges[now]:
        que.append((to, d + 1))

A = [i for i, d in enumerate(dist) if d % 2 == 0]
B = [i for i, d in enumerate(dist) if d % 2 == 1]

if len(A) > len(B):
    A, B = B, A

ans = [-1] * N

if len(A) <= N // 3:
    nums = set(range(1, N + 1))
    now = 3
    for i in A:
        ans[i] = now
        nums.remove(now)
        now += 3
    nums = list(nums)
    for i, n in zip(B):
        ans[i] = n
else:
    now = 0
    nums = set(range(1, N + 1))
    for i in A:
        if now + 1 > N:
            break
        ans[i] = now + 1
        nums.remove(now + 1)
        now += 3
    now = 0
    for i in B:
        if now + 2 > N:
            break
        ans[i] = now + 2
        nums.remove(now + 2)
        now += 3
    now = 3
    for i, a in enumerate(ans):
        if a == -1:
            ans[i] = now
            now += 3

print(*ans)

Fixed submission:
from collections import deque

import sys
input = sys.stdin.buffer.readline

N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

dist = [10**10] * N
que = deque([(0, 0)])
while que:
    now, d = que.popleft()

    if dist[now] <= d:
        continue
    dist[now] = d

    for to in edges[now]:
        que.append((to, d + 1))

A = [i for i, d in enumerate(dist) if d % 2 == 0]
B = [i for i, d in enumerate(dist) if d % 2 == 1]

if len(A) > len(B):
    A, B = B, A

ans = [-1] * N
nums = set(range(1, N + 1))

if len(A) <= N // 3:
    mul = 1
    for i in A:
        ans[i] = 3 * mul
        nums.remove(3 * mul)
        mul += 1
    nums = list(nums)
    for i, n in zip(B, nums):
        ans[i] = n
else:
    mul = 1
    for c, i in enumerate(A):
        if c * 3 + 1 > N:
            ans[i] = mul * 3
            mul += 1
        else:
            ans[i] = c * 3 + 1
    for c, i in enumerate(B):
        if c * 3 + 2 > N:
            ans[i] = mul * 3
            mul += 1
        else:
            ans[i] = c * 3 + 2

print(*ans)
Buggy python submission (verdict: Runtime Error):
# modなしの場合は，mod=1にする

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

N, A, B = map(int, input().split())
MOD = 10**9 + 7

def calc(k):
    ret = 1
    for i in range(k):
        ret = ret * (N - i) * pow(i + 1, -1, MOD) % MOD
    return ret

ans = pow(2, N, MOD) - 1 - calc(A) - calc(B)
print(ans % MOD)

Fixed submission:
# modなしの場合は，mod=1にする

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

N, A, B = map(int, input().split())
MOD = 10**9 + 7

def calc(k):
    ret = 1
    for i in range(k):
        ret = ret * (N - i) * pow(i + 1, MOD - 2, MOD) % MOD
    return ret

ans = pow(2, N, MOD) - 1 - calc(A) - calc(B)
print(ans % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

dp = [10**18] * (H + 1)
dp[0] = 0
for a, b in AB:
    for h in range(H + 1):
        r = min(H, h + a)
        if dp[r] > dp[h] + b:
            dp[r] = dp[h] + b
print(dp[H])


Fixed submission:
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

dp = [10**10] * (H + 1)
dp[H] = 0

for a, b in AB:
    for h in range(H + 1)[:: -1]:
        dp[h] = min(dp[h], dp[min(H, h + a)] + b)

print(dp[0])
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
N = H * W

chart = [input() for _ in range(H)]

def node(h, w):
    return h * W + w

minDist = [[10**10] * N for _ in range(N)]

for i in range(N):
    minDist[i][i] = 0

for h in range(H):
    for w in range(W):
        if chart[h][w] == '#':
            continue

        if h > 0 and chart[h - 1][w] == '.':
            minDist[node(h, w)][node(h - 1, w)] = 1
            minDist[node(h - 1, w)][node(h, w)] = 1
        if h < H - 1 and chart[h + 1][w] == '.':
            minDist[node(h, w)][node(h + 1, w)] = 1
            minDist[node(h + 1, w)][node(h, w)] = 1
        if w > 0 and chart[h][w - 1] == '.':
            minDist[node(h, w)][node(h, w - 1)] = 1
            minDist[node(h, w - 1)][node(h, w)] = 1
        if w < W - 1 and chart[h][w + 1] == '.':
            minDist[node(h, w)][node(h, w + 1)] = 1
            minDist[node(h, w + 1)][node(h, w)] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = minDist[i][k] + minDist[k][j]
            if minDist[i][j] > d:
                minDist[i][j] = d

ans = 0
for dists in minDist:
    for d in dists:
        if d < 10**10:
            ans = max(ans, d)

print(ans)

Fixed submission:
H, W = map(int, input().split())
N = H * W

chart = [input() for _ in range(H)]

def node(h, w):
    return h * W + w

minDist = [[10**10] * N for _ in range(N)]

for i in range(N):
    minDist[i][i] = 0

for h in range(H):
    for w in range(W):
        if chart[h][w] == '#':
            continue

        if h > 0 and chart[h - 1][w] == '.':
            minDist[node(h, w)][node(h - 1, w)] = 1
            minDist[node(h - 1, w)][node(h, w)] = 1
        if h < H - 1 and chart[h + 1][w] == '.':
            minDist[node(h, w)][node(h + 1, w)] = 1
            minDist[node(h + 1, w)][node(h, w)] = 1
        if w > 0 and chart[h][w - 1] == '.':
            minDist[node(h, w)][node(h, w - 1)] = 1
            minDist[node(h, w - 1)][node(h, w)] = 1
        if w < W - 1 and chart[h][w + 1] == '.':
            minDist[node(h, w)][node(h, w + 1)] = 1
            minDist[node(h, w + 1)][node(h, w)] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = minDist[i][k] + minDist[k][j]
            if minDist[i][j] > d:
                minDist[i][j] = d

ans = 0
for dists in minDist:
    for d in dists:
        if d < 10**10:
            ans = max(ans, d)

print(ans)
Buggy python submission (verdict: Runtime Error):
from math import sin

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

def dist(x, y, u, v):
    return ((x - u)**2 + (y - v)**2)**0.5

ans = 10**10

for i in range(N):
    for j in range(i + 1, N):
        # 対辺
        xi, yi = XY[i]
        xj, yj = XY[j]
        cx = (xi + xj) / 2
        cy = (yi + yj) / 2
        d = 0
        for x, y in XY:
            d = max(d, dist(x, y, cx, cy))
        ans = min(ans, d)

        for k in range(j + 1, N):
            xi, yi = XY[i]
            xj, yj = XY[j]
            xk, yk = XY[k]
            c = dist(xi, yi, xj, yj)
            a = dist(xj, yj, xk, yk)
            b = dist(xk, yk, xi, yi)

            # 外心
            S = a**2 * (b**2 + c**2 - a**2) + b**2 * (c**2 + a**2 - b**2) + c**2 * (a**2 + b**2 - c**2)
            cx = a**2 * (b**2 + c**2 - a**2) * xi + b**2 * (c**2 + a**2 - b**2) * xj + c**2 * (a**2 + b**2 - c**2) * xk
            cy = a**2 * (b**2 + c**2 - a**2) * yi + b**2 * (c**2 + a**2 - b**2) * yj + c**2 * (a**2 + b**2 - c**2) * yk
            cx /= S
            cy /= S
            d = 0
            for x, y in XY:
                d = max(d, dist(x, y, cx, cy))
            ans = min(ans, d)

print(ans)


Fixed submission:
from math import sin

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

def dist(x, y, u, v):
    return ((x - u)**2 + (y - v)**2)**0.5

ans = 10**10

for i in range(N):
    for j in range(i + 1, N):
        # 対辺
        xi, yi = XY[i]
        xj, yj = XY[j]
        cx = (xi + xj) / 2
        cy = (yi + yj) / 2
        d = 0
        for x, y in XY:
            d = max(d, dist(x, y, cx, cy))
        ans = min(ans, d)

        for k in range(j + 1, N):
            xi, yi = XY[i]
            xj, yj = XY[j]
            xk, yk = XY[k]
            c = dist(xi, yi, xj, yj)
            a = dist(xj, yj, xk, yk)
            b = dist(xk, yk, xi, yi)

            # 外心
            S = a**2 * (b**2 + c**2 - a**2) + b**2 * (c**2 + a**2 - b**2) + c**2 * (a**2 + b**2 - c**2)
            if S == 0:
                continue
            cx = a**2 * (b**2 + c**2 - a**2) * xi + b**2 * (c**2 + a**2 - b**2) * xj + c**2 * (a**2 + b**2 - c**2) * xk
            cy = a**2 * (b**2 + c**2 - a**2) * yi + b**2 * (c**2 + a**2 - b**2) * yj + c**2 * (a**2 + b**2 - c**2) * yk
            cx /= S
            cy /= S
            d = 0
            for x, y in XY:
                d = max(d, dist(x, y, cx, cy))
            ans = min(ans, d)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
A, B, K = map(int, input().split())

for _ in range(K):
    if A > 0:
        A -= 1
    elif B > 0:
        B -= 1
    else:
        continue
print(A, B)


Fixed submission:
A, B, K = map(int, input().split())

C = max(0, A - K)
K -= A - C
print(C, max(0, B - K))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
W = N - V

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    D = deque([d for d in D if d > 0])
    cnt = 0

    while D:
        cnt += 1
        E = []
        for _ in range(min(W, len(D))):
            E.append(D.pop())
        for e in E:
            e -= 1
            if e > 0:
                D.append(e)

    return cnt <= M

ok = -1
ng = N
while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ng)

Fixed submission:
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
W = N - V

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    cnt = -(-(sum(D) - W) // W) + 1

    return max(max(D), cnt) <= M

ok = -1
ng = N
while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ng)
Buggy python submission (verdict: Runtime Error):
from collections import Counter, deque

N, K = map(int, input().split())
A = list(map(int, input().split()))
INF = 10**18

cnt = Counter()
cnt[0] = 1
que = deque([-INF] * (K - 1) + [0])
sumR = 0
ans = 0
for right, a in enumerate(A, start=1):
    cnt[que.popleft()] -= 1
    sumR = (a + sumR) % K
    D = (sumR - right) % K
    ans += cnt[D]
    cnt[D] += 1
    que.append(D)
print(ans)


Fixed submission:
from collections import defaultdict, deque

N, K = map(int, input().split())
A = list(map(int, input().split()))

cumA = [0] * (N + 1)
for i in range(1, N + 1):
    cumA[i] = cumA[i - 1] + A[i - 1]

cnt = defaultdict(int)
que = deque([])
ans = 0

for i, c in enumerate(cumA):
    while que and que[0][0] <= i - K:
        cnt[que.popleft()[1]] -= 1
    diff = (i - c) % K
    ans += cnt[diff]
    cnt[diff] += 1
    que.append((i, diff))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
M = int(input())
now = 0
ans = 0

for _ in range(M):
    d, c = map(int, input().split())
    for _ in range(c):
        now += d
        ans += 1
        if now >= 10:
            now = now // 10 + now % 10
            ans += 1

print(ans - 1)

Fixed submission:
M = int(input())
DC = [tuple(map(int, input().split())) for _ in range(M)]
ans = 0
s = 0

for d, c in DC:
    s += d * c
    ans += c

ans += (s - 1) // 9 - 1
print(ans)
Buggy python submission (verdict: Runtime Error):
from itertools import permutations

N = int(input())

def length(x, y, u, v):
    return ((x - u)**2 + (y - v)**2)**0.5

XY = [tuple(map(int, input().split())) for _ in range(N)]
ans = 0

for x in permutations(range(N)):
    for fr, to in zip(x, x[1:]):
        ans += length(*XY[fr], *XY[to])

for i in range(1, N + 1):
    ans /= i

print(ans)

Fixed submission:
from itertools import permutations

N = int(input())

def length(x, y, u, v):
    return ((x - u)**2 + (y - v)**2)**0.5

XY = [tuple(map(int, input().split())) for _ in range(N)]
ans = 0

for x, y in XY:
    for u, v in XY:
        ans += length(x, y, u, v)

print(ans / N)

Buggy python submission (verdict: Runtime Error):
from itertools import permutations

N = int(input())

def length(x, y, u, v):
    return ((x - u)**2 + (y - v)**2)**0.5

XY = [tuple(map(int, input().split())) for _ in range(N)]
ans = 0

for x in permutations(range(N)):
    for fr, to in zip(x, x[1:]):
        ans += length(*XY[fr], *XY[to])

for i in range(1, N + 1):
    ans /= i

print(ans)

Fixed submission:
from itertools import permutations

N = int(input())

def length(x, y, u, v):
    return ((x - u)**2 + (y - v)**2)**0.5

XY = [tuple(map(int, input().split())) for _ in range(N)]
ans = 0

for x, y in XY:
    for u, v in XY:
        ans += length(x, y, u, v)

print(ans / N)
Buggy python submission (verdict: Runtime Error):
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

    def f(self, p, q):
        return self.fact[p + q] * self.factInv[p] * self.factInv[q] % MOD


X, Y = map(int, input().split())
MOD = 10**9 + 7

if (X + Y) % 3 != 0:
    print(0)
    exit()

time = (X + Y) // 3
ans = 0
comb = Combination(time + 10)

x = (2 * X - Y) // 3
y = time - x

print(comb.f(x, y) % MOD)


Fixed submission:
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

    def f(self, p, q):
        return self.fact[p + q] * self.factInv[p] * self.factInv[q] % MOD


X, Y = map(int, input().split())
MOD = 10**9 + 7

if (X + Y) % 3 != 0:
    print(0)
    exit()

time = (X + Y) // 3
ans = 0
comb = Combination(time + 10)

for y in range(time + 1):
    x = time - y

    if X == x * 2 + y and Y == y * 2 + x:
        ans += comb.f(x, y)
        ans %= MOD

print(ans % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
N, T = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()
INF = float('inf')

dp = [-INF] * (T + 1)
dp[0] = 0

for a, b in AB:
    for t in range(T)[:: -1]:
        dp[min(T, t + a)] = max(dp[min(T, t + a)], dp[t] + b)

print(max(dp))

Fixed submission:
N, T = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()
INF = float('inf')

dp = [-INF] * (T + 1)
dp[0] = 0

for a, b in AB:
    newDp = dp[::]
    for t, d in enumerate(dp[:T]):
        newDp[min(T, t + a)] = max(newDp[min(T, t + a)], d + b)
    dp = newDp

print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
INF = float('inf')

class MinSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in rawData(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = min(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, M = map(int, input().split())

LRC = []
for _ in range(M):
    L, R, C = map(int, input().split())
    L -= 1
    LRC.append((L, R, C))
LRC.sort()

tree = MinSegTree(N)
tree.update(0, 0)
for l, r, c in LRC:
    newDist = tree.query(l, r) + c
    oldDist = tree.query(r - 1, r)
    if newDist < oldDist:
        tree.update(r - 1, newDist)

ans = tree.query(N - 1, N)
print(-1 if ans == INF else ans)

Fixed submission:
INF = float('inf')

class MinSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in rawData(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = min(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, M = map(int, input().split())

LRC = []
for _ in range(M):
    L, R, C = map(int, input().split())
    L -= 1
    LRC.append((L, R, C))
LRC.sort()

tree = MinSegTree(N)
tree.update(0, 0)
for l, r, c in LRC:
    newDist = tree.query(l, r) + c
    oldDist = tree.query(r - 1, r)
    if newDist < oldDist:
        tree.update(r - 1, newDist)

ans = tree.query(N - 1, N)
print(-1 if ans == INF else ans)
Buggy python submission (verdict: Time Limit Exceeded):
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
        mxI = 0
        for to in edges[i]:
            total += dp[to]
            if mxI < dp[to]:
                mxI = dp[to]
        size = len(edges[i])
        if size > 1 and stop == i:
            size -= 1
            total -= mxI
        dp[i] = total / size + 1
    return dp[0]

ans = float('inf')
for s in range(N):
    ans = min(ans, E(s))

print(ans)


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