Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n, k = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

INF = 10 ** 18
DP = [INF] * n
DP[0] = 0

for i in range(1, n):
    DP[i] = min(DP[i-j] + abs(H[i] - H[i-j]) for j in range(1, k+1) if i - j >= 0)

print(DP[n-1])


Fixed submission:
n, k = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

INF = 10 ** 18
DP = [INF] * n
DP[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if i + j >= n:
            break
        DP[i+j] = min(DP[i+j], DP[i] + abs(H[i+j] - H[i]))

print(DP[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

INF = 10 ** 18
DP = [INF] * n
DP[0] = 0

for i in range(1, n):
    DP[i] = min(DP[i-j] + abs(H[i] - H[i-j]) if i - j >= 0 else INF for j in range(1, k+1))

print(DP[n-1])

Fixed submission:
n, k = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

INF = 10 ** 18
DP = [INF] * n
DP[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if i + j >= n:
            break
        DP[i+j] = min(DP[i+j], DP[i] + abs(H[i+j] - H[i]))

print(DP[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

INF = 10 ** 18
DP = [INF] * n
DP[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if i + j >= n:
            break
        DP[i+j] = min(DP[i+j], DP[i] + abs(H[i+j] - H[i]))

print(DP[n-1])

Fixed submission:
n, k = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

INF = 10 ** 18
DP = [INF] * n
DP[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if i + j >= n:
            break
        DP[i+j] = min(DP[i+j], DP[i] + abs(H[i+j] - H[i]))

print(DP[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = [int(i) for i in input().split()]
V = [[int(i) for i in input().split()] for j in range(N)]

DP = [0] * (W+1)
V.sort(key=lambda x: x[1])

for w, v in V:
    for i in range(W, -1, -1):
        if w > i:
            break
        DP[i] = max(DP[i], DP[i-w] + v)

print(DP[W])

Fixed submission:
N, W = [int(i) for i in input().split()]
V = [[int(i) for i in input().split()] for j in range(N)]

DP = [0] * (W+1)
V.sort(key=lambda x: x[1])

for w, v in V:
    for i in range(W, -1, -1):
        if w > i:
            break
        DP[i] = max(DP[i], DP[i-w] + v)

print(DP[W])
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
T = input()
n = len(S)
m = len(T)

DP = [[''] * (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] + S[i]
        else:
            DP[i+1][j+1] = DP[i+1][j] if len(DP[i+1][j]) > len(DP[i][j+1]) else DP[i][j+1]
        
print(DP[n][m])

Fixed submission:
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+1][j], DP[i][j+1])

ans = ''
while n > 0 and m > 0:
    if S[n-1] == T[m-1]:
        n -= 1
        m -= 1
        ans += S[n]
    elif DP[n][m-1] > DP[n-1][m]:
        m -= 1
    else:
        n -= 1

print(ans[::-1])
Buggy python submission (verdict: Runtime Error):
n, m = [int(i) for i in input().split()]
X = [[int(i) for i in input().split()] for j in range(m)]

E = [[] for i in range(n+1)]

for a, b in X:
    E[a].append(b)

memo = [-1] * (n+1)

def dfs(i):
    if memo[i] != -1:
        return memo[i] + 1
    if not E[i]:
        return 0

    memo[i] = max(dfs(e) for e in E[i])
    return memo[i] + 1

print(max(dfs(i) for i in range(1, n+1)))

Fixed submission:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, m = [int(i) for i in input().split()]
X = [[int(i) for i in input().split()] for j in range(m)]

E = [[] for i in range(n+1)]

for a, b in X:
    E[a].append(b)

memo = [-1] * (n+1)

def dfs(i):
    if memo[i] != -1:
        return memo[i] + 1
    if not E[i]:
        return 0

    memo[i] = max(dfs(e) for e in E[i])
    return memo[i] + 1

print(max(dfs(i) for i in range(1, n+1)))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
P = [float(i) for i in input().split()]

DP = [[0] * (n+1) for j in range(n+1)]
DP[0][0] = 1

for i in range(n):
    for j in range(n):
        DP[i+1][j+1] += DP[i][j] * P[i]
        DP[i+1][j] += DP[i][j] * (1 - P[i])

print(sum(DP[n][(n+1)//2:]))

Fixed submission:
n = int(input())
P = [float(i) for i in input().split()]

DP = [[0] * (n+1) for j in range(n+1)]
DP[0][0] = 1

for i in range(n):
    for j in range(n):
        DP[i+1][j+1] += DP[i][j] * P[i]
        DP[i+1][j] += DP[i][j] * (1 - P[i])

print(sum(DP[n][(n+1)//2:]))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
a, b, c = [C[i] for i in range(3, 0, -1)]

DP = [[[-1] * (a + b + c + 1) for i in range(a + b + 1)] for j in range(a + 1)]
DP[0][0][0] = 0

def dfs(i, j, k):
    if DP[i][j][k] != -1:
        return DP[i][j][k]
    
    DP[i][j][k] = 1
    if i > 0: DP[i][j][k] += i / n * dfs(i - 1, j + 1, k)
    if j > 0: DP[i][j][k] += j / n * dfs(i, j - 1, k + 1)
    if k > 0: DP[i][j][k] += k / n * dfs(i, j, k - 1)
    DP[i][j][k] *= n / (i + j + k)

    return DP[i][j][k]

print(dfs(a, b, c))

Fixed submission:
from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
a, b, c = [C[i] for i in range(3, 0, -1)]

DP = [[[-1] * (a + b + c + 1) for i in range(a + b + 1)] for j in range(a + 1)]
DP[0][0][0] = 0

for i in range(a + 1):
    for j in range(a + b - i + 1):
        for k in range(a + b + c - i - j + 1):
            if i == j == k == 0:
                continue
            DP[i][j][k] = 1
            if i > 0: DP[i][j][k] += i / n * DP[i - 1][j + 1][k]
            if j > 0: DP[i][j][k] += j / n * DP[i][j - 1][k + 1]
            if k > 0: DP[i][j][k] += k / n * DP[i][j][k - 1]
            DP[i][j][k] *= n / (i + j + k)

print(DP[a][b][c])

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

n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
a, b, c = [C[i] for i in range(3, 0, -1)]

DP = [[[-1] * (a + b + c + 1) for i in range(a + b + 1)] for j in range(a + 1)]
DP[0][0][0] = 0

def dfs(i, j, k):
    if DP[i][j][k] != -1:
        return DP[i][j][k]
    
    DP[i][j][k] = 1
    DP[i][j][k] += i / n * dfs(i - 1, j + 1, k) if i != 0 else 0
    DP[i][j][k] += j / n * dfs(i, j - 1, k + 1) if j != 0 else 0
    DP[i][j][k] += k / n * dfs(i, j, k - 1) if k != 0 else 0
    DP[i][j][k] *= n / (i + j + k)

    return DP[i][j][k]

print(dfs(a, b, c))

Fixed submission:
from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
a, b, c = [C[i] for i in range(3, 0, -1)]

DP = [[[-1] * (a + b + c + 1) for i in range(a + b + 1)] for j in range(a + 1)]
DP[0][0][0] = 0

for i in range(a + 1):
    for j in range(a + b - i + 1):
        for k in range(a + b + c - i - j + 1):
            if i == j == k == 0:
                continue
            DP[i][j][k] = 1
            if i > 0: DP[i][j][k] += i / n * DP[i - 1][j + 1][k]
            if j > 0: DP[i][j][k] += j / n * DP[i][j - 1][k + 1]
            if k > 0: DP[i][j][k] += k / n * DP[i][j][k - 1]
            DP[i][j][k] *= n / (i + j + k)

print(DP[a][b][c])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = [int(i) for i in input().split()]

DP = [[0] * n for i in range(n)]
if n % 2 == 1:
    for i in range(n):
        DP[i][i] = A[i]
else:
    for i in range(n):
        DP[i][i] = -A[i]

for i in range(1, n):
    for l in range(n-i):
        if (n - i) % 2 == 1:
            DP[l][l+i] = max(DP[l+1][l+i] + A[l], DP[l][l+i-1] + A[l+i])
        else:
            DP[l][l+i] = min(DP[l+1][l+i] - A[l], DP[l][l+i-1] - A[l+i])

score = [0] * 2
l = 0
r = n - 1

for i in range(n-2):
    if A[l] + A[r - 1] > A[r] + A[l + 1]:
        score[i%2] += A[l]
        l += 1
    else:
        score[i%2] += A[r]
        r -= 1

score[n%2] += max(A[l], A[r])
score[(n+1)%2] += min(A[l], A[r])

if n % 2 == 0:
    print(score[0] - score[1])
else:
    print(DP[0][n-1])


Fixed submission:
n = int(input())
A = [int(i) for i in input().split()]

DP = [[0] * n for i in range(n)]
if n % 2 == 1:
    for i in range(n):
        DP[i][i] = A[i]
else:
    for i in range(n):
        DP[i][i] = -A[i]

for i in range(1, n):
    for l in range(n-i):
        if (n - i) % 2 == 1:
            DP[l][l+i] = max(DP[l+1][l+i] + A[l], DP[l][l+i-1] + A[l+i])
        else:
            DP[l][l+i] = min(DP[l+1][l+i] - A[l], DP[l][l+i-1] - A[l+i])

print(DP[0][n-1])
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = [int(input()) for i in range(n)]
B = [i % 2 for i in A]

print('first' if sum(B) % 2 != 0 or (any(b == 1 for b in B) and (max(A) - min(A)) <= 1) else 'second')

Fixed submission:
from collections import defaultdict
from math import sqrt

n, p = [int(i) for i in input().split()]

A = defaultdict(int)

def factorize(n):    
    i = 2
    
    while n % i == 0:
        n //= i
        A[i] += 1
    i += 1

    while n != 1 and i <= sqrt(n):
        while n % i == 0:
            n //= i
            A[i] += 1
        i += 2
    if n != 1:
        A[n] += 1

    return A

factorize(p)
ans = 1
for k, v in A.items():
    if v >= n:
        ans *= k ** (v // n)

print(ans)
Buggy python submission (verdict: Runtime Error):
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    _ = int(input())
    A = [int(i) for i in input().split()]

    ans = 0
    c = Counter(A)
    B = sorted(c.keys(), reverse=True)

    for b in B:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            if a in c.keys():
                cur = min(c[a], c[b])
            else:
                cur = 0
        ans += cur
        # c[b] -= cur
        c[a] -= cur

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
S = input()

ans = 0
f = -1

for i, s in enumerate(S):
    if f != -1 and s == 'W':
        ans += i - f
        f += 1
    elif f == -1 and s == 'B':
        f = i

print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())
A = [int(i) for i in input().split()]

A.sort()
m = 1 << 30
used = [False] * n
ans = 0

def search(ok, ng, n):
    if abs(ok-ng) <= 1:
            return ok
    mid = (ok+ng) // 2
    if A[mid] < n or (A[mid] == n and used[mid]):
        return search(mid, ng, n)
    else:
        return search(ok, mid, n)

for i in range(30):
    for j in range(n):
        if used[j] or A[j] >= m:
            continue
        a = search(-1, n, m - A[j]) + 1
        if a >= n:
            continue
        if A[a] == m - A[j]:
            if a == j:
                a += 1
                if a >= n or not A[a] == A[j]:
                    continue
            used[a] = True
            used[j] = True
            ans += 1
    m >>= 1

print(ans)

Fixed submission:
S = input()

ans = 0
f = -1

for i, s in enumerate(S):
    if f != -1 and s == 'W':
        ans += i - f
        f += 1
    elif f == -1 and s == 'B':
        f = i

print(ans)
Buggy python submission (verdict: Runtime Error):
from math import log10

n = int(input())
m = int(log10(n)) + 1

ans = 0

def dfs(i, s):
    if i == m:
        if not '0' in all(a in str(int(s)) a in '753') and int(s) <= n:
            return 1
        return 0
    res = 0
    for a in '0357':
        res += dfs(i+1, s + a)
    return res

print(dfs(0, ''))


Fixed submission:
n = int(input())
print('YES' if n == 3 or n == 5 or n == 7 else 'NO')
Buggy python submission (verdict: Runtime Error):
n = int(input())
X = [[int(i) for i in input().split()] for j in range(n)]

x_s = 0
x_e = 100
y_s = 0
y_e = 100

for x, y, z in X:
    for x2, y2, z2 in X:
        if (x, y) == (x2, y2):
            continue
        d = abs(x-x2) + abs(y-y2)
        if d == z - z2:            
            if x < x2:
                x_e = min(x_e, x) #左側
            elif x > x2:
                x_s = max(x_s, x) #右側
            if y < y2:
                y_e = min(y_e, y) #上川
            else y > y2:
                y_s = max(y_s, y) #下側

        else:
            if x < x2:
                x_s = max(x_s, x) #左側
            elif x > x2:
                x_e = min(x_e, x) #右側
            if y < y2:
                y_s = max(y_s, y) #上川
            elif y > y2:
                y_e = min(y_e, y) #下側

x, y, z = X[0]
print(x_e, y_e, z + abs(x_e - x) + abs(y_e - y))

Fixed submission:
n = int(input())
X = [[int(i) for i in input().split()] for j in range(n)]

X.sort(key=lambda x:x[2], reverse=True)

for h in range(101):
    for w in range(101):
        x, y, z = X[0]
        d = z + abs(x-w) + abs(y-h)
        for x, y, z in X:
            d2 = z + abs(x-w) + abs(y-h)
            if z == 0:
                if d2 < d:
                    break 
            elif d2 != d:
                break
        else:
            print(w, h, d)
            exit()
Buggy python submission (verdict: Runtime Error):
n, p = [int(i) for i in input().split()]
X = [int(i) for i in input().split()]

memo = [[-1] * (n+1) for i in range(n+1)]

def dfs(i, k):
    if memo[i][k] != -1:
        return memo[i][k]
    elif i == 0:
        return min(p + (k+2) ** 2 * X[i] + p, (k + 1) ** 2 * X[i] + p + X[i] + p + 4 * X[i] + p)

    memo[i][k] = min(dfs(i-1, k+1) + p + (k+2) ** 2 * (X[i] - X[i-1]),
                    dfs(i-1, 1) + (k + 1) ** 2 * X[i] + p + X[i] + p + 4 * (X[i] - X[i-1]))

    return memo[i][k]

print(dfs(n-1, 0) + X[-1])

Fixed submission:
n, p = [int(i) for i in input().split()]
X = [int(i) for i in input().split()]

ans = []
S = [0]

for x in X:
    S.append(S[-1] + x)

for t in range(1, n+1):
    cur = n - t
    time = 5
    tmp = time * (S[-1] - S[cur]) + (t + n) * p
    cur -= t
    while True:
        tmp += time * (S[cur+t] - S[max(0,cur)])
        if cur <= 0:
            break
        cur -= t
        time += 2

    ans.append(tmp)

print(min(ans))
Buggy python submission (verdict: Runtime Error):
H, W = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(H)]

ans = []
dx = -1
w = 0

for h in range(H):
    dx *= -1
    for j in range(W):
        if A[h][w] % 2 == 1:
            A[h][w] -= 1
            a = [h+1, w+1]
            if w + dx < 0 or w + dx >= W:
                if h + 1 == H:
                    break
                A[h+1][w] += 1
                a += [h+2, w+1]
            else:
                A[h][w+dx] += 1
                a += [h+1, w+1+dx]
            ans.append(a)
        w += dx
        
print(len(ans))
for a in ans:
    print(*a)


Fixed submission:
H, W = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(H)]

ans = []
dx = -1
w = 0

for h in range(H):
    dx *= -1
    for j in range(W):
        if A[h][w] % 2 == 1:
            A[h][w] -= 1
            a = [h+1, w+1]
            if w + dx < 0 or w + dx >= W:
                if h + 1 == H:
                    break
                A[h+1][w] += 1
                a += [h+2, w+1]
            else:
                w += dx
                A[h][w] += 1
                a += [h+1, w+1]
            ans.append(a)
            
        elif 0 <= w + dx < W:
            w += dx
            
            
        

print(len(ans))
for a in ans:
    print(*a)
Buggy python submission (verdict: Runtime Error):
n, k = [int(i) for i in input().split()]

ans = [0, 0]

for i in range(1, n+1):
    if k % 2 == 0 and i % k == d:
        ans[0] += 1
    if i % k == 0:
        ans[1] += 1

print(ans[0] ** 3 + ans[1] ** 3)

Fixed submission:
n, k = [int(i) for i in input().split()]

ans = [0, 0]
d = k // 2

for i in range(1, n+1):
    if k % 2 == 0 and i % k == d:
        ans[0] += 1
    if i % k == 0:
        ans[1] += 1

print(ans[0] ** 3 + ans[1] ** 3)
Buggy python submission (verdict: Runtime Error):
n = int(input())

ans = 'ABC' if n <= 999: else 'ABD'

print(ans)

Fixed submission:
n = int(input())

ans = 'ABC' if n <= 999 else 'ABD'

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, c = [int(i) for i in input().split()]
D = [[int(i) for i in input().split()] for j in range(c)]
C = [[int(i) for i in input().split()] for j in range(n)]

# for i in range(c):
#   for j in range(c):
#     for k in range(c):
#       d = D[i][j] + D[j][k]
#       if D[i][k] > d:
#         D[i][k] = d

sum_d = [[0] * c for i in range(3)]

for i in range(n):
  for j in range(n):
    for k in range(c):
      sum_d[(i+j)%3][k] += D[C[i][j]-1][k]
      
max_d = 1000 * (n//3+1)
ans = max_d * n**2
      
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i != j != k != i:
        ans = min(ans, sum_d[0][i] + sum_d[1][j] + sum_d[2][k])
        
print(ans)

Fixed submission:
n, c = [int(i) for i in input().split()]
D = [[int(i) for i in input().split()] for j in range(c)]
C = [[int(i) for i in input().split()] for j in range(n)]

# for i in range(c):
#   for j in range(c):
#     for k in range(c):
#       d = D[i][j] + D[j][k]
#       if D[i][k] > d:
#         D[i][k] = d

sum_d = [[0] * c for i in range(3)]
mod_c = [[0] * c for i in range(3)]

for i in range(n):
  for j in range(n):
      mod_c[(i+j)%3][C[i][j]-1] += 1

for i in range(c):
    for j in range(c):
        for k in range(3):
            sum_d[k][j] += D[i][j] * mod_c[k][i]
      
max_d = 1000 * (n//3+1)
ans = max_d * n**2
      
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i != j != k != i:
        ans = min(ans, sum_d[0][i] + sum_d[1][j] + sum_d[2][k])
        
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()

ans = 3 * 10**5

for i in range(n):
    ans = min(ans, s[:i].count('W') + s[i+1:].count('E'))

print(ans)

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

ans = 3 * 10**7
w = [0]
e = [0]

for i, a in enumerate(s):
    if a == 'W':
        w.append(w[-1]+1)
    else:
        w.append(w[-1])

for i, a in enumerate(s[::-1]):
    if a == 'E':
        e.append(e[-1]+1)
    else:
        e.append(e[-1])

e.reverse()

for i in range(n):
    ans = min(ans, w[i]+e[i+1])

print(ans)

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

ans = s.count('W')
ans = min(ans, s.count('E'))

for i in range(n):
    test = s[:i]
    test = s[i+1:]
    ans = min(ans, s[:i].count('W') + s[i+1:].count('E'))

print(ans)

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

ans = 3 * 10**7
w = [0]
e = [0]

for i, a in enumerate(s):
    if a == 'W':
        w.append(w[-1]+1)
    else:
        w.append(w[-1])

for i, a in enumerate(s[::-1]):
    if a == 'E':
        e.append(e[-1]+1)
    else:
        e.append(e[-1])

e.reverse()

for i in range(n):
    ans = min(ans, w[i]+e[i+1])

print(ans)
Buggy python submission (verdict: Runtime Error):
from sympy import perfect_power

x = int(input())

ans = 1

for i in range(x, 1, -1):
    if perfect_power(i):
        ans = i
        break

print(ans)

Fixed submission:
x = int(input())

def is_power(a, b):
  while a % b == 0:
    a = a / b
  if a == 1:
    return True
  return False

def is_perfect_power(n):
    for i in range(n//2, 1, -1):
        if is_power(n, i):
            return True
    return False

ans = 1

for i in range(x, 1, -1):
    if is_perfect_power(i):
        ans = i
        break

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

sset = set()

for i in range(1, len(s)+1):
    sset |= set([s[j:j+i] for j in range(0, len(s))])

print(sorted(sset)[k-1])

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

sset = set()

for i in range(1, 6):
    sset |= set([s[j:j+i] for j in range(0, len(s))])

print(sorted(sset)[k-1])
Buggy python submission (verdict: Time Limit Exceeded):
from copy import deepcopy

n, m = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for j in range(m)]

x_ = deepcopy(x)
tree = []
memo = []

try:
    for i, y in enumerate(x_):
        if y in memo:
            continue
        tree.append(set(y))
        while True:
            prev = tree[i]
            for j in x_[i+1:]:
                if tree[i] & set(j):
                    tree[i] = tree[i] | set(j)
                    memo.append(j)

            if not tree[i] - prev:
                break
except:
    pass

for i in tree:
    i = list(i)
    temp = [p[j-1] for j in i]
    for j in i:
        if j in temp:
            p[j-1] = j

ans = 0

for i, p_ in enumerate(p):
    if i+1 == p_:
        ans += 1

print(ans)

Fixed submission:
n, m = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for j in range(m)]

par = [i for i in range(0, n+1)]

def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

def unite(x, y):
    x = root(x)
    y = root(y)
    if x != y:
        par[x] = y

for i in x:
    a, b = i
    unite(a, b)

ans = 0
for i, p_ in enumerate(p):
    if root(i+1) == root(p_):
        ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())

def prime():
    p = [2]
    m = 3
    while m < 1400:
        for i in p:
            if m % i == 0:
                break
        else:
            p.append(m)
        m += 2
    return p

ans = []
q = p[1:]

while len(ans) < n:
    for i, q_ in enumerate(q):
        if q_ % 5 == 1:
            ans.append(q_)
            del q[i]
            break

print(' '.join([str(s) for s in ans]))

Fixed submission:
n = int(input())

def prime():
    p = [2]
    m = 3
    while m < 1400:
        for i in p:
            if m % i == 0:
                break
        else:
            p.append(m)
        m += 2
    return p

ans = []
p = prime()
q = p[1:]

while len(ans) < n:
    for i, q_ in enumerate(q):
        if q_ % 5 == 1:
            ans.append(q_)
            del q[i]
            break

print(' '.join([str(s) for s in ans]))
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = [input() for i in range(n)]

cnt = 0

for i in range(n):
    i_ = (n+i)%n
    for k in range(n):
        for l in range(n):
            if s[(i_+k)%n][l] != s[(i_+l)%n][k]:
                break
        else:
            continue
        break
    else:
        cnt += 1

print(cnt*n)

Fixed submission:
from collections import Counter

n = int(input())
a = [int(i) for i in input().split()]

a_ = [0]

for i in range(n):
    a_.append(a_[i] + a[i])

cnt = 0

def sum(i):
    return int((i + 1) / 2 * i)

for i in Counter(a_).values():
    cnt += sum(i-1)

print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(i) for i in input().split()]

a_ = [0]

for i in range(n):
    a_.append(a_[i] + a[i])

cnt = 0
x = []

for i in a_:
    if i in x:
        cnt += x.count(i)
    x.append(i) 

print(cnt)

Fixed submission:
from collections import Counter

n = int(input())
a = [int(i) for i in input().split()]

a_ = [0]

for i in range(n):
    a_.append(a_[i] + a[i])

cnt = 0

def sum(i):
    return int((i + 1) / 2 * i)

for i in Counter(a_).values():
    cnt += sum(i-1)

print(cnt)