Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(1000000000)

n,u,v = map(int,input().split())
u -= 1
v -= 1
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

dist = [-1]*n
dist[v] = 0
prev = [-1]*n
def dfs(now):
    for nxt in G[now]:
        if dist[nxt] != -1: continue
        dist[nxt] = dist[now]+1
        prev[nxt] = now
        dfs(nxt)
dfs(v)

color = [0]*n
now = u
while now >= 0:
    color[now] = 1
    now = prev[now]

def dfs2(now,prev,dist,cnt):
    if dist == 0: return cnt
    if dist == -1: return cnt-1
    if G[now] == [prev]: return cnt+dist-1
    res = 0
    for nxt in G[now]:
        if nxt == prev: continue
        if color[nxt]: res = max(res,dfs2(nxt,now,dist-2,cnt+1))
        else: res = max(res,dfs2(nxt,now,dist,cnt+1))
    return res

print(dfs2(u,-1,dist[u]-dist[v],0))

Fixed submission:
n = int(input())

if n%2 != 0:
    ans = 0
else:
    ans = 0
    x = 5
    while n >= x:
        ans += n//(x*2)
        x *= 5

print(ans)
Buggy python submission (verdict: Runtime Error):
n,u,v = map(int,input().split())
u -= 1
v -= 1
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

dist = [-1]*n
dist[v] = 0
prev = [-1]*n
def dfs(now):
    for nxt in G[now]:
        if dist[nxt] != -1: continue
        dist[nxt] = dist[now]+1
        prev[nxt] = now
        dfs(nxt)
dfs(v)

color = [0]*n
now = u
while now >= 0:
    color[now] = 1
    now = prev[now]

def dfs2(now,prev,dist,cnt):
    if dist == 0: return cnt
    if dist == -1: return cnt-1
    if G[now] == [prev]: return cnt+dist-1
    res = 0
    for nxt in G[now]:
        if nxt == prev: continue
        if color[nxt]: res = max(res,dfs2(nxt,now,dist-2,cnt+1))
        else: res = max(res,dfs2(nxt,now,dist,cnt+1))
    return res

print(dfs2(u,-1,dist[u]-dist[v],0))

Fixed submission:
import sys
sys.setrecursionlimit(1000000000)

n,u,v = map(int,input().split())
u -= 1
v -= 1
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

distT = [-1]*n
distA = [-1]*n
distT[u] = 0
distA[v] = 0
def dfs(now,dist):
    for nxt in G[now]:
        if dist[nxt] != -1: continue
        dist[nxt] = dist[now]+1
        dfs(nxt,dist)
dfs(u,distT)
dfs(v,distA)

mx = 0
for i in range(n):
    if distT[i] < distA[i]:
        mx = max(mx, distA[i])
ans = mx-1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(i) for i in input().split()]
mod = 10**9+7
ans = 0
m = max(a)
x = 0
while m > 0:
    m >>= 1
    x += 1 
 
for i in range(x):
    cnt = 0
    for j in range(n):
        if a[j]>>i & 1 == 0: cnt += 1
    ans = (ans+pow(2,i,mod)*cnt%mod*(n-cnt)%mod)%mod
    
print(ans)

Fixed submission:
n = int(input())
a = [int(i) for i in input().split()]
ans = 0
mod = 10**9+7
for i in range(60):
    x = 0
    for j in range(n):
        if a[j] >> i & 1: x += 1 # i桁目が1である数の個数
    now = x*(n-x)%mod # 0と1の組み合わせの数(0 xor 1 = 1)
    for _ in range(i): now = now*2%mod # i桁目が1なら*2^i
    ans += now
    ans %= mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(i) for i in input().split()]
mod = 10**9+7
ans = 0
for i in range(60):
    cnt = 0
    for j in range(n):
        if a[j]>>i & 1 == 0: cnt += 1
    ans = (ans+pow(2,i,mod)*cnt%mod*(n-cnt)%mod)%mod
print(ans)

Fixed submission:
n = int(input())
a = [int(i) for i in input().split()]
ans = 0
mod = 10**9+7
for i in range(60):
    x = 0
    for j in range(n):
        if a[j] >> i & 1: x += 1 # i桁目が1である数の個数
    now = x*(n-x)%mod # 0と1の組み合わせの数(0 xor 1 = 1)
    for _ in range(i): now = now*2%mod # i桁目が1なら*2^i
    ans += now
    ans %= mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(i) for i in input().split()]
ans = 0
mod = 10**9+7
for i in range(60):
    x = 0
    for j in range(n):
        if a[j] >> i & 1: x += 1 # i桁目が1である数の個数
    now = x*(n-x)%mod # 0と1の組み合わせの数(0 xor 1 = 1)
    for _ in range(i): now = now*2%mod # i桁目が1なら*2^i
    ans += now
    ans %= mod
print(ans)

Fixed submission:
n = int(input())
a = [int(i) for i in input().split()]
ans = 0
mod = 10**9+7
for i in range(60):
    x = 0
    for j in range(n):
        if a[j] >> i & 1: x += 1 # i桁目が1である数の個数
    now = x*(n-x)%mod # 0と1の組み合わせの数(0 xor 1 = 1)
    for _ in range(i): now = now*2%mod # i桁目が1なら*2^i
    ans += now
    ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()
cnt = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            idx = S.find(str(k))
            if idx != -1:
                idx = S.find(str(j),idx+1)
                if idx != -1:
                    idx = S.find(str(i),idx+1)
                    if idx != -1:
                        cnt += 1

print(cnt)

Fixed submission:
m,d = map(int,input().split())
M,D = map(int,input().split())

if m != M:
    print(1)
else:
    print(0)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
ans = 0
for i in range(1000):
    pw = str(i).zfill(3)
    idx = 0
    for c in s:
        if c == pw[idx]: idx += 1
        if idx == 3:
            ans += 1
            break
print(ans)

Fixed submission:
N = int(input())
S = input()
cnt = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            idx = 0
            a = S.find(str(k),idx)
            if a != -1:
                idx = a
                b = S.find(str(j),idx+1)
                if b != -1:
                    idx = b
                    c = S.find(str(i),idx+1)
                    if c != -1:
                        cnt += 1

print(cnt)
Buggy python submission (verdict: Runtime Error):
n = int(input())
edge = [tuple(int(i) for i in input().split()) for i in range(n-1)]
to = [[] for _ in range(n+1)]
for e in edge:
    a,b = e
    to[a].append(b)
    to[b].append(a)
color = {}

def f(cn,pn,pc):
    c = 1
    for nn in to[cn]:
        if nn == pn: continue
        if c == pc: c += 1
        tmp = (cn,nn)
        color[(min(tmp),max(tmp))] = c
        f(nn,cn,c)
        c += 1

f(1,0,0)
print(max(color.values()))
for key in edge: print(color[key])

Fixed submission:
from sys import setrecursionlimit
setrecursionlimit(10**6)
n = int(input())
edge = [tuple(int(i) for i in input().split()) for i in range(n-1)]
to = [[] for _ in range(n+1)]
for e in edge:
    a,b = e
    to[a].append(b)
    to[b].append(a)
color = {}

def f(cn,pn,pc):
    c = 1
    for nn in to[cn]:
        if nn == pn: continue
        if c == pc: c += 1
        tmp = (cn,nn)
        color[(min(tmp),max(tmp))] = c
        f(nn,cn,c)
        c += 1

f(1,0,0)
print(max(color.values()))
for key in edge: print(color[key])
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

from math import factorial

x,y = map(int,input().split())
cnt = 0

for i in range(0,x//2+1):
    if 2*x-3*i == y:
        cnt += factorial(x-i)//(factorial(x-2*i)*factorial(i))
        break

print(cnt%(10**9+7))

Fixed submission:
x,y = map(int,input().split())
ans = 0
mod = 10**9+7

if (x+y)%3 == 0:
    m = (2*y-x)//3
    n = (2*x-y)//3
    if m >= 0 and n >= 0:
        fac = [1]*(m+n+1)
        for i in range(2,m+n+1): 
            fac[i] = fac[i-1]*i % mod
        ans = fac[m+n]*(pow(fac[m],mod-2,mod)*pow(fac[n],mod-2,mod)%mod)%mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

from math import factorial

x,y = map(int,input().split())
cnt = 0

for i in range(0,x//2+1):
    if (x-2*i)*2+i == y:
        cnt += factorial(x-i)//(factorial(x-2*i)*factorial(i))

print(cnt%(10**9+7))

Fixed submission:
x,y = map(int,input().split())
ans = 0
mod = 10**9+7

if (x+y)%3 == 0:
    m = (2*y-x)//3
    n = (2*x-y)//3
    if m >= 0 and n >= 0:
        fac = [1]*(m+n+1)
        for i in range(2,m+n+1): 
            fac[i] = fac[i-1]*i % mod
        ans = fac[m+n]*(pow(fac[m],mod-2,mod)*pow(fac[n],mod-2,mod)%mod)%mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

n = int(input())
a = []

for i in range(1,n+1):
    if n%i == 0:
        a.append(i+n//i-2)

print(min(a))

Fixed submission:
# -*- coding: utf-8 -*-
from math import sqrt

n = int(input())
a = []

for i in range(1,int(sqrt(n))//1+1):
    if n%i == 0:
        a.append(i+n//i-2)

print(min(a))
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
A = [int(i) for i in input().split()]
A.sort()
F = [int(i) for i in input().split()]
F.sort(reverse=True)

left = -1
right = 10**12
def f(x):
    cnt = 0
    for i in range(n): cnt += max(A[i]-x//F[i],0)
    return cnt <= k
    
while right - left > 1:
    mid = (left+right)//2
    if f(mid): right = mid
    else: left = mid
print(right)

Fixed submission:
n,k = map(int,input().split())
A = [int(i) for i in input().split()]
A.sort()
F = [int(i) for i in input().split()]
F.sort(reverse=True)

left = -1
right = 10**12
def f(x):
    cnt = 0
    for i in range(n): cnt += max(A[i]-x//F[i],0)
    return cnt <= k
    
while right - left > 1:
    mid = (left+right)//2
    if f(mid): right = mid
    else: left = mid
print(right)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = [int(i) for i in input().split()]
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        lp = j+1
        rp = n-1
        while lp < rp:
            mp = (lp+rp)//2
            if l[mp] < l[i] + l[j]:
                lp = mp+1
            else:
                rp = mp-1
        if l[lp] < l[i] + l[j]:
            ans += lp-j
        else:
            ans += lp-j-1
print(ans)

Fixed submission:
n = int(input())
l = [int(i) for i in input().split()]
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        lp = j+1
        rp = n-1
        while lp < rp:
            mp = (lp+rp)//2
            if l[mp] < l[i] + l[j]:
                lp = mp+1
            else:
                rp = mp-1
        if l[lp] < l[i] + l[j]:
            ans += lp-j
        else:
            ans += lp-j-1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = [int(i) for i in input().split()]
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if l[k] < l[i] + l[j]:
                ans += 1
            else:
                break

print(ans)


Fixed submission:
n = int(input())
l = [int(i) for i in input().split()]
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        lp = j+1
        rp = n-1
        while lp < rp:
            mp = (lp+rp)//2
            if l[mp] < l[i] + l[j]:
                lp = mp+1
            else:
                rp = mp-1
        if l[lp] < l[i] + l[j]:
            ans += lp-j
        else:
            ans += lp-j-1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

n = int(input())
l = list(map(int,input().split()))
cnt = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if l[i] < l[j] + l[k] and l[j] < l[k] + l[i] and l[k] < l[i] + l[j]:
                cnt += 1

print(cnt)



Fixed submission:
n = int(input())
l = [int(i) for i in input().split()]
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        lp = j+1
        rp = n-1
        while lp < rp:
            mp = (lp+rp)//2
            if l[mp] < l[i] + l[j]:
                lp = mp+1
            else:
                rp = mp-1
        if l[lp] < l[i] + l[j]:
            ans += lp-j
        else:
            ans += lp-j-1
print(ans)
Buggy python submission (verdict: Runtime Error):
from math import sqrt

a,b = map(int,input().split())
 
L = []
 
if a < b: a,b = b,a
while b!=0:
    r = a%b
    a,b = b,r
 
G = a
 
for i in range(2,int(sqrt(G))+1):
    if G%i==0:
        L.append(i)
        while G%i==0:
            G/=i

if G!=1:
    L.append(G)

print(len(L)+1) 

Fixed submission:

n = int(input())

if n%2==0:
    print(0.5)
else:
    print((n//2+1)/n)

Buggy python submission (verdict: Runtime Error):
from math import sqrt

a,b = map(int,input().split())

L = []

if a < b: a,b = b,a
while b!=0:
    r = a%b
    a,b = b,r

G = a

for i in range(2,G+1):
    for j in L:
        if i%j==0: 
            break
    else:
        if G%i==0: 
            L.append(i)

print(len(L)+1)   


Fixed submission:

n = int(input())

if n%2==0:
    print(0.5)
else:
    print((n//2+1)/n)
Buggy python submission (verdict: Time Limit Exceeded):
a,b = map(int,input().split())

L = [1]

if a < b: a,b = b,a
while b!=0:
    r = a%b
    a,b = b,r

G = a

for i in range(2,G+1):
    for j in L:
        if i%j==0 and j!=1: 
            break
    else:
        if G%i==0: 
            L.append(i)

print(len(L))   


Fixed submission:
from math import sqrt

a,b = map(int,input().split())
 
L = []
 
if a < b: a,b = b,a
while b!=0:
    r = a%b
    a,b = b,r
 
G = a
 
for i in range(2,int(sqrt(G))+1):
    if G%i==0:
        L.append(i)
        while G%i==0:
            G/=i

if G!=1:
    L.append(G)

print(len(L)+1)

Buggy python submission (verdict: Time Limit Exceeded):
a,b = map(int,input().split())

L = []

if a < b: a,b = b,a
while b!=0:
    r = a%b
    a,b = b,r

G = a

for i in range(2,G+1):
    if G%i==0:
        for j in L:
            if i%j==0:
                break
        else:
            L.append(i)

print(len(L)+1)   


Fixed submission:
from math import sqrt

a,b = map(int,input().split())
 
L = []
 
if a < b: a,b = b,a
while b!=0:
    r = a%b
    a,b = b,r
 
G = a
 
for i in range(2,int(sqrt(G))+1):
    if G%i==0:
        L.append(i)
        while G%i==0:
            G/=i

if G!=1:
    L.append(G)

print(len(L)+1)

Buggy python submission (verdict: Runtime Error):
import math

a,b = map(int,input().split())

G = math.gcd(a,b)
L = []

for i in range(2,G+1):
    if G%i==0:
        for j in L:
            if i%j==0:
                break
        else:
            L.append(i)

print(len(L)+1)  

Fixed submission:
from math import sqrt

a,b = map(int,input().split())
 
L = []
 
if a < b: a,b = b,a
while b!=0:
    r = a%b
    a,b = b,r
 
G = a
 
for i in range(2,int(sqrt(G))+1):
    if G%i==0:
        L.append(i)
        while G%i==0:
            G/=i

if G!=1:
    L.append(G)

print(len(L)+1)

Buggy python submission (verdict: Runtime Error):
import math

a,b = map(int,input().split())

G = math.gcd(a,b)
L = []

for i in range(2,int(math.sqrt(G))+1):
    if G%i==0:
        for j in L:
            if i%j==0:
                break
        else:
            L.append(i)

print(len(L)+1)

Fixed submission:
from math import sqrt

a,b = map(int,input().split())
 
L = []
 
if a < b: a,b = b,a
while b!=0:
    r = a%b
    a,b = b,r
 
G = a
 
for i in range(2,int(sqrt(G))+1):
    if G%i==0:
        L.append(i)
        while G%i==0:
            G/=i

if G!=1:
    L.append(G)

print(len(L)+1)
Buggy python submission (verdict: Time Limit Exceeded):
INF = float("INF")
n,m = map(int,input().split())
A = [0]*m
C = [0]*m
for i in range(m):
    a,b = map(int,input().split())
    A[i] = a
    for j in map(int,input().split()):
        j -= 1
        C[i] += 1<<j 

dp = [[INF]*(m+1) for _ in range(1<<n)]
dp[0][0] = 0
for i in range(1<<n):
    for j in range(m):
        dp[i][j+1] = min(dp[i][j],dp[C[j]&i^i][j] + A[j])

# for i in range(1<<n): print(dp[i])
print(dp[-1][-1] if dp[-1][-1] != INF else -1)

Fixed submission:
INF = float("INF")
n,m = map(int,input().split())
A = [0]*m
C = [0]*m
for i in range(m):
    a,b = map(int,input().split())
    A[i] = a
    for j in map(int,input().split()):
        j -= 1
        C[i] += 1<<j 

dp = [[INF]*(m+1) for _ in range(1<<n)]
dp[0][0] = 0
for i in range(1<<n):
    for j in range(m):
        dp[i][j+1] = min(dp[i][j],dp[C[j]&i^i][j] + A[j])

# for i in range(1<<n): print(dp[i])
print(dp[-1][-1] if dp[-1][-1] != INF else -1)
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
A = list(map(int,input().split()))
cnt = 0

while cnt < M:
    a = max(A)
    A[A.index(a)] = a//2
    cnt += 1

print(sum(A))

Fixed submission:
import heapq
from math import ceil
n,m = map(int,input().split())
a = [-int(i) for i in input().split()]
heapq.heapify(a)

for i in range(m):
    heapq.heappush(a,ceil(heapq.heappop(a)/2))

print(-sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
A = list(map(int,input().split()))
L = [0]*M

for i in A:
    cnt = 0
    while i!=0 or cnt<M:
        d = i-i//2
        if min(L)<d: 
            L[L.index(min(L))] = d
            i//=2
            cnt+=1
        else:
            break

print(sum(A)-sum(L))

Fixed submission:
import heapq
from math import ceil
n,m = map(int,input().split())
a = [-int(i) for i in input().split()]
heapq.heapify(a)

for i in range(m):
    heapq.heappush(a,ceil(heapq.heappop(a)/2))

print(-sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
A = list(map(int,input().split()))
L = []

for i in A:
    cnt = 0
    while i!=0 or cnt<M:
        L.append(i-i//2)
        i//=2
        cnt+=1

L.sort(reverse=True)
print(sum(A)-sum(L[:M]))

Fixed submission:
import heapq
from math import ceil
n,m = map(int,input().split())
a = [-int(i) for i in input().split()]
heapq.heapify(a)

for i in range(m):
    heapq.heappush(a,ceil(heapq.heappop(a)/2))

print(-sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = []
ans = 0

for i in range(n):
    s = input()
    l.append(sorted(s))
    
for i in range(n-1):
    for j in range(i+1,n):
        if l[i] == l[j]:
            ans += 1

print(ans)

Fixed submission:
n = int(input())
d = {}
ans = 0

for i in range(n):
    s = "".join(sorted(input()))
    if s not in d:
        d[s] = 1
    else:
        ans += d[s]
        d[s] += 1
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9+7
s = input()
n = len(s)
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for j in range(10):
        if s[i] != "?" and int(s[i]) != j: continue
        for k in range(13):
            dp[i+1][(k*10+j)%13] += dp[i][k]
    for j in range(13):
        dp[i+1][j] %= mod
        
# for i in range(n+1): print(dp[i])
print(dp[n][5])

Fixed submission:
mod = 10**9+7
s = input()
n = len(s)
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for j in range(10):
        if s[i] != "?" and int(s[i]) != j: continue
        for k in range(13):
            dp[i+1][(k*10+j)%13] += dp[i][k]
    for j in range(13):
        dp[i+1][j] %= mod
        
# for i in range(n+1): print(dp[i])
print(dp[n][5])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(i) for i in input().split()]
ball = []

for i in range(n,0,-1):
    if a[i-1] == 1: 
        ball.append(i)
        for j in range(1,int(i**0.5//1)+1):
            if i%j == 0:
                a[j-1] = 0 if a[j-1] == 1 else 1
                if i/j != j: 
                    a[i//j-1] = 0 if a[i//j-1] == 1 else 1

m = len(ball)
print(m)
if m != 0:
    for b in ball:
        print(b,end=" ")
    else:
        print("")

Fixed submission:
n = int(input())
a = [int(i) for i in input().split()]
ball = [0]*n
ans = []

for i in range(n,0,-1):
    cnt = 0
    x = i
    while x <= n:
        if ball[x-1] == 1:
            cnt += 1
        x += i
    if cnt%2 != a[i-1]:
        ball[i-1] = 1
        ans.append(i)

m = len(ans)
print(m)
if m != 0:
    for b in ans:
        print(b,end=" ")
    else:
        print("")

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(i) for i in input().split()]
ball = []

for i in reversed(range(1,n+1)):
    if a[i-1] == 1: 
        ball.append(i)
        for j in range(1,int(i**0.5//1)+1):
            if i%j == 0:
                a[j-1] = 0 if a[j-1] == 1 else 1
                if i/j != j: 
                    a[i//j-1] = 0 if a[i//j-1] == 1 else 1

m = len(ball)
print(m)
if m != 0:
    for b in ball:
        print(b,end=" ")
    else:
        print("")

Fixed submission:
n = int(input())
a = [int(i) for i in input().split()]
ball = [0]*n
ans = []

for i in range(n,0,-1):
    cnt = 0
    x = i
    while x <= n:
        if ball[x-1] == 1:
            cnt += 1
        x += i
    if cnt%2 != a[i-1]:
        ball[i-1] = 1
        ans.append(i)

m = len(ans)
print(m)
if m != 0:
    for b in ans:
        print(b,end=" ")
    else:
        print("")
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

mod = 1000000007
def perm(n,k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n]*finv[n-k]%mod
fac = [1]*(k+1)
finv = [1]*(k+1)
for i in range(1,k+1):
    fac[i] = fac[i-1]*i%mod
    finv[i] = pow(fac[i],mod-2,mod)

def dfs(cur,prev=-1):
    nxtcnt = 0
    res = 1
    for nxt in G[cur]:
        if nxt == prev: continue
        nxtcnt += 1
        res = res*dfs(nxt,cur)%mod
    colors = k-1 if cur == 0 else k-2
    res = res*perm(colors,nxtcnt)%mod
    return res
ans = k*dfs(0)%mod
print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
n,k = map(int,input().split())
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

mod = 1000000007
def perm(n,k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n]*finv[n-k]%mod
fac = [1]*(k+1)
finv = [1]*(k+1)
for i in range(1,k+1):
    fac[i] = fac[i-1]*i%mod
    finv[i] = pow(fac[i],mod-2,mod)

def dfs(cur,prev=-1):
    nxtcnt = 0
    res = 1
    for nxt in G[cur]:
        if nxt == prev: continue
        nxtcnt += 1
        res = res*dfs(nxt,cur)%mod
    colors = k-1 if cur == 0 else k-2
    res = res*perm(colors,nxtcnt)%mod
    return res
  
ans = k*dfs(0)%mod
print(ans)
Buggy python submission (verdict: Runtime Error):
s = list(input())
s.sort()

if s[0]==s[1] and s[2]==s[3] ans s[0]!=s[2]:
    ans = "Yes"
else:
    ans = "No"

print(ans)

Fixed submission:
s = list(input())
s.sort()

if s[0]==s[1] and s[2]==s[3] and s[0]!=s[2]:
    ans = "Yes"
else:
    ans = "No"

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
ab = [list(map(int,input().split())) for i in range(n)]

ab.sort(key= lambda x:x[1])
time = 0

for i in range(n):
    time += ab[i][0]
    if time > ab[i][1]:
        ans = "No"
        break
else:
    ans = "Yes"

print(ans)

Fixed submission:
s = input()

for i in range(3):
    if s[i] == s[i+1]:
        ans = "Bad"
        break
else:
    ans = "Good"

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a,b,c,d = map(int,input().split())
ans = 0

for i in range(a,b+1):
    if i%c != 0 and i%d != 0:
        ans += 1

print(ans)

Fixed submission:
def gcd(x,y):
    if y==0:
        return x
    else:
        return(gcd(y,x%y))
    
a,b,c,d = map(int,input().split())
g = gcd(c,d)
l = c*d//g

ans =(b-a+1)-( (b//c-(a-1)//c) + (b//d-(a-1)//d) - (b//l-(a-1)//l)  )
print(ans)
Buggy python submission (verdict: Runtime Error):
x,a = map(int,input().split())

if x < a:
    ans = 0
else;
    ans = 10

print(ans)

Fixed submission:
x,a = map(int,input().split())

if x < a:
    ans = 0
else:
    ans = 10

print(ans)