Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02675 (python)

Fixed submission:
n = int(input())
m = n%10
  
if m==3:
  print('bon')
elif m==0 or m==1or m==6or m==8:
  print('pon')
else:
  print('hon')

Buggy submission (verdict: Runtime Error):
n = int(input())
c = 1
pp = []
mm = []
for i in range(n):
  a,b = map(int,input().split())
  if a*b == 0:
    c += 1
  else:
    pp.append(a/b)
    
c %= mod
mod = 10**9+7
from collections import Counter
p = Counter(pp)
r = 1
s = set()
for i in p.keys():
  if i in s:
    continue
  ans = p[i]
  chk = p[-1/i]
  r *= (pow(2,ans,mod)-1+pow(2,chk,mod))%mod
  r %= mod
  s.add(-1/i)
print((r*c-1)%mod)
Problem p02681 (python)

Fixed submission:
s = input()
t = input()
if s == t[:len(t)-1]:
  print('Yes')
else:
  print('No')

Buggy submission (verdict: Runtime Error):
import numpy as np
n,m,x = map(int,input().split())
c = []
for i in range(n):
  a = [int(i) for i in input().split()]
  c.append(a)
  
c = np.array(c)
ans = float('inf')
for i in range(1,2**n):
  chk = [0]*m
  cost = 0
  for j in range(n):
    if (i>>j)&1 == 1:
      cost += c[j][0]
      chk += c[j][1:]
  if min(chk) >= x:
    ans = min(ans,cost)
  
if ans == float('inf'):
  ans = -1
print(ans)
Problem p02687 (python)

Fixed submission:
s = input()
if s == 'ABC':
  print('ARC')
else:
  print('ABC')

Buggy submission (verdict: Runtime Error):
x = int(input())
if x == 1:
  print(0,-1)
  exit()
  
def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

c = []
fct = factorize(x)
for div in divisorize(fct):
    c.append(num(div))
    
chk = False
for s in c:
  if chk:
    break
  for i in range(1000):
    if (i+s)**5-i**5 > x:
      break
    if (i+s)**5-i**5 == x:
      ans = (i+s,i)
      chk = True
      break
  if s <1000:    
    for p in range(s,1000):
      j = -1*p
      #print(s,(j+s)**5-j**5)
      if (j+s)**5-j**5 > x:
        break 
      if (j+s)**5-j**5 == x:
        ans = (j+s,j)
        chk = True
        break 
  for ww in range(1,(s+1)//2):
    jj = -1*ww
    if (jj+s)**5-jj**5 > x:
      break    
    if (jj+s)**5-jj**5 == x:
      ans = (jj+s,jj)
      chk = True
      break 
print(*ans)

Buggy submission (verdict: Runtime Error):
x = int(input())
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

c = factorization(x)
#print(c)
chk = False
for i in c:
  if chk:
    break
  s,t = i
  #print(s)
  for i in range(130):
    if (i+s)**5-i**5 > x:
      break
    if (i+s)**5-i**5 == x:
      ans = (i+s,i)
      chk = True
      break
  for i in range(1,100):
    j = -1*i
    #print(j+s,j)
    if (j+s)**5-j**5 > x:
      break 
    if (j+s)**5-j**5 == x:
      ans = (j+s,j)
      chk = True
      break 
      
print(*ans)
Problem p02703 (python)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

N,M,S = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
m = map(int,read().split())
CD = list(zip(m,m))

graph = [[] for _ in range(N)]
for u,v,a,b in ABC:
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))

def f():
  INF = 10 ** 18
  arrive = [False]*N
  ans = []
  qq = 2500
  dist = [[INF] * qq for _ in range(N)]
  dist[0][min(qq-1,S)] = 0
  q = [(0,min(qq-1,S),0)]
  while q:
      st,ss,v = heappop(q) # 総時間、銀貨、今いる頂点
      if dist[v][ss] < st:
        continue
      if not arrive[v]:
        arrive[v] = True
        ans.append((v,st))
        if all(arrive):
          break
      c,d = CD[v]
      # 銀貨の購入
      if ss < qq-1:
          ns = min(ss + c, qq-1)
          nt = st + d
          if dist[v][ns] > nt:
              dist[v][ns] = nt
              heappush(q,(nt,ns,v))
      # 移動
      for nex,g,tt in graph[v]:
          if ss-g < 0:
              continue
          dt = st + tt
          if dist[nex][ss-g] <= dt:
              continue
          dist[nex][ss-g] = dt
          heappush(q,(dt,ss-g,nex))
  return ans

ab = f()
from operator import itemgetter
ab = sorted(ab,key=itemgetter(0))
for i in range(1,N):
  print(ab[i][1])

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

N,M,S = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
m = map(int,read().split())
CD = list(zip(m,m))

graph = [[] for _ in range(N)]
for u,v,a,b in ABC:
    graph[u-1].append((v-1,a,b))
    graph[v-1].append((u-1,a,b))

def f():
  INF = 10 ** 18
  arrive = [False]*n
  ans = []
  qq = 2500
  dist = [[INF] * qq for _ in range(N)]
  dist[0][min(qq-1,S)] = 0
  q = [(0,min(qq-1,S),0)]
  while q:
      st,ss,v = heappop(q) # 総時間、銀貨、今いる頂点
      if dist[v][ss] < st:
        continue
      if not arrive[v]:
        arrive[v] = True
        ans.append((v,st))
        if all(arrive):
          break
      c,d = CD[v]
      # 銀貨の購入
      if ss < qq-1:
          ns = min(ss + c, qq-1)
          nt = st + d
          if dist[v][ns] > nt:
              dist[v][ns] = nt
              heappush(q,(nt,ns,v))
      # 移動
      for nex,g,tt in graph[v]:
          if ss-g < 0:
              continue
          dt = st + tt
          if dist[nex][ss-g] <= dt:
              continue
          dist[nex][ss-g] = dt
          heappush(q,(dt,ss-g,nex))
  return ans

ab = f()
from operator import itemgetter
ab = sorted(ab,key=itemgetter(0))
for i in range(N-1):
  print(ab[i][1])
Problem p02708 (python)

Fixed submission:
n,k = [int(i) for i in input().split()]
mod = 10**9+7
chk = 0
ans = 0
for i in range(n+1):
  chk += (n + i*n +1 -(i+1)*i)%mod
  chk %= mod
for i in range(k-1):
  ans += (n + i*n +1 -(i+1)*i)%mod
  ans %= mod
print((chk-ans)%mod)

Buggy submission (verdict: Runtime Error):
n,k=map(int,input().split());mod=10**9+7;print((n*(n+1)*(n+2)//6-k*(k-1)*(3*n-2*k+4)//6+n-k+2)%mod
Problem p02713 (python)

Fixed submission:
k = int(input())
ans = 0
import math
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      f = math.gcd(i,j)
      ff = math.gcd(f,l)
      ans += ff
print(ans)

Buggy submission (verdict: Runtime Error):
k = int(input())
ans = 0
import math
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      f = gcd(i,j)
      ff = gcd(f,l)
      ans += ff
print(ans)
Problem p02727 (python)

Fixed submission:
x,y,a,b,c  = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
q = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
p = sorted(p,reverse=True)
q = sorted(q,reverse=True)
r = sorted(r,reverse=True)
chk = p[:x]+q[:y]
chk = sorted(chk,reverse=True)
for i in range(c):
  if i < len(chk) and r[i] > chk[-(1+i)]:
    chk[-(1+i)] = r[i]   
print(sum(chk))

Buggy submission (verdict: Runtime Error):
x,y,a,b,c  = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
q = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
p = sorted(p,reverse=True)
q = sorted(q,reverse=True)
r = sorted(r,reverse=True)
chk = p[:x]+q[:y]
chk = sorted(chk,reverse=True)
for i in range(c):
  if r[i] > chk[-1+i]:
    chk[-1+i] = r[i] 
print(sum(chk))
Problem p02741 (python)

Fixed submission:
k = int(input())
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(l[k-1])

Buggy submission (verdict: Runtime Error):
k = int(i) for i in input().split()
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(l[k])
Problem p02844 (python)

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
s = input()
def multi_index(l,x):
  return tuple([i for i,_x in enumerate(l) if _x == x])

ans = 0
for i in range(10):
  e = 0
  if str(i) in s:
    c = multi_index(s,str(i))[0]
    for j in range(10):
      if str(j) in s and i!=j and c<=len(s)-2:
        for q in range(c+1,len(s)-1):
          if str(j) == s[q]:
            d = q
            break
        else:
          d = -1
      elif str(j) in s and i==j and len(multi_index(s,str(i)))>=2:
        d = multi_index(s,str(i))[1]
      else:
        d = -1
      if d > c:
        for l in range(10):
          if str(l) in s and i!=j and j!=l and i!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i!=j and j==l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i==j and j!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i==j and j==l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i==l and j!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n = int(input())
s = input()
ans = set()
for i in range(len(s)-2):
  for j in range(i+1,len(s)-1):
    for l in range(j+1,len(s)):
      ans.add(int(s[i])*100+int(s[j])*10+int(s[l]))
print(len(ans))

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n = int(input())
s = input()
ans = set()
for i in range(len(s)-2):
  for j in range(i+1,len(s)-1):
    for l in range(j+1,len(s)):
      ans.add(int(s[i])*100+int(s[j])*10+int(s[l]))
print(len(ans))

Buggy submission (verdict: Runtime Error):
def main():  
  import sys
  input = sys.stdin.readline
  n = int(input())
  s = input()
  ans = set()
  for i in range(len(s)-2):
    for j in range(i+1,len(s)-1):
      for l in range(j+1,len(s)):
        ans.add(int(s[i])*100+int(s[j])*10+int(s[l]))
  print(len(ans))
if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():  
  import sys
  input = sys.stdin.readline
  n = int(input())
  s = input()
  ans = set()
  for i in range(len(s)-2):
    for j in range(i+1,len(s)-1):
      for l in range(j+1,len(s)):
        ans.add(int(s[i])*100+int(s[j])*10+int(s[l]))
  print(len(ans))
if __name__ == '__main__':
    main()
Problem p02936 (python)

Fixed submission:
import sys
input = sys.stdin.readline
import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
g = [[] * n for i in range(n)]

par = [-1]*n
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

chk = [0]*n
for i in range(q):
    x, y = map(int, input().split())
    chk[x-1] += y

def dfs(now, prev):
    # リストはglobal宣言の必要がない？
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            chk[next] += chk[now]
            dfs(next, now)

dfs(0,-1)
print(*chk)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
import sys
sys.setrecursionlimit(200000)

n, q = map(int, input().split())
g = [[] * n for i in range(n)]

par = [-1]*n
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

chk = [0]*n
for i in range(q):
    x, y = map(int, input().split())
    chk[x-1] += y

def dfs(now, prev):
    # リストはglobal宣言の必要がない？
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            chk[next] += chk[now]
            dfs(next, now)

dfs(0,-1)
chk = list(map(str,chk))
print(' '.join(chk))

Buggy submission (verdict: Runtime Error):
n, q = map(int, input().split())
g = [[] * n for i in range(n)]

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True
      
par = [-1]*n
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    unite(u,v)

chk = [0]*n
for i in range(q):
    x, y = map(int, input().split())
    chk[x-1] += y

def dfs(now, prev):
    # リストはglobal宣言の必要がない？
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            chk[next] += chk[now]
            dfs(next, now)

par = tuple(par)            
for i in range(n):
  if par[i] < 0:
    dfs(i,-1)

chk = list(map(str,chk))
print(' '.join(chk))
Problem p02949 (python)

Fixed submission:
from collections import deque
def use_path(n,start,es):
    q = deque()
    chk = [False] * n
    q.append(start)
    chk[start] = True
    used = {start}
    while len(q) > 0:
        node = q.popleft()
        for nex in es[node]:
            if not chk[nex]:
                chk[nex] = True
                q.append(nex)
                used.add(nex)
    return used
  
def belman(s,g,n,es):
    d = [10**10] * n
    d[s] = 0
    fin = False
    cnt = 0
    while True:
      update = False
      for p,q,r in es:
        if d[p] != 10**10 and d[q] > d[p] + r:
          d[q] = d[p] + r
          update = True
      cnt += 1
      if not update:
        fin = True
        break
      if cnt > n+1:
          break      
    if fin:
        return max(0,-d[g])
    else:
        return -1   
  
n,m,p = map(int, input().split())

l = [[] for i in range(n)]
r = [[] for i in range(n)]
edges = []

for i in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    l[a].append(b)
    r[b].append(a)
    edges.append((a,b,-c+p))
    
use_nodes = use_path(n,0,l) & use_path(n,n-1,r)
es = [(a,b,c) for a,b,c in edges if a in use_nodes and b in use_nodes]
print(belman(0,n-1,n,es))

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
chk = []
for i in range(n):
  a,b =  map(int,input().split())
  if a <= m:
    chk.append((a,b))

from heapq import heappop, heappush
from operator import itemgetter
chk = sorted(chk,key=itemgetter(0),reverse=True)

q = []
ans = 0
for i in range(1, m + 1):
    while chk and chk[-1][0] <= i:
        a,b = chk.pop()
        heappush(q,-b)
    if q:
        ans -= heappop(q)
print(ans)
Problem p02961 (python)

Fixed submission:
k = int(input())
X,Y = map(int,input().split())
x = max(abs(X),abs(Y))
y = min(abs(X),abs(Y))
c = (k-(x+y)%k)%k
if k%2 == 0 and (x+y)%2 == 1:
  print(-1)
  exit()
  
import math
ans = []
m = math.ceil((x+y)/k)
if (x+y)/k == int((x+y)/k):
  for i in range(m):
    ans.append((min(x,k*i+k),max(0,k*i+k-x)))
    
elif m == 1:
  if (x+y)%2 == 1:
    ans.append((x,x-k))
    ans.append((x+(k+x-y)//2,(-k+x+y)//2))
    ans.append((x,y))
  else:
    ans.append(((x+y)//2,-k+(x+y)//2))
    ans.append((x,y))
               
elif c%2 == 0 and x+y >= k:
  a = abs((k*m-x-y)//2)
  for i in range(m-1):
    l = k*i+k
    if a >= l:
      ans.append((0,-l))
    elif a < l <= x+a:
      ans.append((l-a,-a))
    elif x+a < l:
      ans.append((x,l-x-2*a))
  ans.append((x,y))
  
else:
  m += 1
  a = abs((k*m-x-y)//2)
  for i in range(m-1):
    l = k*i+k
    if a >= l:
      ans.append((0,-1))
    elif a < l <= x+a:
      ans.append((l-a,-a))
    elif x+a < l:
      ans.append((x,l-x-2*a))
  ans.append((x,y))
  
print(len(ans))
for i,j in ans:
  if abs(X) < abs(Y):
    i,j = j,i
  if X < 0:
    i *= -1
  if Y < 0:
    j *= -1
  print(i,j)

Buggy submission (verdict: Runtime Error):
k = int(input())
X,Y = map(int,input().split())
x = abs(X)
y = abs(Y)

if k%2 == 0 and (x+y)%2 == 1:
  print(-1)
  exit()
  
import math
ans = []
m = math.ceil((x+y)/k)
if (x+y)/k == int((x+y)/k):
  for i in range(m):
    ans.append((min(x,k*i+k),max(0,k*i+k-x)))
    
elif m == 1:
  if (x+y)%2 == 1:
    ans.append(x,x-k)
    ans.append(x+(k+x-y)//2,(-k+x+y)//2)
    ans.append(x,y)
  else:
    ans.append(-k+(x+y)//2,(x+y)//2)
    ans.append(x,y)
    
elif (m*k-x-y)%2 == 0:
  x += (m*k-x-y)//2
  for i in range(m-1):
    ans.append((min(x,k*i+k),max(0,k*i+k-x)))
  ans.append((abs(X),y))
  
elif (m*k-x-y)%2 == 1:
  x += (m*k-x-y)//2
  m += 1
  for i in range(m-1):
    ans.append((min(x,k*i+k),max(0,k*i+k-x)))
  ans.append((abs(X),y))
  
print(len(ans))
for i,j in ans:
  if X < 0:
    i *= -1
  if Y < 0:
    j *= -1
  print(i,j)
Problem p02973 (python)

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
if n == 1:
  print(1)
  exit()
  
chk = []
for i in range(n):
  a = int(input())
  chk.append((i,a))
  
from bisect import bisect_left,insort_left
from collections import deque
ans = 1

c = deque([])
for j in chk:
  i,a = j
  if i == 0:
    c.append((a,n-i))
  else:
    ind = bisect_left(c,(a,n-i))
    if ind == 0:
      ans += 1
      c.appendleft((a,n-i))
    else:
      c[ind-1] = (a,n-i)
      
print(ans)

Buggy submission (verdict: Runtime Error):
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*10**5
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=[b]
for i in v[:M]:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

Buggy submission (verdict: Runtime Error):
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*7**6
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=[b]
for i in v[:M]:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

Buggy submission (verdict: Runtime Error):
from heapq import*
(n,m),*t=[map(int,s.split())for s in open(0)]
q=[0]*7**6
v=[[]for _ in q]
z=0
for a,b in t:
  v[a-1]+=[b]
for i in v[:m]:
  for j in i:
    heappush(q,-j)
  z-=heappop(q)
print(z)
Problem p02975 (python)

Fixed submission:
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
s = set(a)
c = Counter(a)

if n%3 != 0:
  if s == {0}:
    print('Yes')
  else:
    print('No')
else:
  if len(c) > 3:
      print('No')
  elif len(c) == 3:
    a,b,q = list(s)
    if a^b == q and c[a] == n//3 and c[b] == c[q]:
      print('Yes')
    else:
      print('No')
  elif len(c) == 2:
    if not 0 in s:
      print('No')
    else:
      if c[0] == n//3:
        print('Yes')
      else:
        print('No')
  elif len(c) == 1:
    if s == {0}:
      print('Yes')
    else:
      print('No')

Buggy submission (verdict: Runtime Error):
from colletions import Counter
n = int(input())
if n%3 != 0:
  print('No')
else:
  a = [int(i) for i in input().split()]
  c = Counter(a)
  for i in c.values():
    if i != n//3:
      print('No')
      exit()
  print('Yes')
Problem p02985 (python)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
mod = 10**9+7
sys.setrecursionlimit(4100000)
n,k = map(int,readline().split())
if n == 1:
  print(k%mod)
  exit()

g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int,readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

ans = 1
used = [False]*n
def dfs(now,prev,p):
    global ans
    if k <= p:
      ans = 0
    ans *= k-p
    ans %= mod
    used[now] == True
    if all(used):
      return ans
    cnt = 1
    new = []
    for next in g[now]:
      if next == prev:
        cnt += 1
      else:
        new.append(next)
    for i,next in enumerate(new):
      dfs(next,now,cnt+i)
      
dfs(0,-1,0)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
mod = 10**9+7

n,k = map(int,readline().split())
if n == 1:
  print(k%mod)
  exit()

g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int,readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

ans = 1
used = [False]*n
def dfs(now,prev,p):
    global ans
    if k <= p:
      ans = 0
    ans *= k-p
    ans %= mod
    used[now] == True
    if all(used):
      return ans
    cnt = 1
    new = []
    for next in g[now]:
      if next == prev:
        cnt += 1
      else:
        new.append(next)
    for i,next in enumerate(new):
      dfs(next,now,cnt+i)
      
dfs(0,-1,0)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,k = map(int,readline().split())
mod = 10**9+7
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int,readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

ans = 1
used = [False]*n
def dfs(now,prev,p):
    global ans
    if k <= p:
      ans = 0
    ans *= k-p
    ans %= mod
    used[now] == True
    if all(used):
      return ans
    cnt = 1
    new = []
    for next in g[now]:
      if next == prev:
        cnt += 1
      else:
        new.append(next)
    for i,next in enumerate(new):
      dfs(next,now,cnt+i)
      
dfs(0,-1,0)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,k = map(int,readline().split())
mod = 10**9+7
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int,readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

ans = 1
used = [False]*n
def dfs(now,prev,p):
    global ans
    if k <= p:
      return 0
    ans *= k-p
    ans %= mod
    used[now] == True
    if all(used):
      return ans
    cnt = 1
    new = []
    for next in g[now]:
      if next == prev:
        cnt += 1
      else:
        new.append(next)
    for i,next in enumerate(new):
      dfs(next,now,cnt+i)
      
dfs(0,-1,0)
print(ans)
Problem p02997 (python)

Fixed submission:
n,k = map(int,input().split())
if n == 2 and k == 0:
  print(1)
  print(1,2)
  exit()
  
if k > (n-1)*(n-2)//2 or n == 2:
  print(-1)
  exit()
  
if n == 3:
  if k == 1:
    print(2)
    print(1,2)
    print(2,3)
  elif k == 0:
    print(3)
    print(1,2)
    print(2,3)
    print(3,1)
  else:
    print(-1)
  exit()
    
m = (n-1)*(n-2)//2+(n-1)-k
print(m)
for i in range(n-1):
  print(1,2+i)
for i in range(min(n-1,m-n+1)):
  if 3+i > n:
    print(2+i,2)
  else:
    print(2+i,3+i)
    
if m > (n-1)*2:
  cnt = m-(n-1)*2
  for i in range(2,n-2):
    if cnt == 0:
        break
    for j in range(2,n-i+1):
      print(j,j+i)
      cnt -= 1
      if cnt == 0:
        break

Buggy submission (verdict: Runtime Error):
n,k = map(int,input().split())

if k > (n-1)*(n-2)//2:
  print(-1)
  exit()
    
m = (n-1)*(n-2)//2+(n-1)-k
print(m)
for i in range(n-1):
  print(1,2+i)
    
if m > n-1:
  c = m-(n-1)
  for i in range(1,n-1):
    if c == 0:
        break
    for j in range(2,n-i+1):
      print(j,j+i)
      cnt -= 1
      if c == 0:
        break