Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)
M = int(input())
AB = tuple(tuple(map(int, input().split())) for _ in range(M))


parent = [-1] * (N + 1)
node = [1]
while node:
    s = node.pop()
    for t in edge[s]:
        if t == parent[s]:
            continue
        parent[t] = s
        node.append(t)

pair = [-1] * M
for i, (a, b) in enumerate(AB):
    pa = set()
    pb = set()
    while a != 1:
        pa.add(a - 1)
        a = parent[a]
    while b != 1:
        pb.add(b - 1)
        b = parent[b]
    pair[i] = pa ^ pb

ans = pow(2, N - 1)

whole = set(range(1, N))
for bit in range(1, 1 << M):
    popcnt = 0
    inter = set()
    for i in range(M):
        if (bit >> i) & 1:
            popcnt += 1
            inter |= pair[i]
    x = N - len(inter) - 1
    if popcnt % 2 == 1:
        ans -= 2 ** x
    else:
        ans += 2 ** x

print(ans)

Fixed submission:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)
M = int(input())
AB = tuple(tuple(map(int, input().split())) for _ in range(M))


parent = [-1] * (N + 1)
node = [1]
while node:
    s = node.pop()
    for t in edge[s]:
        if t == parent[s]:
            continue
        parent[t] = s
        node.append(t)

pair = [-1] * M
for i, (a, b) in enumerate(AB):
    pa = set()
    pb = set()
    while a != 1:
        pa.add(a - 1)
        a = parent[a]
    while b != 1:
        pb.add(b - 1)
        b = parent[b]
    pair[i] = pa ^ pb

ans = pow(2, N - 1)

whole = set(range(1, N))
for bit in range(1, 1 << M):
    popcnt = 0
    inter = set()
    for i in range(M):
        if (bit >> i) & 1:
            popcnt += 1
            inter |= pair[i]
    x = N - len(inter) - 1
    if popcnt % 2 == 1:
        ans -= 2 ** x
    else:
        ans += 2 ** x

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10**9+7


def binomial_coefficient(n, r, mod=10**9+7):
    """
    二項係数nCr, (n,r)をmodで除したあまりを返す
    """
    res = 1
    div = 1
    r = min(r, n - r)
    for i in range(r):
        res *= (n - i) % mod
        div *= (i + 1) % mod
    res *= pow(div, mod - 2, mod)
    return res % mod


ans = 0
for i in range(n - k + 1):
    f = a[-(i + 1)] - a[i]
    cnt = binomial_coefficient(n - i - 1, k - 1)
    ans += f * cnt
    ans %= mod

print(ans % mod)


Fixed submission:
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10**9+7

fac = [i for i in range(N + 1)]
for i in range(2, N + 1):
    fac[i] *= fac[i - 1]
    fac[i] %= mod
fac[0] = 1

fk = pow(fac[K - 1], mod-2, mod)

ans = 0
for i in range(N - K + 1):
    f = a[-(i + 1)] - a[i]
    nCr = fac[N - i - 1]*pow(fac[N-K-i], mod-2, mod)*fk % mod
    ans += f * nCr
    ans %= mod

print(ans % mod)
Buggy python submission (verdict: Runtime Error):
def abc151_b():
    N, K, M = map(int, input().split())
    A = sum(list(map(int, input().split())))
    need = max(0, N * M - A)
    ans = need if need <= K else - 1
    print(ans)

abc151_b()

Fixed submission:
N = int(input())
s = input()

ans = 0
for x, y, z in zip(s[:-2], s[1:-1], s[2:]):
    if x + y + z == "ABC":
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np
N, M = map(int, input().split())
A = tuple(map(int, input().split()))


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


A = np.unique(A)
for i, a in enumerate(A):
    if i == 0:
        g = a
        lcm = a
    g = gcd(g, a)
    lcm *= a // g

ans = M / lcm + 0.5
ans = int(ans)
print(ans)


Fixed submission:
def GCD(x, y):
    if y == 0:
        return x
    return GCD(y, x % y)


N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(set(A))

check = set()
for a in A:
    cnt = 0
    while a % 2 == 0:
        cnt += 1
        a //= 2
    check.add(cnt)

if len(check) > 1:
    print(0)
    exit()

LCM = 1
for a in A:
    gcd = GCD(LCM, a // 2)
    LCM = LCM * (a // 2) // gcd

ans = (M - LCM) // (2 * LCM) + 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

bit = [0] * 60
for a in A:
    i = 0
    while a > 0:
        bit[i] += a & 1
        i += 1
        a >>= 1

ans = 0
for i, x in enumerate(bit):
    x = x*(n-x)
    for _ in range(i):
        x *= 2
        x %= mod
    ans += x
    ans %= mod
print(ans)


Fixed submission:
n = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

bit = [0] * 60
for a in A:
    i = 0
    while a > 0:
        bit[i] += a & 1
        i += 1
        a >>= 1

ans = 0
for i, x in enumerate(bit):
    x = x*(n-x)
    for _ in range(i):
        x *= 2
        x %= mod
    ans += x
    ans %= mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
mod = 10**9+7

ans = 0
one = np.zeros(60, dtype=int)

for i in range(n):
    b = bin(a[i])[2:].zfill(60)

    for j in range(60):
        if b[j] == "1":
            ans += pow(2, 60-j-1, mod)*(i-one[j])
        else:
            ans += pow(2, 60-j-1, mod) * one[j]
        ans %= mod

    one += np.array(list(map(int, list(b))))

print(ans)


Fixed submission:
n = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

bit = [0] * 60
for a in A:
    i = 0
    while a > 0:
        bit[i] += a & 1
        i += 1
        a >>= 1

ans = 0
for i, x in enumerate(bit):
    x = x*(n-x)
    for _ in range(i):
        x *= 2
        x %= mod
    ans += x
    ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
S = input()

ans = 0
for i in range(1000):
    pin = str(i).zfill(3)

    ind = 0
    for s in S:
        if pin[ind] == s:
            ind += 1
        if ind >= 3:
            ans += 1
            break

print(ans)


Fixed submission:
from collections import defaultdict
n = int(input())
S = input()

d = defaultdict(list)
for i, s in enumerate(S):
    d[s].append(i)

ans = 0
for p in range(1000):
    p1, p2, p3 = str(p).zfill(3)

    i0 = -1
    for i in d[p1]:
        if i > i0:
            i1 = i
            break
    else:
        continue

    for i in d[p2]:
        if i > i1:
            i2 = i
            break
    else:
        continue

    for i in d[p3]:
        if i > i2:
            ans += 1
            break


print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()

seen = [False] * 10

ans = 0
for i in range(n - 2):
    if seen[int(s[i])]:
        continue

    tmp = set()
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            tmp.add(s[j] + s[k])
    ans += len(tmp)
    seen[int(s[i])] = True

print(ans)


Fixed submission:
from collections import defaultdict
n = int(input())
S = input()

d = defaultdict(list)
for i, s in enumerate(S):
    d[s].append(i)

ans = 0
for p in range(1000):
    p1, p2, p3 = str(p).zfill(3)

    i0 = -1
    for i in d[p1]:
        if i > i0:
            i1 = i
            break
    else:
        continue

    for i in d[p2]:
        if i > i1:
            i2 = i
            break
    else:
        continue

    for i in d[p3]:
        if i > i2:
            ans += 1
            break


print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()

seen = [False] * 10

ans = 0
for i in range(n - 2):
    if seen[int(s[i])]:
        continue

    tmp = set()
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            tmp.add(s[j] + s[k])
    ans += len(tmp)
    seen[int(s[i])] = True

print(ans)


Fixed submission:
from collections import defaultdict
n = int(input())
S = input()

d = defaultdict(list)
for i, s in enumerate(S):
    d[s].append(i)

ans = 0
for p in range(1000):
    p1, p2, p3 = str(p).zfill(3)

    i0 = -1
    for i in d[p1]:
        if i > i0:
            i1 = i
            break
    else:
        continue

    for i in d[p2]:
        if i > i1:
            i2 = i
            break
    else:
        continue

    for i in d[p3]:
        if i > i2:
            ans += 1
            break


print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np


def calc(mae, now):
    if mae == 3:
        if now == 0:
            return 3
        elif now == 1:
            return 2
        elif now == 2:
            return 1
    elif mae == 2:
        if now == 0:
            return 2
        elif now == 1:
            return 1
    elif mae == 1:
        if now == 0:
            return 1


if __name__ == "__main__":
    n = int(input())
    a = np.array(list(map(int, input().split())))
    mod = 10**9+7

    memo = np.zeros(n+1, dtype=int)
    memo[0] = 3
    ans = 1
    for i in a:
        mae = memo[i]
        now = memo[i+1]
        ans *= calc(mae, now)
        ans %= mod

        memo[i+1] += 1

    print(ans)


Fixed submission:
import numpy as np


if __name__ == "__main__":
    n = int(input())
    a = np.array(list(map(int, input().split())))
    mod = 10**9+7

    memo = np.zeros(n+10, dtype=int)
    memo[0] = 3
    ans = 1
    for i in a:
        mae = memo[i]
        now = memo[i+1]
        ans *= mae-now
        ans %= mod

        memo[i+1] += 1

    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
edge = [[] for _ in range(N + 1)]
E = [-1] * (N - 1)
for i in range(N - 1):
    a, b = map(int, input().split())
    edge[a].append((b, i))
    edge[b].append((a, i))

cmax = max(len(e) for e in edge)
cand = set(i for i in range(cmax))
seenV = [-1] * (N + 1)
seenE = [-1] * N
node = [(1, cand)]
seenV[1] = 1
while node:
    s, color = node.pop()
    x = 0
    for t, i in edge[s]:
        if seenV[t] != -1:
            continue
        if seenE[i] != -1:
            continue
        seenV[t] = 1
        c = list(color)[x]
        seenE[i] = c
        node.append((t, cand - {c}))
        x += 1

print(cmax)
for i in range(N - 1):
    print(seenE[i]+1)

Fixed submission:
from collections import deque
n = int(input())
tree = [[] for _ in range(n)]
edge = []

for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    edge.append((a, b))


# serch max number of color
for i in range(n):
    if i == 0:
        color = len(tree[i])
    else:
        color = max(color, len(tree[i])+1)

upper = [0 for _ in range(n)]

for i in range(n):
    if not tree[i]:
        continue

    top = upper[i]
    tmp = tree[i].copy()
    cnt = 1
    while tmp:
        if cnt == top:
            cnt += 1
        upper[tmp.pop()] = cnt
        cnt += 1

ans = []
for x, y in edge:
    ans.append(upper[y])
print(color)
print(*ans, sep="\n")

Buggy python submission (verdict: Runtime Error):
from collections import deque
n = int(input())
tree = [[] for _ in range(n)]
edge = []

for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    edge.append((a, b))


# serch max number of color
for i in range(n):
    if i == 0:
        color = len(tree[i])
    else:
        color = max(color, len(tree[i])+1)

upper = [0 for _ in range(n)]

for i in range(n):
    if not tree[i]:
        continue

    top = upper[i]
    tmp = tree[i].copy()
    cnt = 1
    while tmp:
        if cnt == top:
            cnt += 1
        upper[tmp.pop()] = cnt
        cnt += 1

ans = []
for x, y in edge:
    ans.append(upper[y])
print(color)
print(*ans, sep="\n")


Fixed submission:
from collections import deque
n = int(input())
tree = [[] for _ in range(n)]
edge = []

for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    edge.append((a, b))


# serch max number of color
for i in range(n):
    if i == 0:
        color = len(tree[i])
    else:
        color = max(color, len(tree[i])+1)

upper = [0 for _ in range(n)]

for i in range(n):
    if not tree[i]:
        continue

    top = upper[i]
    tmp = tree[i].copy()
    cnt = 1
    while tmp:
        if cnt == top:
            cnt += 1
        upper[tmp.pop()] = cnt
        cnt += 1

ans = []
for x, y in edge:
    ans.append(upper[y])
print(color)
print(*ans, sep="\n")
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
S = input()
S = S[::-1]

dp = [-1] * (N + 1)
dp[0] = 0

pos = 0
while pos < N:

    p = pos
    update = False

    for i in range(1, M + 1):
        if p + i > N:
            break
        if S[p + i] == "1":
            continue
        update = True
        pos = p + i
        dp[pos] = dp[p] + 1

    if not update:
        break

if dp[N] == -1:
    print(-1)
    exit()

dp = dp[::-1]
num = dp[0]
ans = []
pos = 0

while num > 0:
    for i in range(1, M + 1):
        if dp[pos + i] == num - 1:
            num -= 1
            pos += i
            ans.append(str(i))

ans = " ".join(ans)
print(ans)


Fixed submission:
N, M = map(int, input().split())
S = input()

dp = [-1] * (N + M + 1)
dp[N] = 0
pos = N

while pos > 0:
    dist = dp[pos]
    tmp = pos

    for i in range(1, M + 1):
        if pos - i < 0:
            break
        if S[pos - i] == "0":
            dp[pos - i] = dist + 1
            tmp = pos - i
    if pos == tmp:
        break
    pos = tmp

if dp[0] == -1:
    print(-1)
    exit()

ans = []
cnt = dp[0]
pos = 0
while cnt > 0:
    for i in range(1, M + 1):
        if dp[pos + i] + 1 == cnt:
            ans.append(i)
            pos += i
            cnt -= 1
            break

print(*ans, sep=" ")
Buggy python submission (verdict: Time Limit Exceeded):
def knight(x, y):
    mod = 10 ** 9 + 7
    x, y = min(x, y), max(x, y)

    if (x + y) % 3 != 0:
        return 0
    if y > 2 * x:
        return 0

    move = (x + y) // 3
    right = 2 * move - y
    up = move-right

    ans = 1
    for i in range(1, move + 1):
        ans *= i
        ans %= mod
    for i in range(1, right + 1):
        ans *= pow(i, mod - 2, mod)
        ans %= mod
    for i in range(1, up + 1):
        ans *= pow(i, mod - 2, mod)
        ans %= mod
    return ans


if __name__ == "__main__":
    x, y = map(int, input().split())
    ans = knight(x, y)
    print(ans)


Fixed submission:
def knight(x, y):
    mod = 10 ** 9 + 7
    x, y = min(x, y), max(x, y)

    if (x + y) % 3 != 0:
        return 0
    if y > 2 * x:
        return 0

    move = (x + y) // 3
    right = 2 * move - y
    up = move-right

    ans = 1
    for i in range(up):
        ans *= (move - i)
        ans *= pow(i + 1, mod - 2, mod)
        ans %= mod

    return ans


if __name__ == "__main__":
    x, y = map(int, input().split())
    ans = knight(x, y)
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

AB.sort(reverse=True)
dp = [0] * (T + 1)

for a, b in AB:
    for t in range(T):
        x = dp[t+a]+b if t+a < T else b
        dp[t] = max(dp[t], x)

ans = dp[0]
print(ans)


Fixed submission:
import numpy as np
N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]


def knapsack(ab):
    dp = np.zeros(T, dtype=np.int64)
    res = [dp]
    for a, b in ab:
        newDP = res[-1].copy()
        newDP[a:] = np.maximum(newDP[a:], newDP[:-a] + b)
        res.append(newDP)
    return res


dp1 = knapsack(AB)
dp2 = knapsack(AB[::-1])
dp2 = dp2[::-1]

ans = 0

for i in range(N):
    _, b = AB[i]
    l = dp1[i]
    r = dp2[i + 1][::-1]
    tmp = (l + r).max() + b
    ans = max(ans, tmp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
lrc = []
for _ in range(m):
    lrc.append(tuple(map(int, input().split())))
lrc.sort()

inf = 10**15
dp = [inf]*(n+1)
dp[1] = 0

for l, r, c in lrc:
    for i in range(r, l, -1):
        if dp[i] > dp[l] + c:
            dp[i] = dp[l] + c
        else:
            break

ans = -1 if dp[n] == inf else dp[n]
print(ans)


Fixed submission:
n, m = map(int, input().split())
lrc = []
for _ in range(m):
    lrc.append(tuple(map(int, input().split())))
lrc.sort()

inf = 10**15
dp = [inf]*(n+1)
dp[1] = 0

for l, r, c in lrc:
    for i in range(r, l, -1):
        if dp[i] > dp[l] + c:
            dp[i] = dp[l] + c
        else:
            break

ans = -1 if dp[n] == inf else dp[n]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
lrc = []
for _ in range(m):
    l, r, c = map(int, input().split())
    lrc.append((l, r, c))
lrc.sort()

inf = 10**18
dp = [inf]*(n+1)
dp[1] = 0

for l, r, c in lrc:
    for i in range(r, l, -1):
        if dp[i] > dp[l] + c:
            dp[i] = dp[l] + c
        else:
            break

ans = -1 if dp[n] == inf else dp[n]
print(ans)


Fixed submission:
n, m = map(int, input().split())
lrc = []
for _ in range(m):
    lrc.append(tuple(map(int, input().split())))
lrc.sort()

inf = 10**15
dp = [inf]*(n+1)
dp[1] = 0

for l, r, c in lrc:
    for i in range(r, l, -1):
        if dp[i] > dp[l] + c:
            dp[i] = dp[l] + c
        else:
            break

ans = -1 if dp[n] == inf else dp[n]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n, m = map(int, input().split())
lrc = []
for _ in range(m):
    l, r, c = map(int, input().split())
    lrc.append((r, l, c))
lrc.sort(reverse=True)

inf = 10**18
dp = np.ones(n+1, dtype=np.int32)*inf
dp[n] = 0

for r, l, c in lrc:

    for i in range(l, r):
        if dp[i] > dp[r] + c:
            dp[i] = dp[r] + c
        else:
            break

ans = -1 if dp[1] == inf else dp[1]
print(ans)


Fixed submission:
n, m = map(int, input().split())
lrc = []
for _ in range(m):
    lrc.append(tuple(map(int, input().split())))
lrc.sort()

inf = 10**15
dp = [inf]*(n+1)
dp[1] = 0

for l, r, c in lrc:
    for i in range(r, l, -1):
        if dp[i] > dp[l] + c:
            dp[i] = dp[l] + c
        else:
            break

ans = -1 if dp[n] == inf else dp[n]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)


def C(x):
    train = 0
    for a, f in zip(A, F):
        train += max(0, a - x // f)

    return train <= K


left = -1
right = 10 ** 12 + 1
while right > left + 1:
    mid = (right + left) // 2
    if C(mid):  # 食べきれる場合
        right = mid
    else:
        left = mid

ans = right
print(ans)


Fixed submission:
import numpy as np
N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
F = np.array(input().split(), dtype=np.int64)
A = np.sort(A)
F = np.sort(F)[::-1]


def C(x):
    train = np.maximum(0, A - x // F).sum()
    return train <= K


left = -1
right = 10 ** 12 + 1
while right > left + 1:
    mid = (right + left) // 2
    if C(mid):  # 食べきれる場合
        right = mid
    else:
        left = mid

ans = right
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))

a.sort()
f.sort(reverse=True)
cost = []
for i, j in zip(a, f):
    heapq.heappush(cost, (-i * j, -j))

cnt = 0
while True:
    tmp = heapq.heappop(cost)
    if cnt >= k:
        ans = -tmp[0]
        break
    if tmp[0] == 0:
        ans = 0
        break
    tmp = (tmp[0] - tmp[1], tmp[1])
    heapq.heappush(cost, tmp)

    cnt += 1

print(ans)


Fixed submission:
import numpy as np
N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
F = np.array(input().split(), dtype=np.int64)
A = np.sort(A)
F = np.sort(F)[::-1]


def C(x):
    train = np.maximum(0, A - x // F).sum()
    return train <= K


left = -1
right = 10 ** 12 + 1
while right > left + 1:
    mid = (right + left) // 2
    if C(mid):  # 食べきれる場合
        right = mid
    else:
        left = mid

ans = right
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque, defaultdict
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

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


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

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

print(ans)

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

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

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


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

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

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import bisect
n = int(input())
l = np.array([int(i) for i in input().split()])
l = np.sort(l)

ans = 0
for i in range(1, n - 1):
    m = l[:i]
    for j in range(i + 1, n):
        tmp = l[j] - l[i]
        cnt = bisect.bisect_right(m, tmp)
        ans += i-cnt
print(ans)


Fixed submission:
import bisect
n = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(n - 2):
    l = L[i]
    for j in range(i + 1, n - 1):
        ll = l + L[j]

        ind = bisect.bisect_left(L, ll)
        ans += ind - j - 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(n - 1, 1, -1):
    for j in range(i - 1, 0, -1):
        d = l[i] - l[j]
        cnt = bisect.bisect_right(l[:j], d)
        if j - cnt <= 0:
            break
        ans += j - cnt


print(ans)


Fixed submission:
import bisect
n = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(n - 2):
    l = L[i]
    for j in range(i + 1, n - 1):
        ll = l + L[j]

        ind = bisect.bisect_left(L, ll)
        ans += ind - j - 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
s=input()
s+="?"

tmp=[]
l=1
for i in range(n):
    if s[i]==s[i+1]:
        l+=1
    else:
        tmp.append(l)
        l=1

for _ in range(k):
    if len(tmp)==1:
        break
    elif len(tmp)==2:
        tmp=[tmp[0]+tmp[1]]
        continue
    tmp=[tmp[0]+tmp[1]+tmp[2]]+tmp[3:]

ans=sum(tmp)-len(tmp)
print(ans)

Fixed submission:
n,k=map(int,input().split())
s=input()
s+="?"

tmp=[]
l=1
for i in range(n):
    if s[i]==s[i+1]:
        l+=1
    else:
        tmp.append(l)
        l=1

RLs=max(1, len(tmp)-2*k)

ans=n-RLs
print(ans)