Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):

N,W = map(int,input().split())

lis = [ [0] * (W+1) ]


for i in range(N):

    w,v = map(int,input().split())

    new = [0] * (W+1)

    for j in range(W+1):

        new[j] = max(new[j],lis[-1][j])

        if j+w <= W:

            new[j+w] = max(new[j+w],lis[-1][j]+v)

    lis.append(new)

print (lis[-1][W])


Fixed submission:

N,W = map(int,input().split())

lis = [ [0] * (W+1) ]


for i in range(N):

    w,v = map(int,input().split())

    new = [0] * (W+1)

    for j in range(W+1):

        new[j] = max(new[j],lis[-1][j])

        if j+w <= W:

            new[j+w] = max(new[j+w],lis[-1][j]+v)

    lis.append(new)

print (lis[-1][W])

Buggy python submission (verdict: Time Limit Exceeded):

N,W = map(int,input().split())
lis = [[[0,0]]]

for i in range(N):

    w,v = map(int,input().split())

    new = []

    for j in lis[i]:

        if j[0] + w <= W:

            new.append([j[0] + w , j[1] + v])
            
        new.append([j[0] ,j[1]])

    lis.append(new)

ans = 0

for i in lis[-1]:

    ans = max( ans , i[1] )

print (ans)


Fixed submission:

N,W = map(int,input().split())

lis = [ [0] * (W+1) ]


for i in range(N):

    w,v = map(int,input().split())

    new = [0] * (W+1)

    for j in range(W+1):

        new[j] = max(new[j],lis[-1][j])

        if j+w <= W:

            new[j+w] = max(new[j+w],lis[-1][j]+v)

    lis.append(new)

print (lis[-1][W])

Buggy python submission (verdict: Time Limit Exceeded):

N,W = map(int,input().split())
lis = [[[0,0]]]

for i in range(N):

    w,v = map(int,input().split())

    new = []

    for j in lis[i]:

        if j[0] + w <= W:

            new.append([j[0] + w , j[1] + v])
            
        new.append([j[0] ,j[1]])

    lis.append(new)

ans = 0

for i in lis[-1]:

    ans = max( ans , i[1] )

print (ans)


Fixed submission:

N,W = map(int,input().split())

lis = [ [0] * (W+1) ]


for i in range(N):

    w,v = map(int,input().split())

    new = [0] * (W+1)

    for j in range(W+1):

        new[j] = max(new[j],lis[-1][j])

        if j+w <= W:

            new[j+w] = max(new[j+w],lis[-1][j]+v)

    lis.append(new)

print (lis[-1][W])
Buggy python submission (verdict: Time Limit Exceeded):

N,W = map(int,input().split())

wv = []
vmax = 0

for i in range(N):

    w,v = map(int,input().split())

    vmax += v
    wv.append([w,v])


lis = [[0] + [float("inf")] * vmax]

for i in wv:

    new = [0] + [float("inf")] * vmax

    for j in range(vmax+1):

        new[j] = min(new[j] , lis[-1][j])

        if j + i[1] <= vmax:

            new[j + i[1]] = min (new[j + i[1]] , lis[-1][j] + i[0])

    lis.append(new)

#print (lis)

lis[-1].reverse()

for i in range(vmax+1):

    if lis[-1][i] <= W:
        print (vmax - i)
        break

    

Fixed submission:

N,W = map(int,input().split())

wv = []
vmax = 0

for i in range(N):

    w,v = map(int,input().split())

    vmax += v
    wv.append([w,v])


lis = [[0] + [float("inf")] * vmax]

for i in wv:

    new = [0] + [float("inf")] * vmax

    for j in range(vmax+1):

        new[j] = min(new[j] , lis[-1][j])

        if j + i[1] <= vmax:

            new[j + i[1]] = min (new[j + i[1]] , lis[-1][j] + i[0])

    lis.append(new)

#print (lis)

lis[-1].reverse()

for i in range(vmax+1):

    if lis[-1][i] <= W:
        print (vmax - i)
        break
Buggy python submission (verdict: Runtime Error):
N,H,W = map(int,input().split())
     
ans = 0
     
for i in range(N):
  A,B = map(int,input().split())
  if (A => H) and (B => W):
     ans += 1
        
print (ans)


Fixed submission:
N,H,W = map(int,input().split())
     
ans = 0
     
for i in range(N):
  A,B = map(int,input().split())

  #print (A,H,B,W)
  if (A >= H) and (B >= W):
     ans += 1
        
print (ans)
Buggy python submission (verdict: Runtime Error):
import sys

N,P = map(int,input().split())

if N == 1:
    print (P)
    sys.exit()

lis = []
dic = {}

i = 1
while i ** N < 10 ** 12:

    flag = True
    for j in lis:
        if i % j == 0:
            flag = False
            break
    
    if flag and i != 1:
        lis.append(i)
        dic[i] = 0

        while P % i == 0:
            P //= i
            dic[i] += 1

    i += 1


ans = 1
#print (dic)

for i in dic:

    if dic[i] != 0:
        ans *= i ** (dic[i]//N)

print (ans)


Fixed submission:
import sys

N,P = map(int,input().split())

if N == 1:
    print (P)
    sys.exit()

lis = []
dic = {}

i = 1
while True:

    flag = True
    now = 1
    if i > 1:
        for j in range(N):
            now *= i
            if now > P:
                flag = False
                break
        if not flag:
            break

    flag = True
    for j in lis:
        if i % j == 0:
            flag = False
            break
    
    if flag and i != 1:
        lis.append(i)
        dic[i] = 0

        while P % i == 0:
            P //= i
            dic[i] += 1

    i += 1


ans = 1
#print (dic)

for i in dic:

    if dic[i] != 0:
        ans *= i ** (dic[i]//N)

print (ans)

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

N,P = map(int,input().split())

if N == 1:
    print (P)
    sys.exit()

lis = [2]

i = 2
while i ** N < 10 ** 12:

    flag = True
    for j in lis:
        if i % j == 0:
            flag = False
            break
    
    if flag:
        lis.append(i)

    i += 1

dic = {}

for i in lis:

    dic[i] = 0

    while P % i == 0:
        P //= i
        dic[i] += 1

ans = 1

for i in dic:

    if dic[i] != 0:
        ans *= i ** (dic[i]//N)

print (ans)


Fixed submission:
import sys

N,P = map(int,input().split())

if N == 1:
    print (P)
    sys.exit()

lis = []
dic = {}

i = 1
while True:

    flag = True
    now = 1
    if i > 1:
        for j in range(N):
            now *= i
            if now > P:
                flag = False
                break
        if not flag:
            break

    flag = True
    for j in lis:
        if i % j == 0:
            flag = False
            break
    
    if flag and i != 1:
        lis.append(i)
        dic[i] = 0

        while P % i == 0:
            P //= i
            dic[i] += 1

    i += 1


ans = 1
#print (dic)

for i in dic:

    if dic[i] != 0:
        ans *= i ** (dic[i]//N)

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

N = int(input())
A = []
B = []

for i in range(N):

    a = int(input())

    A.append(a)

A.sort()

now = A.pop(0)
L = now
R = now
ans = 0

for i in range(N-1):

    if abs(L-A[0]) == max(abs(L-A[0]),abs(L-A[-1]),abs(R-A[0]),abs(R-A[-1])):
        ans += abs(L-A[0])
        L = A[0]
        A.pop(0)

    elif abs(L-A[-1]) == max(abs(L-A[0]),abs(L-A[-1]),abs(R-A[0]),abs(R-A[-1])): 
        ans += abs(L-A[-1])
        L = A[-1]
        A.pop(-1)

    elif abs(R-A[0]) == max(abs(L-A[0]),abs(L-A[-1]),abs(R-A[0]),abs(R-A[-1])):
        ans += abs(R-A[0])
        R = A[0]
        A.pop(0)

    elif abs(R-A[-1]) == max(abs(L-A[0]),abs(L-A[-1]),abs(R-A[0]),abs(R-A[-1])):
        ans += abs(R-A[-1])
        R = A[-1]
        A.pop(-1)

    else:
        print ("eeror")

    #print (A,L,R,ans)

print (ans)

Fixed submission:
from collections import deque

N = int(input())
A = []
B = []

for i in range(N):

    a = int(input())

    A.append(a)

A.sort()

now = A.pop(0)
L = now
R = now
ans = 0
Lind = 0
Rind = -1

for i in range(N-1):

    if abs(L-A[Lind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])):
        ans += abs(L-A[Lind])
        L = A[Lind]
        Lind += 1

    elif abs(L-A[Rind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])): 
        ans += abs(L-A[Rind])
        L = A[Rind]
        Rind -= 1

    elif abs(R-A[Lind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])):
        ans += abs(R-A[Lind])
        R = A[Lind]
        Lind += 1

    elif abs(R-A[Rind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])):
        ans += abs(R-A[Rind])
        R = A[Rind]
        Rind -= 1

    else:
        print ("eeror")

    #print (A,L,R,ans)

print (ans)
Buggy python submission (verdict: Runtime Error):

n = input()

v = list(map(int,input().split()))

eve = []
odd = []

for i in range(len(v)):

    if (i % 2 == 1):
        eve.append(v[i])
    else:
        odd.append(v[i])

dic_o = {}
dic_e = {}

dic_o[-1] = 0
dic_e[-1] = 0
#print (dic_o)

for i in odd:

    if ( i in dic_o.keys() ):
        dic_o[i] += 1
    else:
        dic_o[i] = 1


for i in eve:

    if ( i in dic_e.keys() ):
        dic_e[i] += 1
    else:
        dic_e[i] = 1

omax = -1
emax = -1
bul = True

while bul:

    for i in dic_o:
        
        if omax < 0:
            omax = i
        
        elif dic_o[i] > dic_o[omax] :
            omax = i

    for i in dic_e:

        if emax < 0:
            emax = i
        
        elif dic_e[i] > dic_e[emax] :
            emax = i

    if omax != emax :
        bul = False

    else:

        print(dic_o,dic_e)
        
        flag = True
        
        for i in dic_e:
            if dic_e[i] == dic_e[emax] and i != emax:
                emax = i
                flag = False

        if flag:
            for i in dic_o:
                if dic_o[i] == dic_o[emax] and i != omax:
                    omax = i
                    flag = False

        if flag:
        
            if dic_o[omax] > dic_e[emax]:
        
                dic_e.pop(emax)
                emacs = -1

            else:

                dic_o.pop(omax)
                emacs = -1

    
emax_n = dic_e[emax]
omax_n = dic_o[omax]

#print (dic_o,dic_e)
#print (omax,emax)
print ( (len(odd) - omax_n) + (len(eve) - emax_n))


Fixed submission:

n = int(input())
odd = {}
eve = {}

nums = list(map(int,input().split()))

for i in range(n):
    
    new_v = nums[i]
    
    if (i % 2 == 0):

        if new_v in odd:
            odd[new_v] += 1

        else:
            odd[new_v] = 1

    else:

        if new_v in eve:
            eve[new_v] += 1

        else:
            eve[new_v] = 1



odd_m = max(odd , key=odd.get)
eve_m = max(eve , key=eve.get)

odd_c = odd.copy()
eve_c = eve.copy()

del odd_c[odd_m]
del eve_c[eve_m]

if len(odd_c) == 0:
    odd_mt = 0
else:
    odd_mt = max(odd_c , key=odd.get)

if len(eve_c) == 0:
    eve_mt = 0
else:
    eve_mt = max(eve_c , key=eve.get)

odd[0] = 0
eve[0] = 0


if odd_m != eve_m:
    print (n - odd[odd_m] - eve[eve_m])

elif odd[odd_m] + eve[eve_mt] > odd[odd_mt] + eve[eve_m] :
    print (n - odd[odd_m] - eve[eve_mt])

else:
    print (n - odd[odd_mt] - eve[eve_m])
Buggy python submission (verdict: Time Limit Exceeded):
import math

def nCr(n,r):
    return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))


N,M = map(int,input().split())

l = [2]
now = 3

while now ** 2 <= M:
    flag = True
    for i in l:
        if now % i == 0:
            flag = False
            break
    if flag:
        l.append(now)
    now += 2

dic = {}
for i in l:

    while M % i == 0:
        if i not in dic:
            dic[i] = 1
        else:
            dic[i] += 1

        M //= i

if M != 1:
    dic[M] = 1

ans = 1
#print (dic)

for i in dic:
    ans *= nCr(dic[i] + N - 1,dic[i])
    #print (ans)
    ans %= (10 ** 9 + 7)
print (ans % (10**9+7))


Fixed submission:
import sys
mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def div(a, b):
    return mul(a, pow(b, mod-2,mod))

ivl = [0]
def inverse_max(a): #下2つを使用する際の下準備

    now = 1
    for i in range(a):
        i += 1
        now *= i
        now %= mod
        ivl.append(now)

def nCr(n,r):
    return div(ivl[n] , mul(ivl[n-r] , ivl[r]))


N,M = map(int,input().split())
inverse_max(N + 40)

if N == 1:
    print (1)
    sys.exit()

l = [2]
now = 3

while now ** 2 <= M:
    flag = True
    for i in l:
        if now % i == 0:
            flag = False
            break
    if flag:
        l.append(now)
    now += 2

dic = {}
for i in l:

    while M % i == 0:
        if i not in dic:
            dic[i] = 1
        else:
            dic[i] += 1

        M //= i

if M != 1:
    dic[M] = 1

ans = 1
#print (dic)

for i in dic:
    ans *= nCr(dic[i] + N - 1,dic[i])
    #print (ans)
    ans %= (10 ** 9 + 7)
print (ans % (10**9+7))
Buggy python submission (verdict: Time Limit Exceeded):

S = input()

lis = [1,0,0,0]
nlis = [1,0,0,0]

for s in S:

    if s == "?":

        nlis[0] += lis[0] * 2
        nlis[1] += lis[1] * 2
        nlis[2] += lis[2] * 2
        nlis[3] += lis[3] * 2

    if s == "A" or s == "?":

        nlis[1] += lis[0]

    if s == "B" or s == "?":

        nlis[2] += lis[1]

    if s == "C" or s == "?":

        nlis[3] += lis[2]

    lis = nlis.copy()

print (lis[3]  % (10 ** 9 + 7))


Fixed submission:

S = input()

lis = [1,0,0,0]
nlis = [1,0,0,0]

for s in S:

    if s == "?":

        nlis[0] += lis[0] * 2
        nlis[1] += lis[1] * 2
        nlis[2] += lis[2] * 2
        nlis[3] += lis[3] * 2

    if s == "A" or s == "?":

        nlis[1] += lis[0]

    if s == "B" or s == "?":

        nlis[2] += lis[1]

    if s == "C" or s == "?":

        nlis[3] += lis[2]

    lis = []
    for i in range(4):

        lis.append(nlis[i] % (10 ** 9 + 7))

print (lis[3]  % (10 ** 9 + 7))
Buggy python submission (verdict: Runtime Error):
import heapq

n,m,s,t = map(int,input().split())
s -= 1
t -= 1

dic = {}

for i in range(m):

    u,v,a,b = map(int,input().split())
    u -= 1
    v -= 1

    if u not in dic:
        dic[u] = []
    if v not in dic:
        dic[v] = []

    dic[u].append([v,a,b])
    dic[v].append([u,a,b])



q = [[0,t]]

yen = [float("inf")] * n
yen[t] = 0

yenwait = [True] * n

while len(q) > 0:

    du = heapq.heappop(q)

    for vab in dic[du[1]]:

        if yen[vab[0]] > yen[du[1]] + vab[2]:
            yen[vab[0]] = yen[du[1]] + vab[2]
            heapq.heappush(q,[yen[vab[0]] , vab[0]])

sunk = yen.copy()


q = [[0,s]]

yen = [float("inf")] * n
yen[s] = 0

yenwait = [True] * n

while len(q) > 0:

    du = heapq.heappop(q)

    for vab in dic[du[1]]:

        if yen[vab[0]] > yen[du[1]] + vab[1]:
            yen[vab[0]] = yen[du[1]] + vab[1]
            heapq.heappush(q,[yen[vab[0]] , vab[0]])


cost = []

for i in range(n):
    cost.append( yen[i] + sunk[i] )

costq = []

for i in range(n):
    heapq.heappush(costq , [cost[i] , i])

for i in range(n):

    while costq[0][1] < i:
        heapq.heappop(costq)

    print (10 ** 15 - costq[0][0])





Fixed submission:
import heapq

n,m,s,t = map(int,input().split())
s -= 1
t -= 1

dic = {}

for i in range(m):

    u,v,a,b = map(int,input().split())
    u -= 1
    v -= 1

    if u not in dic:
        dic[u] = []
    if v not in dic:
        dic[v] = []

    dic[u].append([v,a,b])
    dic[v].append([u,a,b])



q = [[0,t]]

yen = [float("inf")] * n
yen[t] = 0

yenwait = [True] * n

while len(q) > 0:

    du = heapq.heappop(q)

    for vab in dic[du[1]]:

        if yen[vab[0]] > yen[du[1]] + vab[2]:
            yen[vab[0]] = yen[du[1]] + vab[2]
            heapq.heappush(q,[yen[vab[0]] , vab[0]])

sunk = yen.copy()


q = [[0,s]]

yen = [float("inf")] * n
yen[s] = 0

yenwait = [True] * n

while len(q) > 0:

    du = heapq.heappop(q)

    for vab in dic[du[1]]:

        if yen[vab[0]] > yen[du[1]] + vab[1]:
            yen[vab[0]] = yen[du[1]] + vab[1]
            heapq.heappush(q,[yen[vab[0]] , vab[0]])


cost = []

for i in range(n):
    cost.append( yen[i] + sunk[i] )

costq = []

for i in range(n):
    heapq.heappush(costq , [cost[i] , i])

for i in range(n):

    while costq[0][1] < i:
        heapq.heappop(costq)

    print (10 ** 15 - costq[0][0])
Buggy python submission (verdict: Time Limit Exceeded):

N,M = map(int,input().split())

xyz = []

for i in range(N):

    x,y,z = map(int,input().split())
    xyz.append([x,y,z])

ans = -1 * float("inf")

for bpm in range(2):

    for dpm in range(2):

        for fpm in range(2):


            if bpm == 0:
                bpm = -1
            if dpm == 0:
                dpm = -1
            if fpm == 0:
                fpm = -1

            lis = [0] * (M+1)
            nlis = [0] * (M+1)


            for i in range(N):

                now = xyz[i][0] * bpm + xyz[i][1] * dpm + xyz[i][2] * fpm


                for j in range(M):

                    if j == 0 or lis[j] != 0:

                        nlis[j+1] = max(nlis[j+1],lis[j] + now)

                lis = nlis.copy()

            ans = max(ans,lis[M])

print (ans)

Fixed submission:

N,M = map(int,input().split())

xyz = []

for i in range(N):

    x,y,z = map(int,input().split())
    xyz.append([x,y,z])

ans = -1 * float("inf")

for bpm in range(2):

    for dpm in range(2):

        for fpm in range(2):


            if bpm == 0:
                bpm = -1
            if dpm == 0:
                dpm = -1
            if fpm == 0:
                fpm = -1

            lis = []

            for i in xyz:

                lis.append(i[0] * bpm + i[1] * dpm + i[2] * fpm)

            lis.sort()
            lis.reverse()

            now = 0
            for j in range(M):
                now += lis[j]

            ans = max(ans,now)

print (ans)
Buggy python submission (verdict: Time Limit Exceeded):

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

for i in range(B-A+1):

    if i <= K-1 or max( B - (A + i) , -B + ( A + i ) ) <= K-1:
        print (A+i)


Fixed submission:

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


if B-A+1 <= 2*K:

    for i in range(B-A+1):
        print (A+i)

else:

    for i in range(K):
        print (A+i)

    for i in range(K):
        print (B-K+1+i)
Buggy python submission (verdict: Time Limit Exceeded):
"""
各山のgrundy数がわかればよい

基本的にループする
"""

N = int(input())

ans = 0

for i in range(N):

    A,K = map(int,input().split())

    while True:

        if A % K == 0:
            ans ^= A // K
            break

        elif A == K-1:
            ans ^= 0
            break

        else:
            A = A - A // K - 1

if ans == 0:
    print ("Aoki")
else:
    print ("Takahashi")


Fixed submission:
"""
各山のgrundy数がわかればよい

基本的にループする
"""

N = int(input())

ans = 0

for i in range(N):

    A,K = map(int,input().split())

    

    while True:

        if A % K == 0:
            ans ^= A // K
            break

        elif A == K-1:
            ans ^= 0
            break

        else:

            if A // K != (A - A//K -1) // K:
                A = A - A // K - 1
            else:
                A -= (A - (A // K) * K) // (A // K+1) * (A//K+1)

    

if ans == 0:
    print ("Aoki")
else:
    print ("Takahashi")
Buggy python submission (verdict: Time Limit Exceeded):

H,W,D = map(int,input().split())
A = []

for i in range(H):

    a = list(map(int,input().split()))
    A.append(a)

dic = {}


for i in range(H):

    for j in range(W):

        dic[A[i][j]] = [i,j]

Q = int(input())


for i in range(Q):

    ans = 0

    L,R = map(int,input().split())

    now = dic[L]

    for j in range((R-L) // D):

        now = dic[L + j * D]
        nex = dic[L + (j+1) * D]

        ans += abs(now[0]-nex[0]) + abs(now[1]-nex[1])

    print(ans)
        


Fixed submission:

H,W,D = map(int,input().split())
A = []

for i in range(H):

    a = list(map(int,input().split()))
    A.append(a)

dic = {}


for i in range(H):

    for j in range(W):

        dic[A[i][j]] = [i,j]

Q = int(input())

nlis = [0]
for i in range(H * W):

    i += 1

    if i - D < 1:
        nlis.append(0)

    else:
        now = dic[i]
        las = dic[i-D]
        nlis.append(nlis[i-D] + abs(now[0]-las[0]) + abs(now[1]-las[1]))


for i in range(Q):

    L,R = map(int,input().split())

    print(nlis[R] - nlis[L])

Buggy python submission (verdict: Time Limit Exceeded):

H,W,D = map(int,input().split())
A = []

for i in range(H):

    a = list(map(int,input().split()))
    A.append(a)

dic = {}


for i in range(H):

    for j in range(W):

        dic[A[i][j]] = [i,j]

Q = int(input())


for i in range(Q):

    ans = 0

    L,R = map(int,input().split())

    now = dic[L]

    for j in range((R-L) // D):

        now = dic[L + j * D]
        nex = dic[L + (j+1) * D]

        ans += abs(now[0]-nex[0]) + abs(now[1]-nex[1])

    print(ans)
        


Fixed submission:

H,W,D = map(int,input().split())
A = []

for i in range(H):

    a = list(map(int,input().split()))
    A.append(a)

dic = {}


for i in range(H):

    for j in range(W):

        dic[A[i][j]] = [i,j]

Q = int(input())

nlis = [0]
for i in range(H * W):

    i += 1

    if i - D < 1:
        nlis.append(0)

    else:
        now = dic[i]
        las = dic[i-D]
        nlis.append(nlis[i-D] + abs(now[0]-las[0]) + abs(now[1]-las[1]))


for i in range(Q):

    L,R = map(int,input().split())

    print(nlis[R] - nlis[L])
Buggy python submission (verdict: Runtime Error):
c = []
ans = "No"

for i in range(3):

    nc = input()
    c.append([int(nc[0]),int(nc[2]),int(nc[4])])


if c[0][1]-c[0][0] == c[1][1]-c[1][0] and c[1][1]-c[1][0] == c[2][1]-c[2][0] and c[0][2]-c[0][1] == c[1][2]-c[1][1] and c[1][2]-c[1][1] == c[2][2]-c[2][1]:

    if c[1][0]-c[0][0] == c[1][1] - c[0][1] and c[1][1]-c[0][1] == c[1][2] - c[0][2] and c[2][0]-c[1][0] == c[2][1]-c[1][1] and c[2][1]-c[1][1] == c[2][2]-c[1][2]:

        ans = "Yes"

print (ans)


Fixed submission:
c = []
ans = "No"

for i in range(3):

    nc = list(map(int,input().split()))
    c.append(nc)


if c[0][1]-c[0][0] == c[1][1]-c[1][0] and c[1][1]-c[1][0] == c[2][1]-c[2][0] and c[0][2]-c[0][1] == c[1][2]-c[1][1] and c[1][2]-c[1][1] == c[2][2]-c[2][1]:

    if c[1][0]-c[0][0] == c[1][1] - c[0][1] and c[1][1]-c[0][1] == c[1][2] - c[0][2] and c[2][0]-c[1][0] == c[2][1]-c[1][1] and c[2][1]-c[1][1] == c[2][2]-c[1][2]:

        ans = "Yes"

print (ans)
Buggy python submission (verdict: Runtime Error):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/apc001/tasks/apc001_e

厳密な照明は難しいが…
直径を取る
直径の端点からbfs

全ての頂点に関して、部分木に少なくとも一つのアンテナを持つかのフラグを管理
子の数をkとする。その内x個がtrueの場合、k-1-x個のアンテナを追加。自分のflagをtrueにする
子がfalseで、子が0 or 1つしかない場合のみfalse継続

簡単な木では最適になることを実験したがどうだろうか…？
"""

from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    plis = [i for i in range(len(lis))]

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                plis[nex] = now
                q.append(nex)

    return ret,plis,now

N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

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

    lis[a].append(b)
    lis[b].append(a)

td,tp,stp = NC_Dij(lis,0)


ans = 0

def dfs(v,p):

    x = 0
    c = 0
    retflag = False
    for nex in lis[v]:

        if nex != p:
            c += 1
            have = dfs(nex,v)
            retflag = have or retflag
            if have:
                x += 1

    if c-1-x > 0:
        retflag = True
    global ans
    ans += max(0,c-1-x)

    return retflag

dfs(stp,stp)
print (ans+1)



Fixed submission:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/apc001/tasks/apc001_e

厳密な照明は難しいが…
直径を取る
直径の端点からbfs

全ての頂点に関して、部分木に少なくとも一つのアンテナを持つかのフラグを管理
子の数をkとする。その内x個がtrueの場合、k-1-x個のアンテナを追加。自分のflagをtrueにする
子がfalseで、子が0 or 1つしかない場合のみfalse継続

簡単な木では最適になることを実験したがどうだろうか…？
"""
import sys
sys.setrecursionlimit(3*10**5)

from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    plis = [i for i in range(len(lis))]

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                plis[nex] = now
                q.append(nex)

    return ret,plis,now

N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

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

    lis[a].append(b)
    lis[b].append(a)

td,tp,stp = NC_Dij(lis,0)


ans = 0

def dfs(v,p):

    x = 0
    c = 0
    retflag = False
    for nex in lis[v]:

        if nex != p:
            c += 1
            have = dfs(nex,v)
            retflag = have or retflag
            if have:
                x += 1

    if c-1-x > 0:
        retflag = True
    global ans
    ans += max(0,c-1-x)

    return retflag

dfs(stp,stp)
print (ans+1)