Buggy python submission (verdict: Time Limit Exceeded):
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
T=input()
dp=[["" for j in range(len(T))] for i in range(len(S))]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i][j]=dp[max(i-1,0)][max(j-1,0)]+S[i]
        else:
            L=[dp[max(i-1,0)][max(j-1,0)],dp[max(i-1,0)][j],dp[i][max(j-1,0)]]
            L_len=[len(L[0]),len(L[1]),len(L[2])]
            dp[i][j]=L[L_len.index(max(L_len))]
print(dp[-1][-1])

Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
S=input()
T=input()
dp=[["" for j in range(len(T))] for i in range(len(S))]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i][j]=dp[max(i-1,0)][max(j-1,0)]+S[i]
        else:
            L=[dp[max(i-1,0)][max(j-1,0)],dp[max(i-1,0)][j],dp[i][max(j-1,0)]]
            dp[i][j]=L[np.argmax([len(L[0]),len(L[1]),len(L[2])])]
print(dp[-1][-1])

Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
d=[[] for i in range(N)]
for i in range(M):
    x,y=map(int,input().split())
    d[x-1].append(y-1)
scores=[]
def depth(now,score):
    global scores
    if d[now]:
        for i in d[now]:
            depth(i,score+1)
    else:
        scores.append(score)
Max=0
for i in range(N):
    depth(i,0)
    if scores and max(scores)>Max:
        Max=max(scores)
    scores.clear()
print(Max)

Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
s= sys.stdin.readline().rstrip() 
t= sys.stdin.readline() .rstrip()
Ns=len(s)
Nt=len(t)
i=1
dp=[["" for i in range(Nt+1)]for j in range(Ns+1)]
while i<=Ns:
    j=1
    while j<=Nt:
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+s[i-1]
        else:
            if len(dp[i][j-1])>len(dp[i-1][j]):
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]
        j+=1
    i+=1
print(dp[Ns][Nt])

Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
s= sys.stdin.readline().rstrip() 
t= sys.stdin.readline() .rstrip()
Ns=len(s)
Nt=len(t)
i=1
dp=[["" for i in range(Nt+1)]for j in range(Ns+1)]
while i<=Ns:
    j=1
    while j<=Nt:
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+s[i-1]
        else:
            if len(dp[i][j-1])>len(dp[i-1][j]):
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]
        j+=1
    i+=1
print(dp[Ns][Nt])

Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
s= sys.stdin.readline().rstrip() 
t= sys.stdin.readline() .rstrip()
Ns=len(s)
Nt=len(t)
dp=[["" for i in range(Nt+1)]for j in range(Ns+1)]
for i in range(1,Ns+1):
    for j in range(1,Nt+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+s[i-1]
        else:
            if len(dp[i][j-1])>len(dp[i-1][j]):
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]
print(dp[Ns][Nt])

Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
t=input()
Ns=len(s)
Nt=len(t)
dp=[["" for i in range(Nt+1)]for j in range(Ns+1)]
for i in range(1,Ns+1):
    for j in range(1,Nt+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+s[i-1]
        else:
            if len(dp[i][j-1])>len(dp[i-1][j]):
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]
print(dp[Ns][Nt])

Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s=str(input())
t=str(input())
Ns=len(s)
Nt=len(t)
dp=[["" for i in range(Nt+1)]for j in range(Ns+1)]
for i in range(1,Ns+1):
    for j in range(1,Nt+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+s[i-1]
        else:
            if len(dp[i][j-1])>len(dp[i-1][j]):
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]
print(dp[Ns][Nt])

Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Runtime Error):
s=str(input())
t=str(input())
Ns=len(s)
Nt=len(t)
dp=[["" for i in range(Nt+1)]for j in range(Ns+1)]
for i in range(1,Ns+1):
    for j in range(1,Nt+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+s[i-1]
        else:
            if len(dp[i][j-1])>len(dp[i-1][j]):
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]
print(dp[Ns][Nt])

Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s=str(input())
t=str(input())
Ns=len(s)
Nt=len(t)
dp=[["" for i in range(Nt+1)]for j in range(Ns+1)]
for i in range(1,Ns+1):
    for j in range(1,Nt+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+s[i-1]
        else:
            if len(dp[i][j-1])>len(dp[i-1][j]):
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]
print(dp[Ns][Nt])

Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
T=input()
s=len(S)
t=len(T)
dp=[['' for i in range(t+1)] for j in range(s+1)]
for i in range(s):
    for j in range(t):
        if S[i]!=T[j]:
            dp[i+1][j+1]=dp[i+1][j]
            if len(dp[i][j+1])>len(dp[i+1][j]):
                dp[i+1][j+1]=dp[i][j+1]
            continue
        dp[i+1][j+1]=dp[i][j]+S[i]
print(dp[s][t])


Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Runtime Error):
def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)

def solve():
    N = int(input())
    for _ in range(N):
        x = input()
        y = input()
        print(lcs(x, y))

if __name__ == '__main__':
    solve()

Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
T=input()
s=len(S)
t=len(T)
dp=[['' for i in range(t+1)] for j in range(s+1)]
for i in range(s):
    for j in range(t):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+S[i]
            continue
        dp[i+1][j+1]=dp[i+1][j]
        if len(dp[i][j+1])>len(dp[i+1][j]):
            dp[i+1][j+1]=dp[i][j+1]
print(dp[s][t])


Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
T=input()
s=len(S)
t=len(T)
dp=[['' for i in range(t+1)] for j in range(s+1)]
for i in range(s):
    for j in range(t):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+S[i]
        else:
            dp[i+1][j+1]=dp[i+1][j]
            if len(dp[i][j+1])>len(dp[i+1][j]):
                dp[i+1][j+1]=dp[i][j+1]
print(dp[s][t])


Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Runtime Error):
S=input()
T=input()
s=len(S)
t=len(T)
dp=[['' for i in range(s+1)] for j in range(t+1)]
for i in range(s):
    for j in range(t):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+S[i]
        else:
            dp[i+1][j+1]=dp[i+1][j]
            if len(dp[i][j+1])>len(dp[i+1][j]):
                dp[i+1][j+1]=dp[i][j+1]
print(dp[s][t])


Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Runtime Error):
S=input()
T=input()
s=len(S)
t=len(T))
dp=[['' for i in range(T+1)] for j in range(T+1)]
for i in range(S):
    for j in range(T):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+s[i]
        else:
            dp[i+1][j+1]=dp[i+1][j]
            if len(dp[i][j+1])>len(dp[i+1][j]):
                dp[i+1][j+1]=dp[i][j+1]
print(dp[S][T])


Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
t=input()
dp=[['' for i in range(len(t)+1)] for j in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+s[i]
        else:
            dp[i+1][j+1]=dp[i+1][j]
            if len(dp[i][j+1])>len(dp[i+1][j]):
                dp[i+1][j+1]=dp[i][j+1]
print(dp[len(s)][len(t)])


Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
t=input()
dp=[['' for i in range(len(t)+1)] for j in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+s[i]
        else:
            a=dp[i+1][j]
            if len(dp[i][j+1])>len(dp[i+1][j]):
                a=dp[i][j+1]
            dp[i+1][j+1]=a
print(dp[len(s)][len(t)])


Fixed submission:
S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)