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

sa = sum(A)
m = 1
divs = set()
while m*m <= sa:
    if sa%m == 0:
        divs.add(m)
        divs.add(sa//m)
    m += 1

for d in sorted(divs,reverse=True):
    mods = []
    for a in A:
        mods.append(a%d)
    mods.sort()
    if all(m==0 for m in mods):
        print(d)
        exit()
    for i in range(N-1):
        plus = minus = 0
        for j,m in enumerate(mods):
            if j <= i:
                plus += m
            else:
                minus += d-m
        if plus == minus and plus <= K:
            print(d)
            exit()

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

sa = sum(A)
m = 1
divs = set()
while m*m <= sa:
    if sa%m == 0:
        divs.add(m)
        divs.add(sa//m)
    m += 1

for d in sorted(divs,reverse=True):
    mods = []
    for a in A:
        mods.append(a%d)
    mods.sort()
    if all(m==0 for m in mods):
        print(d)
        exit()

    cump = [0]
    for m in mods:
        cump.append(cump[-1] + m)
    cumm = [0]
    for m in reversed(mods):
        cumm.append(cumm[-1] + (d-m))
    for i in range(1,N):
        if cump[i] == cumm[N-i] and cump[i] <= K:
            print(d)
            exit()

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

sa = sum(A)
m = 1
divs = set()
while m*m <= sa:
    if sa%m == 0:
        divs.add(m)
        divs.add(sa//m)
    m += 1

for d in sorted(divs,reverse=True):
    mods = []
    for a in A:
        mods.append(a%d)
    mods.sort()
    if all(m==0 for m in mods):
        print(d)
        exit()
    for i in range(N-1):
        plus = minus = 0
        for j,m in enumerate(mods):
            if j <= i:
                plus += m
            else:
                minus += d-m
        if plus == minus and plus <= K:
            print(d)
            exit()

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

sa = sum(A)
m = 1
divs = set()
while m*m <= sa:
    if sa%m == 0:
        divs.add(m)
        divs.add(sa//m)
    m += 1

for d in sorted(divs,reverse=True):
    mods = []
    for a in A:
        mods.append(a%d)
    mods.sort()
    if all(m==0 for m in mods):
        print(d)
        exit()

    cump = [0]
    for m in mods:
        cump.append(cump[-1] + m)
    cumm = [0]
    for m in reversed(mods):
        cumm.append(cumm[-1] + (d-m))
    for i in range(1,N):
        if cump[i] == cumm[N-i] and cump[i] <= K:
            print(d)
            exit()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]
XY.sort(key=lambda x:x[0])

ys = []
for _,y in XY:
    ys.append(y)
ys.sort()
yd = {y:i for i,y in enumerate(ys)}

class BinaryIndexedTree:
    def __init__(self,size):
        self.N = size
        self.bit = [0]*(size+1)
    def add(self,x,w): # 0-indexed
        x += 1
        while x <= self.N:
            self.bit[x] += w
            x += (x & -x)
    def _sum(self,x): # 1-indexed
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= (x & -x)
        return ret
    def sum(self,l,r): # [l,r)
        return self._sum(r) - self._sum(l)
    def __str__(self): # for debug
        arr = [self.sum(i,i+1) for i in range(self.N)]
        return str(arr)

lbit = BinaryIndexedTree(N)
lu = []
ld = []
for i,(_,y) in enumerate(XY):
    d = lbit._sum(yd[y])
    u = i - d
    lu.append(u)
    ld.append(d)
    lbit.add(yd[y],1)

rbit = BinaryIndexedTree(N)
ru = []
rd = []
for i,(_,y) in enumerate(XY[::-1]):
    d = rbit._sum(yd[y])
    u = i - d
    ru.append(u)
    rd.append(d)
    rbit.add(yd[y],1)

MOD = 998244353
ans = 0
for a,b,c,d in zip(ld,lu,rd[::-1],ru[::-1]):
    pa,pb,pc,pd = pow(2,a,MOD),pow(2,b,MOD),pow(2,c,MOD),pow(2,d,MOD)
    ans += (pa-1) * (pd-1) * pb * pc
    ans += (pb-1) * (pc-1) * pa * pd
    ans -= (pa-1) * (pb-1) * (pc-1) * (pd-1)
    ans %= MOD
ans += N * pow(2,N-1,MOD)
ans %= MOD
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]
XY.sort(key=lambda x:x[0])

ys = []
for _,y in XY:
    ys.append(y)
ys.sort()
yd = {y:i for i,y in enumerate(ys)}

class BinaryIndexedTree:
    def __init__(self,size):
        self.N = size
        self.bit = [0]*(size+1)
    def add(self,x,w): # 0-indexed
        x += 1
        while x <= self.N:
            self.bit[x] += w
            x += (x & -x)
    def _sum(self,x): # 1-indexed
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= (x & -x)
        return ret
    def sum(self,l,r): # [l,r)
        return self._sum(r) - self._sum(l)
    def __str__(self): # for debug
        arr = [self.sum(i,i+1) for i in range(self.N)]
        return str(arr)

lbit = BinaryIndexedTree(N)
lu = []
ld = []
for i,(_,y) in enumerate(XY):
    d = lbit._sum(yd[y])
    u = i - d
    lu.append(u)
    ld.append(d)
    lbit.add(yd[y],1)

rbit = BinaryIndexedTree(N)
ru = []
rd = []
for i,(_,y) in enumerate(XY[::-1]):
    d = rbit._sum(yd[y])
    u = i - d
    ru.append(u)
    rd.append(d)
    rbit.add(yd[y],1)

MOD = 998244353
ans = 0
for a,b,c,d in zip(ld,lu,rd[::-1],ru[::-1]):
    pa,pb,pc,pd = pow(2,a,MOD),pow(2,b,MOD),pow(2,c,MOD),pow(2,d,MOD)
    ans += (pa-1) * (pd-1) * pb * pc
    ans += (pb-1) * (pc-1) * pa * pd
    ans -= (pa-1) * (pb-1) * (pc-1) * (pd-1)
    ans %= MOD
ans += N * pow(2,N-1,MOD)
ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
dp = [[0]*13 for i in range(len(S))]
MOD = 10**9+7

if S[0]=='?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(S[0])] = 1

for i,c in enumerate(S[1:]):
    for j in range(13):
        if c=='?':
            for k in range(10):
                nj = (j*10 + k) % 13
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
        else:
            nj = (j*10 + int(c)) % 13
            dp[i+1][nj] += dp[i][j]
            dp[i+1][nj] %= MOD

print(dp[-1][5])

Fixed submission:
S = input()
dp = [[0]*13 for i in range(len(S))]
MOD = 10**9+7

if S[0]=='?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(S[0])] = 1

for i,c in enumerate(S[1:]):
    for j in range(13):
        if c=='?':
            for k in range(10):
                nj = (j*10 + k) % 13
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
        else:
            nj = (j*10 + int(c)) % 13
            dp[i+1][nj] += dp[i][j]
            dp[i+1][nj] %= MOD

print(dp[-1][5])
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
MOD = 10**9+7

es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

MAXN = N+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def npr(n,r):
    if n<r: return 0
    return fac[n] * finv[n-r]


ans = K
stack = [(0,0)]
visited = [0]*N
while stack:
    v,d = stack.pop()
    visited[v] = 1
    c = 0
    for to in es[v]:
        if visited[to]: continue
        c += 1
        stack.append((to,d+1))
    if c==0: continue
    m = npr(K-1,c) if d==0 else npr(K-2,c)
    ans *= m
    ans %= MOD
print(ans)

Fixed submission:
N,K = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

MOD = 10**9+7

fac = [1,1] + [0]*K
finv = [1,1] + [0]*K
inv = [0,1] + [0]*K
for i in range(2,K+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def npr(n,r):
    if n<r: return 0
    return fac[n] * finv[n-r]

ans = K * npr(K-1,len(es[0]))
ans %= MOD

visited = [0]*N
visited[0] = 1
stack = []
for v in es[0]:
    stack.append(v)

while stack:
    v = stack.pop()
    visited[v] = 1
    ans *= npr(K-2, len(es[v])-1)
    ans %= MOD
    for to in es[v]:
        if visited[to]: continue
        stack.append(to)
print(ans%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
MOD = 10**9+7

def solve():
    m = 1
    a,b = [],[]
    while m*m <= N:
        a.append(m)
        b.append(N//m)
        m += 1
    if a[-1] == b[-1]:
        b.pop()
    a += b[::-1]
    w = [b-a for a,b in zip([0]+a, a)]
    
    L = len(a)
    dp = [1]*L
    for _ in range(K-1):
        dp2 = [0]*L
        c = 0
        for i,v in enumerate(w):
            c += dp[i] * v
            dp2[L-1-i] += c
            dp2[L-1-i] %= MOD
        dp = dp2
    return sum(a*b for a,b in zip(w,dp)) % MOD
print(solve())

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

m = 1
a,b = [],[]
while m*m <= N:
    a.append(m)
    b.append(N//m)
    m += 1
if a[-1] == b[-1]:
    b.pop()
a += b[::-1]
w = [b-a for a,b in zip([0]+a, a)]

L = len(a)
dp = [1]*L
for _ in range(K-1):
    dp2 = [0]*L
    c = 0
    for i,v in enumerate(w):
        c += dp[i] * v
        dp2[L-1-i] += c
        dp2[L-1-i] %= MOD
    dp = dp2
ans = sum(a*b for a,b in zip(w,dp))
print(ans%MOD)

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
MOD = 10**9+7

m = 1
a,b = [],[]
while m*m <= N:
    a.append(m)
    b.append(N//m)
    m += 1
if a[-1] == b[-1]:
    b.pop()
a += b[::-1]
w = [b-a for a,b in zip([0]+a, a)]

L = len(a)
dp = [1]*L
for _ in range(K-1):
    dp2 = [0]*L
    c = 0
    for i,v in enumerate(w):
        c += dp[i] * v
        dp2[L-1-i] += c
        dp2[L-1-i] %= MOD
    dp = dp2
ans = sum(a*b for a,b in zip(w,dp))
print(ans%MOD)

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

m = 1
a,b = [],[]
while m*m <= N:
    a.append(m)
    b.append(N//m)
    m += 1
if a[-1] == b[-1]:
    b.pop()
a += b[::-1]
w = [b-a for a,b in zip([0]+a, a)]

L = len(a)
dp = [1]*L
for _ in range(K-1):
    dp2 = [0]*L
    c = 0
    for i,v in enumerate(w):
        c += dp[i] * v
        dp2[L-1-i] += c
        dp2[L-1-i] %= MOD
    dp = dp2
ans = sum(a*b for a,b in zip(w,dp))
print(ans%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
MOD = 10**9+7

dp = [[1]*(M+1) for i in range(N+1)]

for i,s in enumerate(S):
    for j,t in enumerate(T):
        if s==t:
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
        else:
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j]
        dp[i+1][j+1] %= MOD
print(dp[-1][-1])

Fixed submission:
N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
MOD = 10**9+7

dp = [[1]*(M+1) for i in range(N+1)]

for i,s in enumerate(S):
    for j,t in enumerate(T):
        if s==t:
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
        else:
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j]
        dp[i+1][j+1] %= MOD
print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

def solve(n,fr,to):
    rates = [(f,t) for f,t in zip(fr,to) if f < t]
    rates.sort()
    if not rates:
        return n
    dp = [i for i in range(n+1)]
    for f,t in rates:
        for i in range(f,n+1):
            dp[i] = max(dp[i], dp[i-f] + t)
    return dp[-1]

n = solve(N,A,B)
print(solve(n,B,A))

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

def solve(n,fr,to):
    rates = [(f,t) for f,t in zip(fr,to) if f < t]
    rates.sort()
    if not rates:
        return n
    dp = [i for i in range(n+1)]
    for f,t in rates:
        for i in range(f,n+1):
            dp[i] = max(dp[i], dp[i-f] + t)
    return dp[-1]

n = solve(N,A,B)
print(solve(n,B,A))
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
ans = 0

while 1:
    c = S.count('ABC')
    if c==0: break
    ans += c
    S = S.replace('ABC','BCA')
print(ans)

Fixed submission:
S = input()
S = S.replace('BC','D')
ans = 0
a = 0
for c in S:
    if c=='A':
        a += 1
    elif c=='D':
        ans += a
    else:
        a = 0
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,N = map(int,input().split())
ans = 0
for r in range(N+1):
    if r*R > N: break
    for g in range(N+1):
        if r*R + g*G > N: break
        rem = N - r*R - g*G
        if rem%B == 0:
            ans += 1
print(ans)

Fixed submission:
R,G,B,N = map(int,input().split())
ans = 0
for a in range(0,N+1,R):
    for b in range(0,N+1,G):
        if a+b > N: break
        c = N - a - b
        if c%B==0:
            ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
ans = 0
n = 1
while 1:
    if (N-n)%n == 0:
        m = (N-n)//n
        if m <= n: break
        ans += m
    n += 1
print(ans)

Fixed submission:
N = int(input())
ans = 0

n = 1
while n*n < N:
    if N%n==0 and n < N//n-1:
        ans += N//n-1
    n += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in src:
    es[a].append(b)
    es[b].append(a)

if all(len(e)<=2 for e in es):
    print('First' if N%2 else 'Second')
    exit()
assert False

Fixed submission:
N = int(input())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in src:
    es[a].append(b)
    es[b].append(a)

def farthest_node_and_dist(s):
    dist = [N]*N
    dist[s] = 0
    stack = [s]
    ret_node = -1
    ret_dist = 0
    while stack:
        v = stack.pop()
        d = dist[v]
        for to in es[v]:
            if d+1 < dist[to]:
                dist[to] = d+1
                stack.append(to)
                if ret_dist < d+1:
                    ret_dist = d+1
                    ret_node = to
    return (ret_node, ret_dist)

n,d = farthest_node_and_dist(0)
n,d = farthest_node_and_dist(n)
print('Second' if d%3==1 else 'First')
Buggy python submission (verdict: Time Limit Exceeded):
X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

AB = []
AC = []
BC = []
for a in A:
    for b in B:
        AB.append(a+b)
    for c in C:
        AC.append(a+c)
for b in B:
    for c in C:
        BC.append(b+c)
AB.sort(reverse=True)
AC.sort(reverse=True)
BC.sort(reverse=True)

ABC = []
for x in AB[:K]:
    for c in C:
        ABC.append(x+c)
for x in BC[:K]:
    for a in A:
        ABC.append(x+a)
for x in AC[:K]:
    for b in B:
        ABC.append(x+b)
ABC.sort(reverse=True)
print(*ABC[::3][:K], sep='\n')

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

AB = []
AC = []
BC = []
for a in A:
    for b in B:
        AB.append(a+b)
    for c in C:
        AC.append(a+c)
for b in B:
    for c in C:
        BC.append(b+c)
AB.sort(reverse=True)
AC.sort(reverse=True)
BC.sort(reverse=True)

hq = []
heapq.heapify(hq)
for a in A:
    for bc in BC[:K]:
        heapq.heappush(hq,-a-bc)
for b in B:
    for ac in AC[:K]:
        heapq.heappush(hq,-b-ac)
for c in C:
    for ab in AB[:K]:
        heapq.heappush(hq,-c-ab)

ans = []
for _ in range(K):
    ans.append(-heapq.heappop(hq))
    heapq.heappop(hq)
    heapq.heappop(hq)

print(*ans, sep='\n')

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

AB = []
AC = []
BC = []
for a in A:
    for b in B:
        AB.append(a+b)
    for c in C:
        AC.append(a+c)
for b in B:
    for c in C:
        BC.append(b+c)
AB.sort(reverse=True)
AC.sort(reverse=True)
BC.sort(reverse=True)

arr = []
for a in A:
    for bc in BC[:K]:
        arr.append(a+bc)
for b in B:
    for ac in AC[:K]:
        arr.append(b+ac)
for c in C:
    for ab in AB[:K]:
        arr.append(c+ab)

arr.sort(reverse=True)
ans = arr[:K*3:3]
print(*ans, sep='\n')

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

AB = []
AC = []
BC = []
for a in A:
    for b in B:
        AB.append(a+b)
    for c in C:
        AC.append(a+c)
for b in B:
    for c in C:
        BC.append(b+c)
AB.sort(reverse=True)
AC.sort(reverse=True)
BC.sort(reverse=True)

hq = []
heapq.heapify(hq)
for a in A:
    for bc in BC[:K]:
        heapq.heappush(hq,-a-bc)
for b in B:
    for ac in AC[:K]:
        heapq.heappush(hq,-b-ac)
for c in C:
    for ab in AB[:K]:
        heapq.heappush(hq,-c-ab)

ans = []
for _ in range(K):
    ans.append(-heapq.heappop(hq))
    heapq.heappop(hq)
    heapq.heappop(hq)

print(*ans, sep='\n')
Buggy python submission (verdict: Runtime Error):
S = input()
one = S.count('1')
zero = len(S) - one
print(min(one, zero) * 2py )

Fixed submission:
S = input()
z = S.count('0')
o = len(S) - z
print(len(S) - abs(z-o))
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
A = list(map(int,input().split()))

bs = [0] * 40
for a in A:
    for k in range(40):
        if a&(1<<k):
            bs[k] += 1

x = 0
for k in range(39,-1,-1):
    if x + (1<<k) > K: continue
    if bs[k] < (N+1)s//2:
        x += (1<<k)

ans = 0
for a in A:
    ans += x^a
print(ans)

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

bs = [0] * 40
for a in A:
    for k in range(40):
        if a&(1<<k):
            bs[k] += 1

x = 0
for k in range(39,-1,-1):
    if x + (1<<k) > K: continue
    if bs[k] < (N+1)//2:
        x += (1<<k)

ans = 0
for a in A:
    ans += x^a
print(ans)
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
TD = [tuple(map(int,input().split())) for i in range(N)]
TD.sort(key=lambda x:x[1])

import heapq
hq = []
heapq.heapify(hq)
selected = set()
ans = 0
for _ in range(K):
    t,d = TD.pop()
    if t in selected:
        heapq.heappush(hq, d)
    else:
        selected.add(t)
    ans += d
ans += len(selected)**2

tmp = ans
while TD:
    t,d = TD.pop()
    if t in selected: continue
    selected.add(t)
    tmp -= heapq.heappop(hq)
    tmp += d
    tmp += len(selected)*2 - 1
    ans = max(ans ,tmp)
print(ans)

Fixed submission:
from collections import Counter
N,K = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]
src.sort(key=lambda x:-x[1])

selected = Counter()
ans = 0
stack = []

for t,d in src[:K]:
    ans += d
    selected[t] += 1
    stack.append((t,d))
ans += len(selected)**2

tmp = ans
for t,d in src[K:]:
    if t in selected: continue
    while stack:
        t0,d0 = stack.pop()
        if selected[t0] > 1:
            tmp += d - d0 + 2*len(selected)+1
            ans = max(ans, tmp)
            selected[t0] -= 1
            selected[t] += 1
            break
    else:
        break
print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
T = input()
N = len(S)
M = len(T)

dp = [[0]*(M+1) for i in range(N+1)]

for i in range(N):
    for j in range(M):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

ans = ''
def rec(i,j):
    print(i,j)
    if i==0 or j==0: return
    if S[i-1] == T[j-1]:
        global ans
        ans += S[i-1]
        rec(i-1,j-1)
    elif dp[i-1][j] >= dp[i][j-1]:
        rec(i-1,j)
    else:
        rec(i,j-1)

rec(N,M)
print(ans[::-1])

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

S = input()
T = input()
N = len(S)
M = len(T)

dp = [[0]*(M+1) for i in range(N+1)]

for i in range(N):
    for j in range(M):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

ans = ''
def rec(i,j):
    if i==0 or j==0: return
    if S[i-1] == T[j-1]:
        global ans
        ans += S[i-1]
        rec(i-1,j-1)
    elif dp[i-1][j] >= dp[i][j-1]:
        rec(i-1,j)
    else:
        rec(i,j-1)

rec(N,M)
print(ans[::-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
src = [tuple(map(int,input().split())) for i in range(N-1)]

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

es = [[] for i in range(N)]
for a,b in src:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

MOD = 10**9+7
dp = [[1,1] for i in range(N)]

def rec(i,parent):
    for to in es[i]:
        if to==parent: continue
        rec(to,i)
        dp[i][0] *= (dp[to][0] + dp[to][1])
        dp[i][1] *= dp[to][0]
        dp[i][0] %= MOD
        dp[i][1] %= MOD

rec(0,-1)
print(sum(dp[0])%MOD)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
MOD = 10**9+7

N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for x,y in XY:
    x,y = x-1,y-1
    es[x].append(y)
    es[y].append(x)

dp = [[1,1] for i in range(N)]
def rec(v,p=-1):
    for to in es[v]:
        if to==p: continue
        rec(to,v)
        dp[v][0] *= (dp[to][0] + dp[to][1])
        dp[v][1] *= dp[to][0]
        dp[v][0] %= MOD
        dp[v][1] %= MOD
rec(0)

print(sum(dp[0]) % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)

N = int(input())
src = [tuple(map(int,input().split())) for i in range(N-1)]

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

es = [[] for i in range(N)]
for a,b in src:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

MOD = 10**9+7
dp = [[1,1] for i in range(N)]

def rec(i,parent):
    for to in es[i]:
        if to==parent: continue
        rec(to,i)
        dp[i][0] *= (dp[to][0] + dp[to][1])
        dp[i][1] *= dp[to][0]
        dp[i][0] %= MOD
        dp[i][1] %= MOD

rec(0,-1)
print(sum(dp[0])%MOD)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
MOD = 10**9+7

N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for x,y in XY:
    x,y = x-1,y-1
    es[x].append(y)
    es[y].append(x)

dp = [[1,1] for i in range(N)]
def rec(v,p=-1):
    for to in es[v]:
        if to==p: continue
        rec(to,v)
        dp[v][0] *= (dp[to][0] + dp[to][1])
        dp[v][1] *= dp[to][0]
        dp[v][0] %= MOD
        dp[v][1] %= MOD
rec(0)

print(sum(dp[0]) % MOD)