Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
l=[list(map(int,input().split()))for i in range(m)]
dist=[[1<<29]*n for i in range(n)]
for i in range(m): dist[i][i]=0
for a in l:
  dist[a[0]-1][a[1]-1] = min(dist[a[0]-1][a[1]-1],a[2])
  dist[a[1]-1][a[0]-1] = min(dist[a[1]-1][a[0]-1],a[2])
# print(dist)
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
# 経路復元
ans=m
for a in l:
  flag=False
  for j in range(n): 
    if dist[j][a[0]-1]+a[2]==dist[j][a[1]-1]: flag=True
  if flag: ans-=1
print(ans)

Fixed submission:
n,m=map(int,input().split())
l=[list(map(int,input().split()))for i in range(m)]
dist=[[1<<29]*n for i in range(n)]
for i in range(n): dist[i][i]=0
for a in l:
  dist[a[0]-1][a[1]-1] = min(dist[a[0]-1][a[1]-1],a[2])
  dist[a[1]-1][a[0]-1] = min(dist[a[1]-1][a[0]-1],a[2])
# print(dist)
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
# 経路復元
ans=m
for a in l:
  flag=False
  for j in range(n): 
    if dist[j][a[0]-1]+a[2]==dist[j][a[1]-1]: flag=True
  if flag: ans-=1
print(ans)

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
l=[list(map(int,input().split()))for i in range(m)]
dist=[[1<<29]*n for i in range(n)]
for i in range(m): dist[i][i]=0
for a in l:
  dist[a[0]-1][a[1]-1] = min(dist[a[0]-1][a[1]-1],a[2])
  dist[a[1]-1][a[0]-1] = min(dist[a[1]-1][a[0]-1],a[2])
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
# 経路復元
ans=m
for a in l:
  flag=False
  for j in range(n): 
    if dist[j][a[0]-1]+a[2]==dist[j][a[1]-1]: flag=True
  if flag: ans-=1
print(ans)

Fixed submission:
n,m=map(int,input().split())
l=[list(map(int,input().split()))for i in range(m)]
dist=[[1<<29]*n for i in range(n)]
for i in range(n): dist[i][i]=0
for a in l:
  dist[a[0]-1][a[1]-1] = min(dist[a[0]-1][a[1]-1],a[2])
  dist[a[1]-1][a[0]-1] = min(dist[a[1]-1][a[0]-1],a[2])
# print(dist)
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
# 経路復元
ans=m
for a in l:
  flag=False
  for j in range(n): 
    if dist[j][a[0]-1]+a[2]==dist[j][a[1]-1]: flag=True
  if flag: ans-=1
print(ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np
n,l=map(int,input().split())
a=list(map(int,input().split()))
flag=False;idx=0
for i in range(n-1):
  if a[i]+a[i+1]>=l:
    flag=True
    idx=i
if not Flag:
  print("Impossible")
  exit(0)
print("Possible")
for x in range(idx):
  print(x+1)
for x in reversed(range(idx+1)):
  print(x+1)

Fixed submission:
import numpy as np
n,l=map(int,input().split())
a=list(map(int,input().split()))
flag=False;idx=0
for i in range(n-1):
  if a[i]+a[i+1]>=l:
    flag=True
    idx=i
if not flag:
  print("Impossible")
  exit(0)
print("Possible")
for x in range(idx):
  print(x+1)
for x in reversed(range(idx,n-1)):
  print(x+1)
Buggy python submission (verdict: Runtime Error):
from scipy.special import comb

S = int(input())

n = S//3
k = S%3
Q = 10**9+7
ans = 0
for i in range(n):
    #iはしきりをとった数
    m = n-i #要素数
    ans += comb(n-1,i,exact=true)*comb(m,k,exact=True)
    if k==2:
        ans += k
    ans %=Q
print(ans)

Fixed submission:
S = int(input())
A = [0]*(S+1)
A[0] = 1
MOD = 10**9+7

if S<=2:
    print(A[S])
    exit()

for i in range(3,S+1):
    for j in range(i-2):
        A[i] += A[j]
    A[i]%=MOD
print(A[S])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
P = 10**9+7
ans = 0

for i in range(N):
    temp = 0
    for j in range(i+1,N):
        temp += A[j]
    temp *= A[i]
    ans += temp%P
print(ans%P)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
P = 10**9+7
ans = 0
S = sum(A)

for i in range(N):
    S -= A[i]
    ans += A[i]*S%P
print(ans%P)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
P = 10**9+7
ans = 0

for i in range(N):
    for j in range(i+1,N):
        ans += A[i]*A[j]
        if ans >= P:
            ans = ans%P
print(ans)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
P = 10**9+7
ans = 0
S = sum(A)

for i in range(N):
    S -= A[i]
    ans += A[i]*S%P
print(ans%P)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
P = 10**9+7
ans = 0

for i in range(N):
    for j in range(i+1,N):
        ans += ((A[i]%P)*(A[j]%P))%P
print(ans%P)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
P = 10**9+7
ans = 0
S = sum(A)

for i in range(N):
    S -= A[i]
    ans += A[i]*S%P
print(ans%P)
Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
A = list(map(int,input().split()))
x = 1
step = 0
count = [0]*N
count[0] += 1
memo = [-1]*N
memo[0] = 0
M = K
for i in range(M):
    x = A[x-1]
    count[x-1] += 1
    step += 1
    K -= 1
    if memo[x-1] != -1:
        s = memo[x-1]
        t = step-s
#        print(s,t)
        break
    memo[x-1] = step
#    print(step,x,count,memo)

K %= t
for i in range(K):
    x = A[x-1]
print(x)


Fixed submission:
N,K = map(int,input().split())
A = list(map(int,input().split()))
x = 1
step = 0
count = [0]*N
count[0] += 1
memo = [-1]*N
memo[0] = 0
M = K
flag = 0
for i in range(M):
    x = A[x-1]
    count[x-1] += 1
    step += 1
    K -= 1
    if memo[x-1] != -1:
        s = memo[x-1]
        t = step-s
#        print(s,t)
        flag = 1
        break
    memo[x-1] = step
#    print(step,x,count,memo)
if flag == 0:
    print(x)
else:
    if t>= 1:
        K %= t
    else:
        K = 1
    for i in range(K):
        x = A[x-1]
    print(x)
Buggy python submission (verdict: Runtime Error):
import numpy as np
A,B,N = map(int,input().split())

x= np.arange(0,N+1,1)
y1 = np.floor(A*x/B)
y2 = A*np.floor(x/B)
y3 = y1-y2

print(int(max(y3)))



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

def f(x):
    v = math.floor(A*x/B)-A*math.floor(x/B)
    return v

if N>=B-1:
    print(f(B-1))
else:
    print(f(N))
Buggy python submission (verdict: Time Limit Exceeded):
import math
K = int(input())
ans = 0
memo = {}


for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            s = {i,j,k}
            s = tuple(s)
            if s in memo.keys():
                ans += memo[s]
            else:
                tmp = math.gcd(j,k)
                tmp = math.gcd(tmp,i)
                ans += tmp
                memo[s] = tmp

print(ans)

Fixed submission:
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())
ans = 0
memo = {}

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans  += gcd(i,j,k)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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])
    return d

n,X,Y = map(int,input().split())

d = [[float("inf")]*n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)

ans = [0]*(n-1)

for i in range(n-1):
    d[i][i+1] = 1
    d[i+1][i] = 1
d[Y-1][X-1] = 1
d[X-1][Y-1] = 1

for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
d = warshall_floyd(d)

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

for i in range(n-1):
    print(ans[i])

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

X -= 1
Y -= 1
ans = [0]*(N)

d = [[N]*N for i in range(N)]

for i in range(N):
    for j in range(i,N):
        if i<=X and Y<=j:
            d[i][j] = X-i+j-Y+1
        else:
            d[i][j] = min(abs(i-X)+abs(Y-j)+1,j-i)



for i in range(N):
    for j in range(i+1,N):
        ans[d[i][j]] += 1

for i in range(1,N):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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])
    return d

n,X,Y = map(int,input().split())

d = [[float("inf")]*n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)

ans = [0]*(n-1)

for i in range(n-1):
    d[i][i+1] = 1
    d[i+1][i] = 1
d[Y-1][X-1] = 1
d[X-1][Y-1] = 1

for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
d = warshall_floyd(d)

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

for i in range(n-1):
    print(ans[i])

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

X -= 1
Y -= 1
ans = [0]*(N)

d = [[N]*N for i in range(N)]

for i in range(N):
    for j in range(i,N):
        if i<=X and Y<=j:
            d[i][j] = X-i+j-Y+1
        else:
            d[i][j] = min(abs(i-X)+abs(Y-j)+1,j-i)



for i in range(N):
    for j in range(i+1,N):
        ans[d[i][j]] += 1

for i in range(1,N):
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
#import sys
#input = sys.stdin.readline

S = input()
Q = int(input())
W = 0
ans = S

for _ in range(Q):
#    print(W,ans)
    qry = list(input().split())
    if qry[0] == "1":
        W = 1-W
        continue
    T,F,C = qry
    T = int(T)
    F = int(F)
    if (W == 0 and F==2) or (W==1 and F==1):
        ans = ans+C
    else:
        ans = C+ans
if W == 1:
    ans = ans[::-1]
print(ans)

Fixed submission:
from collections import deque

S = input()
Q = int(input())
W = 0
ans = deque(list(S.rstrip()))

for _ in range(Q):
#    print(W,ans)
    qry = list(input().rstrip().split())
    if qry[0] == "1":
        W = 1-W
        continue
    T,F,C = qry
    C.rstrip()
    if (W == 0 and F=="2") or (W==1 and F=="1"):
        ans.append(C)
    else:
        ans.appendleft(C)
ans = "".join(map(str,ans))
if W == 1:
    ans = ans[::-1]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))

count = 0
memo = []

for i in range(N):
  if A[i] not in memo:
    count += 1
    memo.append(A[i])
if N == count:
  print("YES")
else:
  print("NO")

Fixed submission:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))

count = Counter(A)
memo = []

for v in count.values():
  if v >= 2:
    print("NO")
    exit()
else:
  print("YES")

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

for i in range(N):
    for j in range(i+1,N):
        if A[i] == A[j]:
            print("NO")
            exit()
print("YES")

Fixed submission:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))

count = Counter(A)
memo = []

for v in count.values():
  if v >= 2:
    print("NO")
    exit()
else:
  print("YES")

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

for i in range(N):
    for j in range(i+1,N):
        if A[i] == A[j]:
            print("NO")
            exit()
print("YES")

Fixed submission:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))

count = Counter(A)
memo = []

for v in count.values():
  if v >= 2:
    print("NO")
    exit()
else:
  print("YES")
Buggy python submission (verdict: Runtime Error):
N,K = map(int, input().split())
p = list(map(int, input().split()))

sum_memo = [0]*1001
x_memo = [0] * 1000
x_list = [0]*N

for i in range(1,1001):
    sum_memo[i] = sum_memo[i-1] + i

for i in range(N):
    if x_memo[p[i]] == 0:
        x_memo[p[i]] = sum_memo[p[i]]/p[i]
    x_list[i] = x_memo[p[i]]


ans = 0
tmp = sum(x_list[:K])
for l in range(N-K):
    r = l+K
    tmp = tmp -  x_list[l] + x_list[r]
    ans = max(ans, tmp)
print(ans)


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

sum_memo = [0]*1001
x_memo = [0] * 1001
x_list = [0]*N

for i in range(1,1001):
    sum_memo[i] = sum_memo[i-1] + i

for i in range(N):
    if x_memo[p[i]] == 0:
        x_memo[p[i]] = sum_memo[p[i]]/p[i]
    x_list[i] = x_memo[p[i]]


ans = 0
tmp = sum(x_list[:K])
#print(tmp)
#print(x_list)
if N==K:
    print(tmp)
    exit()
for l in range(N-K):
    r = l+K
    tmp = tmp -  x_list[l] + x_list[r]
#    print(l,r,x_list[l], x_list[r], tmp)
    ans = max(ans, tmp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

H,N = map(int, input().split())
table = []
dp = [10**9]*(H+1)
dp[0] = 0

for i in range(N):
    a,b = map(int, input().split())
    table.append((a,b))

for i in range(1,H+1):
#    print(dp)
    for j in range(N):
        a,b = table[j]
        if i<a:
            dp[i] = min(dp[i],b)
        else:
            dp[i] = min(dp[i],dp[i-a]+b)
print(dp[-1])

Fixed submission:
import sys
input = sys.stdin.readline

H,N = map(int, input().split())
table = []
dp = [10**9]*(H+1)
dp[0] = 0

for i in range(N):
    a,b = map(int, input().split())
    table.append((a,b))

for i in range(1,H+1):
#    print(dp)
    for j in range(N):
        a,b = table[j]
        if i<a:
            dp[i] = min(dp[i],b)
        else:
            dp[i] = min(dp[i],dp[i-a]+b)
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
import numpy as np
N = int(input())
D = np.array(input().split(), dtype=np.int64)

C = np.zeros(max(D)+1)
for i in range(N):
    C[D[i]] += 1
    
if D[0] != 0 or C[0] != 1:
    ans = 0
    print(ans)
    exit()

ans = 1
for i in range(1,max(D)+1):
  ans *= C[i-1]**C[i]
  ans %= 998244353
print(int(ans))


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

count = [0]*(max(D)+1)
ans = 1

for i in range(N):
    count[D[i]] += 1

if count[0] != 1 or D[0] != 0:
  print(0)
  exit()
 
for i in range(1,max(D)+1):
    ans *= count[i-1]**count[i]
    ans %= 998244353
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.extend([b]*e)
        b, e = b + 1, 0
    if n > 1:
        fct.extend([n]*1)
    return fct

N = int(input())
arr = factorize(N)
M = len(arr)
ans = N
for i in range(2**(M-1)):
    A = 1
    B = 1
    for j in range(M):
        if (i>>j)&1:
            A *= arr[j]
    B = N//A
    A = max(A-1,0)
    B = max(B-1,0)
    ans = min(ans,A+B)

print(ans)

Fixed submission:
import math
N = int(input())
tmp = math.ceil(N**(1/2))
ans = N
for i in range(1,tmp+1):
    if N%i == 0:
        A = max(N//i-1,0)
        B = max(i-1,0)
        ans = min(ans,A+B)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.extend([b]*e)
        b, e = b + 1, 0
    if n > 1:
        fct.extend([n]*1)
    return fct

N = int(input())
arr = factorize(N)
M = len(arr)
ans = N
for i in range(2**M):
    A = 1
    B = 1
    for j in range(M):
        if (i>>j)&1:
            A *= arr[j]
        else:
            B *= arr[j]
    A = max(A-1,0)
    B = max(B-1,0)
    ans = min(ans,A+B)

print(ans)

Fixed submission:
import math
N = int(input())
tmp = math.ceil(N**(1/2))
ans = N
for i in range(1,tmp+1):
    if N%i == 0:
        A = max(N//i-1,0)
        B = max(i-1,0)
        ans = min(ans,A+B)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.extend([b]*e)
        b, e = b + 1, 0
    if n > 1:
        fct.extend([n]*1)
    return fct

N = int(input())
arr = factorize(N)
M = len(arr)
ans = N
for i in range(2**M):
    A = 1
    B = 1
    for j in range(M):
        if (i>>j)&1:
            A *= arr[j]
        else:
            B *= arr[j]
    A = max(A-1,0)
    B = max(B-1,0)
    ans = min(ans,A+B)

print(ans)

Fixed submission:
import math
N = int(input())
tmp = math.ceil(N**(1/2))
ans = N
for i in range(1,tmp+1):
    if N%i == 0:
        A = max(N//i-1,0)
        B = max(i-1,0)
        ans = min(ans,A+B)

print(ans)
Buggy python submission (verdict: Runtime Error):
import math
a,b,x = map(int, input().split())

ans1 = (b-x/(a**2))*2/a
ans1 = math.degrees(math.asin(ans1))

ans2 = a*(b**2)/(2*x)
ans2 = math.degrees(math.atan(ans2))
print(min(ans1,ans2))

Fixed submission:
import math
a,b,x = map(int, input().split())

theta1 = math.atan((2/a*(b-x/(a**2))))
if math.tan(theta1) <= 2*x/(a**3):
  print(math.degrees(theta1))
  exit()
else:
  theta2 = math.atan(a*b**2/(2*x))
  print(math.degrees(theta2))
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush, heapify
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
F = [int(i) for i in input().split()]
A.sort()
F.sort(reverse=True)
H = []
for i in range(N):
    H.append((-A[i]*F[i],F[i]))
heapify(H)

while K>0:
    K -= 1
    x,y = heappop(H)
    x = min(0,x+y)
    heappush(H,(x,y))
print(-H[0][0])

Fixed submission:
n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort()
f.sort(reverse=True)


ng = -1
ok = 10**12
while ok-ng > 1:
    mid = (ok+ng)//2
    cnt = 0

    for i,e in enumerate(a):    
        cnt += max(0,e-mid//f[i])
    if cnt <= k:
        ok = mid
    else:
        ng = mid

print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
F = [int(i) for i in input().split()]
A.sort()
F.sort(reverse=True)
H = []
for i in range(N):
    heappush(H,(-A[i]*F[i],F[i]))

while K>0:
    K -= 1
    x,y = heappop(H)
    x = min(0,x+y)
    heappush(H,(x,y))
print(-H[0][0])

Fixed submission:
n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort()
f.sort(reverse=True)


ng = -1
ok = 10**12
while ok-ng > 1:
    mid = (ok+ng)//2
    cnt = 0

    for i,e in enumerate(a):    
        cnt += max(0,e-mid//f[i])
    if cnt <= k:
        ok = mid
    else:
        ng = mid

print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
F = [int(i) for i in input().split()]
A.sort()
F.sort(reverse=True)
H = []
for i in range(N):
    heappush(H,(-A[i]*F[i],F[i]))

while K>0:
    K -= 1
    x,y = heappop(H)
    x = min(0,x+y)
    heappush(H,(x,y))
print(-H[0][0])

Fixed submission:
n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort()
f.sort(reverse=True)


ng = -1
ok = 10**12
while ok-ng > 1:
    mid = (ok+ng)//2
    cnt = 0

    for i,e in enumerate(a):    
        cnt += max(0,e-mid//f[i])
    if cnt <= k:
        ok = mid
    else:
        ng = mid

print(ok)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
N,M,L = map(int, input().split())
INF = float("inf")
dist1 = [[INF]*N for i in range(N)]
dist2 = [[INF]*N for i in range(N)]

for i in range(M):
  A,B,C = map(int, input().split())
  A -= 1
  B -= 1
  dist1[A][B] = C
  dist1[B][A] = C

for i in range(N):
  dist1[i][i] = 0
  dist2[i][i] = 0
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      dist1[i][j] = min(dist1[i][j], dist1[i][k]+dist1[k][j])
for i in range(N):
  for j in range(N):
    if dist1[i][j] > L:
      continue
    if i==j:
      dist2[i][j] = 0
    else:
      dist2[i][j] = 1
for k in range(N):
  for i in range(N):
    for j in range(N):
      dist2[i][j] = min(dist2[i][j], dist2[i][k]+dist2[k][j])
Q = int(input())
for i in range(Q):
  s,t = map(int, input().split())
  print(dist2[s-1][t-1]-1 if dist2[s-1][t-1]<=L else -1)

Fixed submission:
import sys
input = sys.stdin.readline
N,M,L = map(int, input().split())
INF = float("inf")
dist1 = [[INF]*N for i in range(N)]
dist2 = [[INF]*N for i in range(N)]

for i in range(M):
  A,B,C = map(int, input().split())
  A -= 1
  B -= 1
  dist1[A][B] = C
  dist1[B][A] = C

for i in range(N):
  dist1[i][i] = 0
  dist2[i][i] = 0
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      d = dist1[i][k]+dist1[k][j]
      if dist1[i][j] <= d:
        continue
      dist1[i][j] = d
for i in range(N):
  for j in range(N):
    if dist1[i][j] > L or i==j:
      continue
    dist2[i][j] = 1
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      d = dist2[i][k]+dist2[k][j]
      if dist2[i][j] <= d:
        continue
      dist2[i][j] = d
Q = int(input())
for i in range(Q):
  s,t = map(int, input().split())
  print(dist2[s-1][t-1]-1 if dist2[s-1][t-1]<=L else -1)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
V = []
INF = float("inf")
dp = [INF]*(1<<N)
dp[0] = 0
for i in range(M):
  a,b = map(int, input().split())
  c = list(map(int, input().split()))
  k = 0
  for j in range(b):
    k |= 1<<(c[j]-1)
  V.append((a,k))
  dp[k] = min(dp[k],a)

for i in range(1<<N):
  for a,k in V:
    dp[i|k] = min(dp[i|k],dp[i]+dp[k])  
print(dp[-1] if dp[-1] != INF else -1)

Fixed submission:
N, M = map(int, input().split())
INF = float("inf")
V = [INF] * (1<<N)
V[0] = 0
for i in range(M):
  v,_ = map(int, input().split())
  b = 0
  s = list(map(int, input().split()))
  for a in s:
    b |= (1<<(a-1))
  V[b] = min(V[b], v) #宝箱の集合bを開けるための最小コスト

vbs = [] #（最小コスト、宝箱の集合b）のリスト、ただしコストINFのものを除く
for b,v in enumerate(V):
  if v == INF:
    continue
  vbs.append((v,b))

for v,b in vbs:
  for c in range(1<<N):
    if V[c] == INF:
      continue
    V[b|c] = min(V[b|c], V[b]+V[c])

print(V[-1] if V[-1] < INF else -1)
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())
    S = input()
    ans = 0
    for i in range(1,N):
      S1 = S[:i]
      S2 = S[i:]
      ans = max(ans,lcs(S1, S2))
    print(ans)

if __name__ == '__main__':
    solve()

Fixed submission:
S = input()
N = len(S)
for i in range(0,N,2):
  if S[i] == "L":
    print("No")
    exit()
for i in range(1,N,2):
  if S[i] == "R":
    print("No")
    exit()
print("Yes")