Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
c = Counter(A)
hs = []
for k,v in c.items():
  if v == 1:
    hs.append(k)
  elif v >= 2:
    hs.append(k)
    hs.append(k)
    
    
ts = []    
for cmb in combinations(hs,2):
  ts.append(sum(cmb))
  
ts = list(set(ts))

ans = 0
for h in ts:
  for i in range(n-h):    
    if abs(A[i]+A[i+h]) == h:
      ans += 1
      
print(ans)

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

X = {}
ans = 0
for i in range(n):
  L = i+A[i]
  R = i-A[i]
  
  if L not in X:
    X[L] = 0
    
  X[L]+=1
  
  if R in X:
    ans += X[R]
    
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
c = Counter(A)
hs = []
for k,v in c.items():
  if v == 1:
    hs.append(k)
  elif v >= 2:
    hs.append(k)
    hs.append(k)
    
    
ts = []    
for cmb in combinations(hs,2):
  ts.append(sum(cmb))
  
ts = list(set(ts))

ans = 0
for h in ts:
  for i in range(n-h):    
    if abs(A[i]+A[i+h]) == h:
      ans += 1
      
print(ans)

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

X = {}
ans = 0
for i in range(n):
  L = i+A[i]
  R = i-A[i]
  
  if L not in X:
    X[L] = 0
    
  X[L]+=1
  
  if R in X:
    ans += X[R]
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from math import floor

def f(x):
  return floor(a*x/b) - a*floor(x/b)

a,b,n = map(int,input().split())
ans = 0
for i in range(min(b-1,n)):
  ans = max(ans,f(i+1))
  
print(ans)  

Fixed submission:
from math import floor

def f(x):
  return floor(a*x/b) - a*floor(x/b)

a,b,n = map(int,input().split())    
print(f(min(b-1,n)))
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(a,b):
  ret = d[a][b]
  if ret != 0:
    return ret
  while b:
    a,b = b,a%b
  d[a][b] = a
  d[b][a] = a
  
  return a

def gcd2(A):    
  ret = gcd(gcd(A[0],A[1]),A[2])    
  return ret

n = int(input())

d = [[0]*(n+1) for _ in range(n+1)]

ans = 0
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      ans += gcd(gcd(i,j),k)

print(ans)

Fixed submission:
def gcd(a,b):
  ret = d[a][b]
  if ret != 0:
    return ret
  while b:
    a,b = b,a%b
  d[a][b] = a
  d[b][a] = a
  
  return a

def gcd2(A):    
  ret = gcd(gcd(A[0],A[1]),A[2])    
  return ret

n = int(input())

d = [[0]*(n+1) for _ in range(n+1)]

ans = 0
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      ans += gcd(gcd(i,j),k)

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

rc = s.count('R')
gc = s.count('G')
bc = s.count('B')
ans = rc * gc * bc

for i in range(n-1):
  for j in range(i+1,n):
    k = j*2 - i
    if k >= n:
      continue
    if len(set([s[i],s[j],s[k]])) == 3:
      ans -= 1
      
print(ans)      

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

rc = s.count('R')
gc = s.count('G')
bc = s.count('B')
ans = rc * gc * bc

for i in range(n-1):
  for j in range(i+1,n):
    k = j*2 - i
    if k >= n:
      continue
    if len(set([s[i],s[j],s[k]])) == 3:
      ans -= 1
      
print(ans)
Buggy python submission (verdict: Runtime Error):
MOD = 10**9+7
n,k = map(int,input().split())

L = [0]*(k+1)

for i in range(k,0,-1):    
  L[i] = pow(k//i,n,mod)
  for j in range(2,k//i+1):        
    L[i] -= L[i*j]
  
ans = 0
for i in range(1,k+1):  
  ans = (ans + i*L[i]) % MOD
  
print(ans)  

Fixed submission:
MOD = 10**9+7
n,k = map(int,input().split())

L = [0]*(k+1)

for i in range(k,0,-1):    
  L[i] = pow(k//i,n,MOD)
  for j in range(2,k//i+1):        
    L[i] -= L[i*j]
  
ans = 0
for i in range(1,k+1):  
  ans = (ans + i*L[i]) % MOD
  
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k,c = map(int,input().split())
s = list(input())

ans = []
for i in range(n):
  
  save = s[i]
  s[i] = 'x'
  count = 0
  j = 0
  while j < n:  
    if s[j] == 'o':
      count += 1
      j += c+1
    else:
      j += 1  
      
  if count < k:
    ans.append(i+1) 
    
  s[i] = save
  
for a in ans:
  print(a)

Fixed submission:
n,k,c = map(int,input().split())
s = list(input())

L = []
R = []

i = -1
j = n  

for ki in range(k):
  while i < n:
    i += 1
    if s[i] == 'o':           
      L += [i]
      i += c
      break

for ki in range(k):      
  while 0 <= j:
    j -= 1
    if s[j] == 'o':          
      R += [j]
      j -= c
      break
      
for i in range(k):
  if L[i] == R[-i-1] :
    print(L[i]+1)
Buggy python submission (verdict: Time Limit Exceeded):
n,x,y = map(int,input().split())
INF = 10**5
d = [[INF]*n for _ in range(n)]
def wf(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j],d[i][k] + d[k][j])

for i in range(n-1):
  d[i][i+1] = 1
  d[i+1][i] = 1
  
d[x-1][y-1]=1
d[y-1][x-1]=1
wf(d)

ans = [0]*(n-1)
for i in range(n-1):
  for j in range(i+1,n):
    ans[d[i][j]-1]+=1

for a in ans:
  print(a)

Fixed submission:
n,x,y = map(int,input().split())
x,y = x-1,y-1
ans = [0]*(n)

for i in range(n):    
  for j in range(i+1,n):
    sp = min(abs(j-i), abs(x-i)+abs(j-y)+1, abs(y-i)+1+abs(j-x))
    ans[sp]+=1
    
for a in ans[1:]:
  print(a)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

h,w = map(int,input().split())
F = [input() for _ in range(h)]
direct = [[0,1],[1,0]]
que = deque()
que.append([0,0])
INF = 10**5
dp = [[INF]*w for _ in range(h)]


dp[0][0] = 0

while len(que)>0:  
  x,y = que.pop()    
  for dy,dx in direct:    
    ny = y+dy
    nx = x+dx
    if (0 <= nx < w) and (0 <= ny < h):
      if F[ny][nx] == F[y][x]:        
        if dp[ny][nx] >= dp[y][x]:
          dp[ny][nx] = dp[y][x]
          que.append([ny,nx])
      else:        
        if dp[ny][nx] >= dp[y][x] + 1 :        
          dp[ny][nx] = dp[y][x] + 1          
          que.append([ny,nx])   

ans = (dp[-1][-1]+1)//2
if F[0][0] == '#':
  ans += 1
print(ans)

Fixed submission:
from collections import deque

h,w = map(int,input().split())
F = [input() for _ in range(h)]
direct = [[0,1],[1,0]]
que = deque()
que.append([0,0])
INF = 10**5
dp = [[INF]*w for _ in range(h)]


dp[0][0] = 0

while len(que)>0:  
  y,x = que.popleft()    
  for dy,dx in direct:    
    ny = y+dy
    nx = x+dx
    if (0 <= nx < w) and (0 <= ny < h):
      if F[ny][nx] == F[y][x]:         
        if dp[ny][nx] > dp[y][x]:
          dp[ny][nx] = dp[y][x]
          que.append([ny,nx])
      else:                
        if dp[ny][nx] > dp[y][x] + 1 :        
          dp[ny][nx] = dp[y][x] + 1          
          que.append([ny,nx])   


ans = dp[-1][-1]//2
if F[0][0] == '#' or F[-1][-1] == '#':
  ans += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

h,w = map(int,input().split())
F = [input() for _ in range(h)]
direct = [[0,1],[1,0]]
que = deque()
que.append([0,0])
INF = 10**5
dp = [[INF]*w for _ in range(h)]


dp[0][0] = 0

while len(que)>0:  
  x,y = que.pop()    
  for dy,dx in direct:    
    ny = y+dy
    nx = x+dx
    if (0 <= nx < w) and (0 <= ny < h):
      if F[ny][nx] == F[y][x]:        
        if dp[ny][nx] >= dp[y][x]:
          dp[ny][nx] = dp[y][x]
          que.append([ny,nx])
      else:        
        if dp[ny][nx] >= dp[y][x] + 1 :        
          dp[ny][nx] = dp[y][x] + 1          
          que.append([ny,nx])   

ans = (dp[-1][-1]+1)//2
if F[0][0] == '#':
  ans += 1
print(ans)

Fixed submission:
from collections import deque

h,w = map(int,input().split())
F = [input() for _ in range(h)]
direct = [[0,1],[1,0]]
que = deque()
que.append([0,0])
INF = 10**5
dp = [[INF]*w for _ in range(h)]


dp[0][0] = 0

while len(que)>0:  
  y,x = que.popleft()    
  for dy,dx in direct:    
    ny = y+dy
    nx = x+dx
    if (0 <= nx < w) and (0 <= ny < h):
      if F[ny][nx] == F[y][x]:         
        if dp[ny][nx] > dp[y][x]:
          dp[ny][nx] = dp[y][x]
          que.append([ny,nx])
      else:                
        if dp[ny][nx] > dp[y][x] + 1 :        
          dp[ny][nx] = dp[y][x] + 1          
          que.append([ny,nx])   


ans = dp[-1][-1]//2
if F[0][0] == '#' or F[-1][-1] == '#':
  ans += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = list(input())
q = int(input())
mode = 0
for i in range(q):
  read = list(map(str,input().split()))
  if read[0]=='1':
    mode = (mode+1)%2
  else:
    if (read[1]=='1' and mode == 0) or (read[1]=='2' and mode == 1):
      s = [read[2]]+ s
    else:
      s = s + [read[2]]
if mode == 0:
  print(''.join(s))
else:
  print(''.join(s[::-1]))

Fixed submission:
s = list(input())
q = int(input())

head = []
tail = []

mode = 0
for i in range(q):
  read = list(map(str,input().split()))
  if read[0]=='1':
    mode = (mode+1)%2
  else:
    if (read[1]=='1' and mode == 0) or (read[1]=='2' and mode == 1):
      head.append(read[2])
    else:
      tail.append(read[2])

s = head[::-1] + s
s = s + tail
if mode == 0:
  print(''.join(s))
else:
  print(''.join(s[::-1]))
Buggy python submission (verdict: Runtime Error):
from collections import Counter

def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= (n-i)
    ret //= i+1
  return ret    

n,p = map(int,input().split())
s = input()

ans = 0
if p == 2 or p == 5:
  for i in range(n):
    if int(s[i]) % p == 0:
      ans += (i+1)
      
else:      
  mods = [0]*(n+1)
  mods[0] = 1
  m = 0
  d = 1  
  for i in range(n):    
    m = (m + int(s[-i-1])*d) % p
    d = (d * 10) % p    
    mods[m] += 1
  
  for i in range(n):
    ans += mods[i]*(mods[i]-1)//2

print(ans)      

Fixed submission:
from collections import Counter

n,p = map(int,input().split())
s = input()

ans = 0
if p == 2 or p == 5:
  for i in range(n):
    if int(s[i]) % p == 0:
      ans += (i+1)

else:      
  mods = [0]*p
  mods[0] = 1
  m = 0
  d = 1  
  for i in range(n):
    m = (m + int(s[-i-1])*d) % p
    d = (d * 10) % p    
    mods[m] += 1
  
  for i in range(p):
    ans += mods[i]*(mods[i]-1)//2

print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import Counter

def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= (n-i)
    ret //= i+1
  return ret    

n,p = map(int,input().split())
s = input()

ans = 0
if p == 2 or p == 5:
  for i in range(n):
    if int(s[i]) % p == 0:
      ans += (i+1)
      
else:      
  mods = [0]*(n+1)
  mods[0] = 1
  m = 0
  d = 1  
  for i in range(n):    
    m = (m + int(s[-i-1])*d) % p
    d = (d * 10) % p    
    mods[m] += 1
  
  for i in range(p+1):
    ans += mods[i]*(mods[i]-1)//2

print(ans)      

Fixed submission:
from collections import Counter

n,p = map(int,input().split())
s = input()

ans = 0
if p == 2 or p == 5:
  for i in range(n):
    if int(s[i]) % p == 0:
      ans += (i+1)

else:      
  mods = [0]*p
  mods[0] = 1
  m = 0
  d = 1  
  for i in range(n):
    m = (m + int(s[-i-1])*d) % p
    d = (d * 10) % p    
    mods[m] += 1
  
  for i in range(p):
    ans += mods[i]*(mods[i]-1)//2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= (n-i)
    ret //= i+1
  return ret    

n,p = map(int,input().split())
s = input()

ans = 0
if p == 2:
  for i in range(n):
    if int(s[i])%2 == 0:
      ans += (i+1)
      
elif p == 5:
  for i in range(n):
    if int(s[i])%5 == 0:
      ans += (i+1)
      
else:      
  mods = [0]*(n+1)
  t = ''
  for i in range(n):
    t = s[-i-1] + t
    mods[i] = int(t)%p    
  c = Counter(mods)
  for k,v in c.items():
    if v > 1:
      ans += nCr(v,2)

print(ans)      

Fixed submission:
from collections import Counter

n,p = map(int,input().split())
s = input()

ans = 0
if p == 2 or p == 5:
  for i in range(n):
    if int(s[i]) % p == 0:
      ans += (i+1)

else:      
  mods = [0]*p
  mods[0] = 1
  m = 0
  d = 1  
  for i in range(n):
    m = (m + int(s[-i-1])*d) % p
    d = (d * 10) % p    
    mods[m] += 1
  
  for i in range(p):
    ans += mods[i]*(mods[i]-1)//2

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

F = [0]*100
for b in B:
  F[b]=1

ans = 'No'  
for i in range(3):
  c = 0
  d = 0
  for j in range(3):    
    c += F[A[i][j]]
    d += F[A[j][i]]
  if c==3 or d==3:
    ans ='Yes'
if F[A[0][0]]+F[A[1][1]]+F[A[2][2]] == 3 or F[A[0][2]]+F[A[1][1]]+F[A[2][0]] == 3:
  ans ='Yes'
  
print(ans)

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

F = [0]*101
for b in B:
  F[b]=1

ans = 'No'  
for i in range(3):
  c = 0
  d = 0
  for j in range(3):    
    c += F[A[i][j]]
    d += F[A[j][i]]
  if c==3 or d==3:
    ans ='Yes'
if F[A[0][0]]+F[A[1][1]]+F[A[2][2]] == 3 or F[A[0][2]]+F[A[1][1]]+F[A[2][0]] == 3:
  ans ='Yes'
  
print(ans)

Buggy python submission (verdict: Runtime Error):
A = [list(map(int,input().split())) for _ in range(3)]
n = int(input())
B = [int(input()) for _ in range(n)]

F = [0]*100
for b in B:
  F[b]=1

ans = 'No'  
for i in range(3):
  c = 0
  d = 0
  for j in range(3):    
    c += F[A[i][j]]
    c += F[A[j][i]]
  if c==3 or d==3:
    ans ='Yes'
if F[A[0][0]]+F[A[1][1]]+F[A[2][2]] == 3 or F[A[0][2]]+F[A[1][1]]+F[A[2][0]] == 3:
  ans ='Yes'
  
print(ans)

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

F = [0]*101
for b in B:
  F[b]=1

ans = 'No'  
for i in range(3):
  c = 0
  d = 0
  for j in range(3):    
    c += F[A[i][j]]
    d += F[A[j][i]]
  if c==3 or d==3:
    ans ='Yes'
if F[A[0][0]]+F[A[1][1]]+F[A[2][2]] == 3 or F[A[0][2]]+F[A[1][1]]+F[A[2][0]] == 3:
  ans ='Yes'
  
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,a,b = map(int,input().split())

MOD = 10**9 + 7
m = 2*10**5
mm = 2** m

def cmb(n,r,mod):        
    ret=1
    div = min(r,n-r)
    for i in range(div):        
        ret=ret*(n-i)*pow(div-i,mod-2,mod)%mod
        
    return ret % mod

ans = 1
for _ in range(n // m):
  ans = (ans * mm) % MOD

ans = (ans * 2**(n % m)) % MOD  
    
ans = (ans - 1) % MOD

ans = (ans - cmb(n,a,MOD))%MOD
ans = (ans - cmb(n,b,MOD))%MOD

print(ans)

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

MOD = 10**9+7

def cmb(n,r,mod):        
    ret=1
    div = min(r,n-r)
    for i in range(div):        
        ret=ret*(n-i)*pow(div-i,mod-2,mod)%mod
        
    return ret % mod

ans = 1
ans = ans * pow(2,n,MOD)
ans = (ans - 1) % MOD

ans = (ans - cmb(n,a,MOD))%MOD
ans = (ans - cmb(n,b,MOD))%MOD

print(ans)

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

MOD = 10**9 + 7
m = 2*10**5
mm = 2** m

ans = 1
for _ in range(n // m):
  ans = (ans * mm) % MOD

ans = (ans * 2**(n % m)) % MOD  
    
ans = (ans - 1) % MOD

ans = (ans - cmb(n,a,MOD))%MOD
ans = (ans - cmb(n,b,MOD))%MOD

print(ans)

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

MOD = 10**9+7

def cmb(n,r,mod):        
    ret=1
    div = min(r,n-r)
    for i in range(div):        
        ret=ret*(n-i)*pow(div-i,mod-2,mod)%mod
        
    return ret % mod

ans = 1
ans = ans * pow(2,n,MOD)
ans = (ans - 1) % MOD

ans = (ans - cmb(n,a,MOD))%MOD
ans = (ans - cmb(n,b,MOD))%MOD

print(ans)
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
P = list(map(int,input().split()))

P = [(v+1)/2 for v in P]

acum = [0]*(n+1)
for i in range(n):
  acum[i+1] = acum[i] + P[i]
  
total = [0]*k
for i in range(k):
  total[i] = acum[i+k]-acum[i]  
  
print(max(total))  

Fixed submission:
n,k = map(int,input().split())
P = list(map(int,input().split()))

P = [(v+1)/2 for v in P]

acum = [0]*(n+1)
for i in range(n):
  acum[i+1] = acum[i] + P[i]
  
total = [0]*(n-k+1)
for i in range(n-k+1):
  total[i] = acum[i+k]-acum[i]  
  
print(max(total))
Buggy python submission (verdict: Time Limit Exceeded):
h,n = map(int,input().split())
a=[0]*n
b=[0]*n

MAX_HP = 10**4
MAX_HP = h
for i in range(n):
  ta,tb = map(int,input().split())
  a[i] = ta
  b[i] = tb

INF = 10**9

dp = [[INF]*(h+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
  for j in range(h+1):    
    dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    dp[i+1][min(j+a[i],h)] = min(dp[i+1][min(j+a[i],h)], dp[i+1][j] + b[i])    

print(dp[-1][-1])  

Fixed submission:
h,n = map(int,input().split())
a=[0]*n
b=[0]*n

MAX_HP = 10**4
MAX_HP = h
for i in range(n):
  ta,tb = map(int,input().split())
  a[i] = ta
  b[i] = tb

INF = 10**9

dp = [[INF]*(h+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
  for j in range(h+1):    
    dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    dp[i+1][min(j+a[i],h)] = min(dp[i+1][min(j+a[i],h)], dp[i+1][j] + b[i])    

print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
xl=[list(map(int,input().split())) for _ in range(n)]
xl = sorted(xl)

ans = 0
for i in range(n):
  count = 1
  right = xl[i][0] + xl[i][1]
  for j in range(i+1,n):
    if right <= xl[j][0] - xl[j][1] :
      count += 1
      right = xl[j][0] + xl[j][1] 
  ans = max(ans,count)

print(ans)    

Fixed submission:
n = int(input())

itv = []
for i in range(n):
  tx,tl = map(int,input().split())  
  itv.append([tx+tl,tx-tl] )

itv = sorted(itv)

ans = 0
right = float('-inf')

for i in range(n):  
  if right <= itv[i][1]:    
    ans += 1
    right = itv[i][0]
    
print(ans)
Buggy python submission (verdict: Runtime Error):
a,b,k = map(int,input().split())

ans_t = max(a-k,0)
if a-k < 0:
  ans_a = max(b-(k-a),0)
print(ans_t,ans_a)  

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

ans_t = max(a-k,0)
if a-k < 0:
  b = max(b-(k-a),0)
print(ans_t,b)
Buggy python submission (verdict: Runtime Error):
def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

x = int(input())  
  
while not is_prime(x):
  x+=1
  
print(x)  

Fixed submission:
import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

x = int(input())  
  
while not is_prime(x):
  x+=1
  
print(x)
Buggy python submission (verdict: Runtime Error):
n,g,s = map(int,input().split())
G = [[] for _ in range(n)]
for i in range(n):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(V,v,d):
  if V[v] != -1:
    return
  V[v] = d
  for nv in G[v]:
    dfs(V,nv,d+1)
  
if len(G[g-1])==1 and G[g-1][0]==s-1:
  print(0)
else:
  vs = [-1]*n
  vg = [-1]*n
  dfs(vs,s-1,0)
  dfs(vg,g-1,0)
  
  ans = 0
  for i in range(n):
    if vs[i]>vg[i]:
      ans = max(ans,vs[i])
      
  print(ans-1)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)

n,g,s = map(int,input().split())
G = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(V,v,d):
  if V[v] != -1:
    return
  V[v] = d
  for nv in G[v]:
    dfs(V,nv,d+1)
  
if len(G[g-1])==1 and G[g-1][0]==s-1:
  print(0)
else:
  vs = [-1]*n
  vg = [-1]*n
  dfs(vs,s-1,0)
  dfs(vg,g-1,0)
  
  ans = 0
  for i in range(n):
    if vs[i]>vg[i]:
      ans = max(ans,vs[i])
      
  print(ans-1)

Buggy python submission (verdict: Runtime Error):
n,g,s = map(int,input().split())
G = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(V,v,d):
  if V[v] != -1:
    return
  V[v] = d
  for nv in G[v]:
    dfs(V,nv,d+1)
  
if len(G[g-1])==1 and G[g-1][0]==s-1:
  print(0)
else:
  vs = [-1]*n
  vg = [-1]*n
  dfs(vs,s-1,0)
  dfs(vg,g-1,0)
  
  ans = 0
  for i in range(n):
    if vs[i]>vg[i]:
      ans = max(ans,vs[i])
      
  print(ans-1)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)

n,g,s = map(int,input().split())
G = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(V,v,d):
  if V[v] != -1:
    return
  V[v] = d
  for nv in G[v]:
    dfs(V,nv,d+1)
  
if len(G[g-1])==1 and G[g-1][0]==s-1:
  print(0)
else:
  vs = [-1]*n
  vg = [-1]*n
  dfs(vs,s-1,0)
  dfs(vg,g-1,0)
  
  ans = 0
  for i in range(n):
    if vs[i]>vg[i]:
      ans = max(ans,vs[i])
      
  print(ans-1)

Buggy python submission (verdict: Runtime Error):
n,g,s = map(int,input().split())
G = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(v,d):
  if vs[v] != -1:
    return
  vs[v] = d
  for nv in G[v]:
    dfs(nv,d+1)

def dfs2(v,d):
  if vg[v] != -1:
    return
  vg[v] = d
  if d >= vs[v]:
    return  
  for nv in G[v]:
    dfs2(nv,d+1)
  
vs = [-1]*n
vg = [-1]*n

dfs(s-1,0)
dfs2(g-1,0)

print(max(vg))

Fixed submission:
import sys
sys.setrecursionlimit(10**6)

n,g,s = map(int,input().split())
G = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(V,v,d):
  if V[v] != -1:
    return
  V[v] = d
  for nv in G[v]:
    dfs(V,nv,d+1)
  
if len(G[g-1])==1 and G[g-1][0]==s-1:
  print(0)
else:
  vs = [-1]*n
  vg = [-1]*n
  dfs(vs,s-1,0)
  dfs(vg,g-1,0)
  
  ans = 0
  for i in range(n):
    if vs[i]>vg[i]:
      ans = max(ans,vs[i])
      
  print(ans-1)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
aa = list(map(int,input().split()))

d = [0]*60
for ai in aa:
  for e,i in enumerate(bin(ai)[:1:-1]):
    d[e]+=int(i) 

ans = 0
for i in range(len(d)):
  if d[i]==0 or d[i]==n:
    pass
  else:     
    #print(d[i]*(n-d[i])* 2**(i))    
    ans += d[i]*(n-d[i])* 2**(i)
    ans %= (10**9+7)
    
print(ans)    

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

m = 1
ans = 0
for i in range(60):
  s = sum([a&m for a in A])
  s//=m
  ans = (ans + (n-s)*s * m) % MOD
  m <<= 1
  
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
aa = list(map(int,input().split()))

d = [0]*60
for ai in aa:
  for e,i in enumerate(bin(ai)[:1:-1]):
    d[e]+=int(i)  

ans = 0
for i in range(len(d)):
  if d[i]==0 or d[i]==n:
    pass
  else:     
    #print(d[i]*(n-d[i])* 2**(i))
    ans += d[i]*(n-d[i])* 2**(i)
    
print(ans % (10**9+7))    

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

m = 1
ans = 0
for i in range(60):
  s = sum([a&m for a in A])
  s//=m
  ans = (ans + (n-s)*s * m) % MOD
  m <<= 1
  
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
aa = list(map(int,input().split()))

ans = 0
for i in range(n-1):
  for j in range(i+1,n):
    ans += aa[i] ^ aa[j]    

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

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

m = 1
ans = 0
for i in range(60):
  s = sum([a&m for a in A])
  s//=m
  ans = (ans + (n-s)*s * m) % MOD
  m <<= 1
  
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()

ans = 0
for i in range(1000):
  pin = '{:03d}'.format(i)
  j = 0
  for si in s:
    if si == pin[j]:
      j+=1
      if j==3:
        break        
  if j == 3:
    ans+=1
    
print(ans)

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

ans = 0
for i in range(1000):
  pin = '{:03d}'.format(i)
  p1 = s.find(pin[0])
  if p1>=0:    
    p2 = s[p1+1:].find(pin[1])     
    if p2>=0:
      p3 = s[p1+p2+2:].find(pin[2])      
      if p3>=0:
        ans+=1        
    
print(ans)

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

ans = 0
set2d = set()

for d1 in range(n-2):
  for d2 in range(d1+1,n-1):    
    if s[d1]+s[d2] not in set2d:      
      set2d.add(s[d1]+s[d2])      
      ans +=len(set(s[d2+1:]))

print(ans)      

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

ans = 0
for i in range(1000):
  pin = '{:03d}'.format(i)
  p1 = s.find(pin[0])
  if p1>=0:    
    p2 = s[p1+1:].find(pin[1])     
    if p2>=0:
      p3 = s[p1+p2+2:].find(pin[2])      
      if p3>=0:
        ans+=1        
    
print(ans)