Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
X,Y,Z,K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

memo = set([((0,0,0), A[0]+B[0]+C[0]),])

'''
def next(next_cand, (a,b,c)):
  if a<len(A)-1:
    next_cand.append(((a+1,b,c), A[a+1]+B[b]+C[c]))
  if b<len(B)-1:
    next_cand.append(((a,b+1,c), A[a]+B[b+1]+C[c]))
  if c<len(C)-1:
    next_cand.append(((a,b,c+1), A[a]+B[b]+C[c+1]))
'''

while len(memo)<K:
  next_cand=set()
  
  for m in memo:
    #print(m)
    a,b,c = m[0]
    if a<len(A)-1:
      next_cand.add(((a+1,b,c), A[a+1]+B[b]+C[c]))
    if b<len(B)-1:
      next_cand.add(((a,b+1,c), A[a]+B[b+1]+C[c]))
    if c<len(C)-1:
      next_cand.add(((a,b,c+1), A[a]+B[b]+C[c+1]))
      
  #print(next_cand)
  x = list(next_cand - (next_cand&memo))
  #print(x)
           
  x.sort(reverse=True, key=lambda x:x[1])
  #print(x)
  memo.add((x[0]))

memo=sorted(list(memo),reverse=True, key=lambda x:x[1])
for m in memo:
  a,b,c = m[0]
  print(A[a] +B[b] +C[c])



Fixed submission:
X,Y,Z,K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

import heapq

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
m = A[0]+B[0]+C[0]

counted=set([])
in_heap=set([])

hp = []
heapq.heapify(hp)
heapq.heappush(hp, (0, (0,0,0)))

#print(hp)

for _ in range(K):
  x = heapq.heappop(hp)
  print(m-x[0])
  counted.add(x[1])
  a,b,c = x[1]
  if (a+1, b,c) not in counted and (a+1, b,c) not in in_heap and a<len(A)-1:
    heapq.heappush(hp, (m-A[a+1]-B[b]-C[c], (a+1,b,c)))
    in_heap.add((a+1, b, c))
  if (a, b+1,c) not in counted and (a, b+1,c) not in in_heap and b<len(B)-1:
    heapq.heappush(hp, (m-A[a]-B[b+1]-C[c], (a,b+1,c)))
    in_heap.add((a,b+1,c))
  if (a, b,c+1) not in counted and (a, b,c+1) not in in_heap and c<len(C)-1:
    heapq.heappush(hp, (m-A[a]-B[b]-C[c+1], (a,b,c+1)))
    in_heap.add((a,b,c+1))
Buggy python submission (verdict: Runtime Error):
import re, copy
import itertools
N= int(input())

pat='(AGC|ACG|GAC|AGAC|AGTC|AGCC|AAGC|ATGC|AGGC)'
repattern = re.compile(pat)

memo={}

for s in itertools.product('ATGC', repeat=3):
  if not repattern.search(''.join(s)):
  	memo[''.join(s)] = 1
  
for _ in range(3,N):
  new_memo={}
  for k,v in memo.items():
    for c in 'ATGC':
      if not repattern.search(k+c):
        new_memo[(k+c)[-3:]] = new_memo.get((k+c)[-3:],0)+v
  memo=new_memo

print(sum(memo.values())%(10**9+7)

Fixed submission:
import re, copy
import itertools
N= int(input())

pat='(AGC|ACG|GAC|AGAC|AGTC|AGCC|AAGC|ATGC|AGGC)'
repattern = re.compile(pat)

memo={}

for s in itertools.product('ATGC', repeat=3):
  if not repattern.search(''.join(s)):
  	memo[''.join(s)] = 1
  
for _ in range(3,N):
  new_memo={}
  for k,v in memo.items():
    for c in 'ATGC':
      if not repattern.search(k+c):
        new_memo[(k+c)[-3:]] = new_memo.get((k+c)[-3:],0)+v
  memo=new_memo

print(sum(memo.values())%(10**9+7))

Buggy python submission (verdict: Time Limit Exceeded):
import re
import itertools
N= int(input())

pat='(AGC|ACG|GAC|AGAC|AGTC|AGCC|AAGC|ATGC|AGGC)'
repattern = re.compile(pat)

answer=0
for s in itertools.product('ATGC', repeat=N):
  answer += not repattern.search(''.join(s))

print(answer)

import numpy

Fixed submission:
import re, copy
import itertools
N= int(input())

pat='(AGC|ACG|GAC|AGAC|AGTC|AGCC|AAGC|ATGC|AGGC)'
repattern = re.compile(pat)

memo={}

for s in itertools.product('ATGC', repeat=3):
  if not repattern.search(''.join(s)):
  	memo[''.join(s)] = 1
  
for _ in range(3,N):
  new_memo={}
  for k,v in memo.items():
    for c in 'ATGC':
      if not repattern.search(k+c):
        new_memo[(k+c)[-3:]] = new_memo.get((k+c)[-3:],0)+v
  memo=new_memo

print(sum(memo.values())%(10**9+7))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
C=[int(input()) for _ in range(N)]
mod = int(1e9+7)

memo={}
new_C=[]

pre = 1.5
i=0
for c in C:
    if c!= pre:
        new_C.append(c)
        memo.setdefault(c,[]).append(i)
        i+=1
    pre=c

answer = [0]*len(new_C)
answer[0] = 1

for i in range(1, len(new_C)):
    try:
        prev_index = i-1 - new_C[i-1::-1].index(new_C[i])
        answer[i] = (answer[i-1] + answer[prev_index]) %mod
    except:
        answer[i] = answer[i-1]

print(answer[-1])

Fixed submission:
N = int(input())
C = [int(input()) for _ in range(N)]
mod = int(1e9+7)

from itertools import groupby
x = [0] + [k for k, g in groupby(C)]

dp = [0]*(len(x)) # i個目までで何通りあるか
dp[0] = 1
memo = {}

for i in range(1, len(x)):
    c = x[i]
    memo[c] = (memo.get(c,0) + dp[i-1])%mod
    dp[i] = memo[c]

print(dp[-1])
Buggy python submission (verdict: Runtime Error):
A, B = list(map(int, input().split()))

def xorsum(m):
  if m==3:
    return 0
  if m==2:
    return 3
  if m==1:
    return 1
  if m==0:
    return 0
  h=1
  while h<=m:
    h=h*2
  h=h//2
  return xorsum(m-h)^(((m-h+1)%2)*h)

print(xorsum(B)^xorsum(A-1))

  
  

  
  

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

def xorsum(m):
  if m==3:
    return 0
  if m==2:
    return 3
  if m==1:
    return 1
  if m==0:
    return 0
  if m==-1:
    return 0
  h=1
  while h<=m:
    h=h*2
  h=h//2
  return xorsum(m-h)^(((m-h+1)%2)*h)

print(xorsum(B)^xorsum(A-1))

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

A, B = list(map(int, input().split()))

def xorsum(m):
  if m==3:
    return 0
  if m==2:
    return 3
  if m==1:
    return 1
  if m==0:
    return 0
  h = 2 ** math.floor(math.log2(m))
  return xorsum(m-h)^(((m-h+1)%2)*h)

print(xorsum(B)^xorsum(A-1))

  
  

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

def xorsum(m):
  if m==3:
    return 0
  if m==2:
    return 3
  if m==1:
    return 1
  if m==0:
    return 0
  if m==-1:
    return 0
  h=1
  while h<=m:
    h=h*2
  h=h//2
  return xorsum(m-h)^(((m-h+1)%2)*h)

print(xorsum(B)^xorsum(A-1))

Buggy python submission (verdict: Runtime Error):

A, B = list(map(int, input().split()))

def xorsum(m):
  if m==3:
    return 0
  if m==2:
    return 3
  if m==1:
    return 1
  if m==0:
    return 0
  h = 2 ** math.floor(math.log2(m))
  return xorsum(m-h)^(((m-h+1)%2)*h)
print(xorsum(B)^xorsum(A-1))

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

def xorsum(m):
  if m==3:
    return 0
  if m==2:
    return 3
  if m==1:
    return 1
  if m==0:
    return 0
  if m==-1:
    return 0
  h=1
  while h<=m:
    h=h*2
  h=h//2
  return xorsum(m-h)^(((m-h+1)%2)*h)

print(xorsum(B)^xorsum(A-1))

Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce

A, B = list(map(int, input().split()))

L = [i for i in range(A,B+1)]

print(reduce(lambda x, y: x^y, L))

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

def xorsum(m):
  if m==3:
    return 0
  if m==2:
    return 3
  if m==1:
    return 1
  if m==0:
    return 0
  if m==-1:
    return 0
  h=1
  while h<=m:
    h=h*2
  h=h//2
  return xorsum(m-h)^(((m-h+1)%2)*h)

print(xorsum(B)^xorsum(A-1))
Buggy python submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

roots = [(i,1) for i in range(N+1)] # root, num_islands_in_group

inconveniences = [0]*(M+1)
inconveniences[-1] = N*(N-1)//2 #すべての橋が崩落するとNC2

def find_root(a, roots=roots):
  if roots[a][0] == a:
    return roots[a]
  else:
    roots[a] = find_root(roots[a][0])
  return roots[a]

def reduce_inconvenience_with_unite(a, b, roots=roots):
  root_a, n_a = find_root(a)
  root_b, n_b = find_root(b)
  if root_a == root_b:
    return 0
  else:
    if n_a > n_b:
      roots[root_a] = (root_a, n_a + n_b)
      roots[root_b] = (root_a, n_a + n_b)
    else:
      roots[root_a] = (root_b, n_a + n_b) 
      roots[root_b] = (root_b, n_a + n_b)
    return n_a * n_b

for i, ab in enumerate(AB[:0:-1]): #実は1個めの橋は全く関係ない
  a, b = ab
  inconveniences[M-1-i] = inconveniences[M-i] - reduce_inconvenience_with_unite(a,b)

for inc in inconveniences[1:]:
  print(inc)


Fixed submission:
import math


A, B, C = list(map(int, input().split()))

print(min(math.floor(B/A), C))
Buggy python submission (verdict: Runtime Error):
S=input()

if len(S)==1:
  print(0)

print(min(S[::2].count(0), S[1::2].count(1)) + min(S[::2].count(1), S[1::2].count(0)))

Fixed submission:
S = input()
s1 = S.count('1')
s0 = S.count('0')
print(2*min(s1, s0))
Buggy python submission (verdict: Runtime Error):
N, K=input().split()

if (N+2)//3 >= K:
  print('YES')
else:
  print('NO')

Fixed submission:
N, K=list(map(int,input().split()))
 
if (N+1)//2 >= K:
  print('YES')
else:
  print('NO')
Buggy python submission (verdict: Runtime Error):
X = list(map(int, input().split()))
X.sort()
print(0.5*(X[0]*X[1])

Fixed submission:
X = list(map(int, input().split()))
X.sort()
print(int(0.5*X[0]*X[1]))
Buggy python submission (verdict: Time Limit Exceeded):
N,M = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

mod = 10**9+7

a = 0
b = 0
ans = 1

for i in range(N*M,0,-1):
  #print(i,a,b,ans)
  if i in A and i in B:
    ans = ans
    a += 1
    b += 1
  elif i in A: # i not in B
    ans *= b
    ans %= mod
    a+=1
  elif i in B:
    ans *= a
    ans %= mod
    b+=1
  else:
    if a*b - (N*M - i) <= 0:
      print(0)
      break
    else:
      ans *= a*b - (N*M - i)
      ans %= mod
      
else:
  print(ans)
    
    
  


Fixed submission:
N,M = list(map(int, input().split()))
A = set(list(map(int, input().split())))
B = set(list(map(int, input().split())))

mod = 10**9+7

a = 0
b = 0
ans = 1

for i in range(N*M,0,-1):
  #print(i,a,b,ans)
  if i in A and i in B:
    ans = ans
    a += 1
    b += 1
  elif i in A: # i not in B
    ans *= b
    ans %= mod
    a+=1
  elif i in B:
    ans *= a
    ans %= mod
    b+=1
  else:
    if a*b - (N*M - i) <= 0:
      print(0)
      break
    else:
      ans *= a*b - (N*M - i)
      ans %= mod
      
else:
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
H=[]
for i in range(N):
  H.append(int(input()))

H.sort()

ans=10**9
for i in range(N-K+1):
  ans = min(ans, max(H[i:i+K]) - min(H[i:i+K]))
  
print(ans)


Fixed submission:
N, K = list(map(int, input().split()))
H=[]
for i in range(N):
  H.append(int(input()))

H.sort()

ans=10**9
for i in range(N-K+1):
  ans = min(ans, H[i+K-1] - H[i])
  
print(ans)
Buggy python submission (verdict: Runtime Error):
import math

s=input()
l=len(s)

ans=0
mindiff=1000

for i in range(l-2):
  if mindiff > math.abs(int(s[i:i+3])-753):
    ans=int(s[i:i+3])
    mindiff=math.abs(int(s[i:i+3])-753)

print(ans)
            

Fixed submission:
s=input()
l=len(s)

mindiff=1000

for i in range(l-2):
  if mindiff > abs(int(s[i:i+3])-753):
    mindiff=abs(int(s[i:i+3])-753)

print(mindiff)
Buggy python submission (verdict: Time Limit Exceeded):
N, X = list(map(int, input().split()))
X_l = list(map(int, input().split()))

def golden_search(func, l,r):
  # 最小値を求める
  phi = 1.618 # phi=2とすると三分探索
  if l >= r-4:
    return min([func(k) for k in range(l,r+1)])

  c1 = int((phi/(1+phi))*l + (1/(1+phi))*r)
  c2 = int((1/(1+phi))*l + (phi/(1+phi))*r)
  if func(c1) < func(c2):
    r = c2
  elif func(c1) >= func(c2):
    l = c1
  return golden_search(func, l,r)

def Ktimes(k):
  ret = X*k + X*N
  ret += 2* sum(X_l[::-1][:k])
  ret += sum([(2*(i//k)+3)*x for i,x in enumerate(X_l[::-1])])
  return ret

answer = golden_search(Ktimes, 1, N)
print(answer)


Fixed submission:
N, X = list(map(int, input().split()))
X_l = list(map(int, input().split()))

def golden_search(func, l,r):
  # 最小値を求める
  phi = 1.618 # phi=2とすると三分探索
  if l >= r-4:
    return min([func(k) for k in range(l,r+1)])

  c1 = int((phi/(1+phi))*l + (1/(1+phi))*r)
  c2 = int((1/(1+phi))*l + (phi/(1+phi))*r)
  if func(c1) < func(c2):
    r = c2
  elif func(c1) >= func(c2):
    l = c1
  return golden_search(func, l,r)

memo = {}
def Ktimes(k):
  if k not in memo:
    memo[k] = X*k + X*N
    memo[k] += 2* sum(X_l[::-1][:k])
    memo[k] += sum([(2*(i//k)+3)*x for i,x in enumerate(X_l[::-1])])
  return memo[k]

answer = golden_search(Ktimes, 1, N)
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
N, X = list(map(int, input().split()))
X_l = list(map(int, input().split()))

def golden_search(func, l,r):
  # 最小値を求める
  phi = 1.618 # phi=2とすると三分探索
  if l >= r-4:
    return min([func(k) for k in range(l,r+1)])

  c1 = int((phi/(1+phi))*l + (1/(1+phi))*r)
  c2 = int((1/(1+phi))*l + (phi/(1+phi))*r)
  if func(c1) < func(c2):
    r = c2
  elif func(c1) >= func(c2):
    l = c1
  return golden_search(func, l,r)

def Ktimes(k):
  ret = X*k + X*N
  for i,x in enumerate(X_l[::-1]):
    t = i//k
    if t==0:
      ret += 5*x
    else:
      ret += ((t+2)**2 - (t+1)**2)*x
  return ret

answer = golden_search(Ktimes, 1, N)
print(answer)

Fixed submission:
N, X = list(map(int, input().split()))
X_l = list(map(int, input().split()))

def golden_search(func, l,r):
  # 最小値を求める
  phi = 1.618 # phi=2とすると三分探索
  if l >= r-4:
    return min([func(k) for k in range(l,r+1)])

  c1 = int((phi/(1+phi))*l + (1/(1+phi))*r)
  c2 = int((1/(1+phi))*l + (phi/(1+phi))*r)
  if func(c1) < func(c2):
    r = c2
  elif func(c1) >= func(c2):
    l = c1
  return golden_search(func, l,r)

memo = {}
def Ktimes(k):
  if k not in memo:
    memo[k] = X*k + X*N
    memo[k] += 2* sum(X_l[::-1][:k])
    memo[k] += sum([(2*(i//k)+3)*x for i,x in enumerate(X_l[::-1])])
  return memo[k]

answer = golden_search(Ktimes, 1, N)
print(answer)
Buggy python submission (verdict: Runtime Error):
N=int(input())
K=int(input())

if K==1:
  print(N[0])
  
else:
  if N[0]==1:
    print(N[1])
  else:
    print(N[0])

Fixed submission:
S=input()
K=int(input())

for i, s in enumerate(S):
  if int(s)==1:
    if i+1 < K:
      continue
    if i+1==K:
      print('1')
      break
  else:
    print(s)
    break
Buggy python submission (verdict: Time Limit Exceeded):
N,M,Q= list(map(int, input().split()))
LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]

from itertools import product, permutations, combinations

memo = {(i,i):0 for i in range(1, N+1)}
trains = {(i,i):0 for i in range(1, N+1)}
for x in combinations(range(1,N+1), 2):
  x = (min(x), max(x))
  memo[x] = 0
  trains[x] = 0

for l, r in LR:
  memo[(l,r)] +=1

for k, v in memo.items():
  for l, r in product(range(1,k[0]+1), range(k[1], N+1)):
    trains[(l,r)] += v

for p,q in PQ:
  print(trains[(p,q)])

Fixed submission:
N,M,Q= list(map(int, input().split()))
LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]

import numpy as np

trains = np.array([[0]*N for _ in range(N)])

for l, r in LR:
  trains[l-1][r-1] +=1

# 二次元累積和
row_sum = trains.cumsum(axis=1)
matrix_sum = row_sum.cumsum(axis=0)

for p,q in PQ:
  if p==1:
    print(matrix_sum[q-1, q-1])
  else:
    print(matrix_sum[q-1,q-1] - matrix_sum[p-2,q-1])
Buggy python submission (verdict: Time Limit Exceeded):
import math
N, K = list(map(int, input().split()))
A = list(map(int, input().split())) #A[0]〜A[N-1]

m = min(A)
answer = N

for i in range(N-K+1): #A[i:i+K]〜A[N-K:N]
  if not m in A[i:i+K]:
    continue
  answer = min(answer,
              (1 + math.ceil(i/(K-1)) + math.ceil((N-K-i)/(K-1))))
print(answer)

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

print((N-1)//(K-1) + bool((N-1)%(K-1)))

Buggy python submission (verdict: Runtime Error):
import math
N, K = list(map(int, input().split()))
A = list(map(int, input().split())) #A[0]〜A[N-1]

m = min(A)
answer = N

for i in range(N-K+1): #A[i:i+K]〜A[N-K:N]
  if not k in A[i:i+K]:
    continue
  answer = min(answer,
              (1 + math.ceil(i/(K-1)) + math.ceil((N-K-i)/(K-1))))
print(answer)

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

print((N-1)//(K-1) + bool((N-1)%(K-1)))

Buggy python submission (verdict: Time Limit Exceeded):
import math
N, K = list(map(int, input().split()))
A = list(map(int, input().split())) #A[0]〜A[N-1]

m = min(A)
answer = N

for i in range(N-K+1): #A[i:i+K]〜A[N-K:N]
  if min(A[i:i+K]) != m:
    continue
  answer = min(answer,
              (1 + math.ceil(i/(K-1)) + math.ceil((N-K-i)/(K-1))))
print(answer)

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

print((N-1)//(K-1) + bool((N-1)%(K-1)))
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
K=int(input())

_set=set()

for i in range(len(s)):
  for j in range(i+1, len(s)+1):
    #print(i,j)
    _set.add(s[i:j])

#print(sorted(list(_set)))
print(sorted(list(_set))[K-1])

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

memo=set()
for i in range(len(s)):
  for j in range(1,min(len(s)-i+1,K+1)):
    memo.add(s[i:i+j])
    
memo=list(memo)
memo.sort()
#print(memo)
print(memo[K-1])

Buggy python submission (verdict: Runtime Error):
s=input()
K=int(input())

_set=set()

for i in range(len(s)-1):
  for j in range(i+1, len(s)):
    _set.add(s[i:j])

#print(sorted(list(_set)))
print(sorted(list(_set))[K-1])

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

memo=set()
for i in range(len(s)):
  for j in range(1,min(len(s)-i+1,K+1)):
    memo.add(s[i:i+j])
    
memo=list(memo)
memo.sort()
#print(memo)
print(memo[K-1])
Buggy python submission (verdict: Runtime Error):
class UnionFind():
  def __init__(self):
    self.roots = {}
    self.nums = {}

  def find_root(self, a):
    if a not in self.roots:
      self.nums[a] = 1
      return a
    else:
      self.roots[a] = self.find_root(self.roots[a])
      return self.roots[a]

  def unite(self, a, b):
    root_a = self.find_root(a)
    root_b = self.find_root(b)
    n_a = self.nums[root_a]
    n_b = self.nums[root_b]
    if root_a == root_b:
      return
    else:
      if n_a > n_b: #多い方に合流させる
        self.roots[root_b] = root_a
        self.nums[root_a] = n_a + n_b
        del self.nums[root_b]
      else:
        self.roots[root_a] = root_b
        self.nums[root_b] = n_a + n_b
        del self.nums[root_a]
      return
  
  def is_union(self, a,b):
    return self.find_root(a) == self.find_root(b)

N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

answer = 0
for i in range(N):
  temp = AB[:i] + AB[i+1:]
  ai, bi = AB[i]
  uf = UnionFind()
  for ab in temp:
    a,b = ab
    uf.unite(a,b)
  answer += not uf.is_union(ai, bi)


print(answer)

Fixed submission:
class UnionFind():
  def __init__(self):
    self.roots = {}
    self.nums = {}

  def find_root(self, a):
    if a not in self.roots:
      self.nums[a] = 1
      return a
    else:
      self.roots[a] = self.find_root(self.roots[a])
      return self.roots[a]

  def unite(self, a, b):
    root_a = self.find_root(a)
    root_b = self.find_root(b)
    n_a = self.nums[root_a]
    n_b = self.nums[root_b]
    if root_a == root_b:
      return
    else:
      if n_a > n_b: #多い方に合流させる
        self.roots[root_b] = root_a
        self.nums[root_a] = n_a + n_b
        del self.nums[root_b]
      else:
        self.roots[root_a] = root_b
        self.nums[root_b] = n_a + n_b
        del self.nums[root_a]
      return
  
  def is_union(self, a,b):
    return self.find_root(a) == self.find_root(b)

N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

answer = 0
for i in range(M):
  temp = AB[:i] + AB[i+1:]
  ai, bi = AB[i]
  uf = UnionFind()
  for ab in temp:
    a,b = ab
    uf.unite(a,b)
  answer += not uf.is_union(ai, bi)


print(answer)
Buggy python submission (verdict: Runtime Error):
N=int(input())

for h in range(N//4, min(3501, 3*N//4 +1)):
  for n in range((N*h)//(4*h-N), min(3501, (2*N*h)//(4*h-N))):
    x = 4*h*n - N*n - N*h
    y = N*h*n
    if x>0 and not y%x:
      print('{} {} {}'.format(h,n,y//x))
      exit()

Fixed submission:
N=int(input())

if N==2:
  print('1 2 2')
  exit()

for h in range(N//4 +1, min(3501, 3*N//4 +1)):
  for n in range((N*h)//(4*h-N), min(3501, (2*N*h)//(4*h-N))):
    x = 4*h*n - N*n - N*h
    y = N*h*n
    if x>0 and not y%x:
      print('{} {} {}'.format(h,n,y//x))
      exit()

Buggy python submission (verdict: Runtime Error):
N=int(input())

for h in range(N//4, min(3501, 3*N//4 +1)):
  for n in range((N*h)//(4*h-N), min(3501, (2*N*h)//(4*h-N))):
    x = 4*h*n - N*n - N*h
    y = N*h*n
    if x<=0 or y%x:
      continue
    else:
      print('{} {} {}'.format(h,n,y//x))
      exit()

Fixed submission:
N=int(input())

if N==2:
  print('1 2 2')
  exit()

for h in range(N//4 +1, min(3501, 3*N//4 +1)):
  for n in range((N*h)//(4*h-N), min(3501, (2*N*h)//(4*h-N))):
    x = 4*h*n - N*n - N*h
    y = N*h*n
    if x>0 and not y%x:
      print('{} {} {}'.format(h,n,y//x))
      exit()

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

for h in range(1,3501):
  for n in range(1,3501):
    x = 4*h*n - N*n - N*h
    y = N*h*n
    if x<=0 or y%x:
      continue
    else:
      print('{} {} {}'.format(h,n,y//x))
      exit()

Fixed submission:
N=int(input())

if N==2:
  print('1 2 2')
  exit()

for h in range(N//4 +1, min(3501, 3*N//4 +1)):
  for n in range((N*h)//(4*h-N), min(3501, (2*N*h)//(4*h-N))):
    x = 4*h*n - N*n - N*h
    y = N*h*n
    if x>0 and not y%x:
      print('{} {} {}'.format(h,n,y//x))
      exit()
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int, input().split()))

temp_set=set()

l = []

for a in A:
  if a in temp_set:
    l.append(a)
    temp_set.remove(a)
  else:
    temp_set.add(a)
    
l.sort()
print(l[-2]*l[-1])

Fixed submission:
N=int(input())
A=list(map(int, input().split()))

temp_set=set()

l = []

for a in A:
  if a in temp_set:
    l.append(a)
    temp_set.remove(a)
  else:
    temp_set.add(a)
    
l.sort()
if len(l)>=2:
  print(l[-2]*l[-1])
else:
  print(0)
Buggy python submission (verdict: Runtime Error):
N=int(input())
T = [int(input()) for _ in range(N)]

from functools import reduce
from fraction import gcd

def lcm(a,b):
  return a*b //gcd(a,b)

print(reduce(lcm, T))
  

Fixed submission:
N=int(input())
T = [int(input()) for _ in range(N)]

from functools import reduce
from fractions import gcd

def lcm(a,b):
  return a*b //gcd(a,b)

print(reduce(lcm, T))
Buggy python submission (verdict: Runtime Error):
N=int(input())
S=[int(input()) for _ in range(N)]

if sum(S)%10:
  print(sum(s))
  exit()

min_s1=101

for s in S:
  if s%10:
    min_s1 = min(s, min_s1)

print(sum(S) - min_s1)

Fixed submission:
N=int(input())
S=[int(input()) for _ in range(N)]

if sum(S)%10:
  print(sum(S))
  exit()

else:
  S.sort()
  for s in S:
    if s%10:
      print(sum(S) - s)
      exit()
  else:
    print(0)
Buggy python submission (verdict: Time Limit Exceeded):
N,A,B=list(map(int,input().split()))
H = [int(input()) for _ in range(N)]

def can_eliminate(n): #O(N)
  H_ = [((h-B*n)+A-B-1)//(A-B) for h in H if h>B*n]
  if sum(H_)<=n:
    #print('can eliminate by ' + str(n) +'times')
    return True
  else:
    #print('can not eliminate by ' + str(n) +'times')
    return False
    
def binary_search(l,r): #r:inclusive
  #print('search between ' + str((l,r)))
  if can_eliminate(l):
    return l
  if r==l+1:
    return r
  
  c = (l+r)//2
  if can_eliminate(c):
    return binary_search(l,c)
  else:
    return binary_search(c,r)
  
print(binary_search(1, (sum(H)+2*B+1)//B))

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

def can_eliminate(n): #O(N)
  H_ = [((h-B*n)+A-B-1)//(A-B) for h in H if h>B*n]
  if sum(H_)<=n:
    #print('can eliminate by ' + str(n) +'times')
    return True
  else:
    #print('can not eliminate by ' + str(n) +'times')
    return False
    
def binary_search(l,r): #r:inclusive
  #print('search between ' + str((l,r)))
  if r==l+1:
    if can_eliminate(l):
      return l
    else:
      return r
  
  c = (l+r)//2
  if can_eliminate(c):
    return binary_search(l,c)
  else:
    return binary_search(c,r)
  
print(binary_search(1, (sum(H)+2*B+1)//B))