Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
  N, M = list(map(int, input().split()))
  L = {}
  D = [[0, i] for i in range(N+1)]

  for i in range(N + M - 1):
    Data = list(map(int, input().split()))
    if Data[0] in L:
      L[Data[0]].append(Data[1])
    else:
      L[Data[0]] = [Data[1]]
    D[Data[1]][0] += 1

  for i in range(1, N+1):
    if D[i][0] == 0:
     s = D[i][1]
     break

  P = [[0, 0] for i in range(N + 1)]
  S = []
  t = L[s]
  for i in t:
    S.append(i)
    P[i] = [1, s]

  while True:
    if len(S) == 0:
      break
    j = S.pop()
    if j not in L:
      continue
    t = L[j]
    for i in t:
      if P[i][0] != 0:
        if P[i][0] < P[j][0] + 1:
          P[i] = [P[j][0] + 1, j]
          S.append(i)
      else:
        P[i] = [P[j][0] + 1, j]
        S.append(i)
  for i in P[1:]:
    print(i[1])

main()

Fixed submission:
def main():
  N, M = list(map(int, input().split()))
  inN = [0 for i in range(N)]
  outN = [[] for i in range(N)]
  
  for i in range(N + M - 1):
    Data = list(map(int, input().split()))
    inN[Data[1] - 1] += 1
    outN[Data[0] - 1].append(Data[1] - 1)
  
  D = []
  for i in range(N):
    if inN[i] == 0:
      D.append(i)
      
  L = []
  while D != []:
    t = D.pop()
    L.append(t)
    for i in outN[t]:
      inN[i] -= 1
      if inN[i] == 0:
        D.append(i)
   
  Ans = [0 for i in range(N)]
  for i in L:
    for j in outN[i]:
      Ans[j] = i + 1
      
  for i in Ans:
    print(i)
main()

Buggy python submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
L = {}
D = [[0, i] for i in range(N+1)]

for i in range(N + M - 1):
  Data = list(map(int, input().split()))
  if Data[0] in L:
    L[Data[0]].append(Data[1])
  else:
    L[Data[0]] = [Data[1]]
  D[Data[1]][0] += 1

for i in range(1, N+1):
  if D[i][0] == 0:
    s = D[i][1]
    break

P = [[0, 0] for i in range(N + 1)]
S = []
t = L[s]
for i in t:
  S.append([s, i])
  P[i] = [1, s]

cnt = 0
print(P)
while True:
  j = S[cnt][1]
  if j not in L:
    cnt += 1
    continue
  t = L[j]
  for i in t:
    if P[i][0] != 0:
      if P[i][0] < P[j][0] + 1:
        #削除
        L[P[i][1]].remove(i)
        #更新
        P[i] = [P[j][0] + 1, j] 
        M -= 1
      else:
        # 削除
        L[P[j][1]].remove(j)
        M -= 1
  print(P)
  print(L)
  if M == 0:
    break
  cnt += 1


Fixed submission:
def main():
  N, M = list(map(int, input().split()))
  inN = [0 for i in range(N)]
  outN = [[] for i in range(N)]
  
  for i in range(N + M - 1):
    Data = list(map(int, input().split()))
    inN[Data[1] - 1] += 1
    outN[Data[0] - 1].append(Data[1] - 1)
  
  D = []
  for i in range(N):
    if inN[i] == 0:
      D.append(i)
      
  L = []
  while D != []:
    t = D.pop()
    L.append(t)
    for i in outN[t]:
      inN[i] -= 1
      if inN[i] == 0:
        D.append(i)
   
  Ans = [0 for i in range(N)]
  for i in L:
    for j in outN[i]:
      Ans[j] = i + 1
      
  for i in Ans:
    print(i)
main()
Buggy python submission (verdict: Runtime Error):
N, K = list(map(int, input().split()))
td = []
for i in range(N):
  td.append(list(map(int, input().split())))

td.sort(key = lambda x:x[1], reverse = True)

D = []
T = {}
d = 0

for i in range(K):
  D.append(td[i])
  d += td[i][1]
  t = td[i][0]
  if t in T:
    T[t] += 1
  else:
    T[t] = 1

D.sort(key = lambda x: x[1])

cnt = 0
flag = False
Ans = d + pow(len(T), 2)
for i in range(K, N):
  if td[i][0] in T:
    continue
  while T[D[cnt][0]] == 1:
    cnt += 1
    if cnt == N:
      flag = True
      break
  if flag:
    break

  T[td[i][0]] = 1
  T[D[cnt][0]] -= 1
  d -= D[cnt][1] - td[i][1]
  
  t = d + pow(len(T), 2)
  if Ans < t:
    Ans = t
  cnt += 1
  if cnt == N:
    break


print(Ans)

Fixed submission:
N, K = list(map(int, input().split()))
td = []
for i in range(N):
  td.append(list(map(int, input().split())))

td.sort(key = lambda x:x[1], reverse = True)

D = []
T = {}
d = 0

for i in range(K):
  D.append(td[i])
  d += td[i][1]
  t = td[i][0]
  if t in T:
    T[t] += 1
  else:
    T[t] = 1

D.sort(key = lambda x: x[1])

cnt = 0
flag = False
Ans = d + pow(len(T), 2)
for i in range(K, N):
  if td[i][0] in T:
    continue
  while T[D[cnt][0]] == 1:
    cnt += 1
    if cnt == K:
      flag = True
      break
  if flag:
    break

  T[td[i][0]] = 1
  T[D[cnt][0]] -= 1
  d -= D[cnt][1] - td[i][1]
  
  t = d + pow(len(T), 2)
  if Ans < t:
    Ans = t
  cnt += 1
  if cnt == K:
    break

print(Ans)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
  N, W = list(map(int, input().split()))
  Data = []
  for i in range(N):
    Data.append(list(map(int, input().split())))
  
  DP = [0 for i in range(W+1)]
  
  for i in range(N):
    for j in range(W - Data[i][0], -1, -1):
      k = j + Data[i][0]
      DP[k] = max(DP[j] + Data[i][1], DP[k])
  
  print(DP[-1])
  
main()


Fixed submission:
def main():
  N, W = list(map(int, input().split()))
  Data = []
  for i in range(N):
    Data.append(list(map(int, input().split())))
  
  DP = [0 for i in range(W+1)]
  
  for i in range(N):
    for j in range(W - Data[i][0], -1, -1):
      k = j + Data[i][0]
      DP[k] = max(DP[j] + Data[i][1], DP[k])
  
  print(DP[-1])
  
main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
  N, W = list(map(int, input().split()))
  Data = []
  su = 0
  for i in range(N):
    t = list(map(int, input().split()))
    su += t[1]
    Data.append(t)
  
  DP = [int(10e12) if i != Data[0][1] else Data[0][0] for i in range(su + 1)]
  DP[0] = 0
  
  for i in range(1, N):
    for j in range(su - Data[i][1], -1, -1):
      k = j + Data[i][1]
      DP[k] = min(DP[j] + Data[i][0], DP[k])
      
  for i in range(su, -1, -1):
    if DP[i] <= W:
      print(i)
      break
  
main()


Fixed submission:
def main():
  N, W = list(map(int, input().split()))
  Data = []
  su = 0
  for i in range(N):
    t = list(map(int, input().split()))
    su += t[1]
    Data.append(t)
  
  DP = [int(10e12) if i != Data[0][1] else Data[0][0] for i in range(su + 1)]
  DP[0] = 0
  
  for i in range(1, N):
    for j in range(su - Data[i][1], -1, -1):
      k = j + Data[i][1]
      DP[k] = min(DP[j] + Data[i][0], DP[k])
      
  for i in range(su, -1, -1):
    if DP[i] <= W:
      print(i)
      break
  
main()
Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
a = list(map(int, input().split()))

def mex(L):
  L.sort()
  ans = 0
  for i in L:
    if i <= ans:
      ans += 1
    else:
      break
  return ans

DP = [0] * (K + 1)
M = 100000

for i in range(a[0], K + 1):
  L = []
  for j in range(N):
    if i - a[j] < 0:
      break
    L.append(DP[i - a[j]])
  DP[i] = mex(L)

if DP[-1] == 0:
  print("Second")
else:
  print("First")


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

def mex(L):
  L.sort()
  ans = 0
  for i in L:
    if i <= ans:
      ans += 1
    else:
      break
  return ans

DP = [0] * (K + 1)
M = 100000

for i in range(a[0], K + 1):
  L = []
  for j in range(N):
    if i - a[j] < 0:
      break
    L.append(DP[i - a[j]])
  DP[i] = mex(L)

if DP[-1] == 0:
  print("Second")
else:
  print("First")
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int, input().split()))

M = 10 ** 15
DP = [[0] * N for _ in range(N)]

if N % 2 == 0:
  t = -1
else:
  t = 1
for i in range(N):
  DP[0][i] = a[i] * t
t *= -1

for i in range(1, N):
  for j in range(N - i):
    if t > 0:
      DP[i][j] = max(DP[i - 1][j] + a[i + j], DP[i - 1][j + 1] + a[j])
    else:
      DP[i][j] = min(DP[i - 1][j] - a[i + j], DP[i - 1][j + 1] - a[j])
  t *= -1

print(DP[-1][0])

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

M = 10 ** 15
DP = [[0] * N for _ in range(N)]

if N % 2 == 0:
  t = -1
else:
  t = 1
for i in range(N):
  DP[0][i] = a[i] * t
t *= -1

for i in range(1, N):
  for j in range(N - i):
    if t > 0:
      DP[i][j] = max(DP[i - 1][j] + a[i + j], DP[i - 1][j + 1] + a[j])
    else:
      DP[i][j] = min(DP[i - 1][j] - a[i + j], DP[i - 1][j + 1] - a[j])
  t *= -1

print(DP[-1][0])
Buggy python submission (verdict: Runtime Error):
import numpy as np

N, K = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(N)]
MOD = 10 ** 9 + 7

A = np.array(a, dtype = 'int64')
A = A.T

ans = np.eye(N, dtype = 'int64')
while K:
  if K & 1:
    ans = np.dot(ans, A)
    ans %= MOD
  A = np.dot(A, A)
  A %= MOD
  K >>= 1

print(int(np.sum(abs(ans))) % MOD)

Fixed submission:
import numpy as np

N, K = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(N)]
MOD = 10 ** 9 + 7

A = np.array(a, dtype = 'O')
A = A.T

ans = np.eye(N, dtype = 'O')
while K:
  if K & 1:
    ans = np.dot(ans, A)
    ans %= MOD
  A = np.dot(A, A)
  A %= MOD
  K >>= 1

print(np.sum(abs(ans)) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
def hersCode(L, n):
  ok = len(L) - 1
  ng = 0
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] > n:
      ok = mid
    else:
      ng = mid
  return ok

def hersCode2(L, n):
  ok = 0
  ng = len(L)
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] <= n:
      ok = mid
    else:
      ng = mid
  return ok

N = int(input())

A = list(map(int, input().split()))
A.sort()

D = [pow(2, i) for i in range(31)]
L = [True for i in range(N + 1)]
Ans = 0
A = [-1e11] + A
for i in range(len(A) - 1, 1, -1):
  if L[i]:
    k = D[hersCode(D, A[-1])] - A[-1]
    del A[-1]
    t = hersCode2(A, k)
    cnt = 0
    while A[t - cnt] == k:
      if L[t - cnt]:
        L[t - cnt] = False
        Ans += 1
        break
      else:
        cnt += 1
  else:
    del A[-1]

print(Ans)

Fixed submission:
def hersCode(L, n):
  ok = len(L) - 1
  ng = 0
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] > n:
      ok = mid
    else:
      ng = mid
  return ok

def hersCode2(L, n):
  ok = 0
  ng = len(L)
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] < n:
      ok = mid
    elif L[mid] == n:
      if TF[mid]:
        ok = mid
      else:
        ng = mid
    else:
      ng = mid
  return ok

N = int(input())

A = list(map(int, input().split()))
A.sort()

D = [pow(2, i) for i in range(31)]
TF = [True for i in range(N + 1)]
Ans = 0
A = [-1e11] + A
for i in range(len(A) - 1, 1, -1):
  if TF[i]:
    k = D[hersCode(D, A[-1])] - A[-1]
    del A[-1]
    t = hersCode2(A, k)
    if A[t] == k:
      TF[t] = False
      Ans += 1
  else:
    del A[-1]

print(Ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
cnt = 0
for i in range(357, N+1):
    c = 0
    T = str(i)
    if T.find('3') == -1:
        continue
    else:
        c += T.count('3')
    if T.find('5') == -1:
        continue
    else:
        c += T.count('5')
    if T.find('7') == -1:
        continue
    else:
        c += T.count('7')
    if c == len(T):
        cnt += 1
print(cnt)


Fixed submission:
N=int(input())

L=[3,5,7]
f = 0
cnt = 0
while f == 0:
  for i in range(3):
    x = L[cnt] * 10 + L[i]
    if x > N:
      f = 1
      break
    else:
      L.append(L[cnt] * 10 + L[i])
  cnt += 1

ans = set(["3","5","7"])
cnt = 0
for i in L:
    s = set(str(i))
    if s == ans:
        cnt += 1
print(cnt)
Buggy python submission (verdict: Runtime Error):
import math
def prime(x):
  p = {}
  cnt = 2
  Flag = True
  while Flag:
    last = math.ceil(x ** 0.5) 
    if cnt > last:
      break
    for i in range(cnt, last + 1):
      if x % i == 0:
        x //= i
        p[i] = 1
        cnt = i + 2
        while x % i == 0:
          x //= i
          p[i] += 1
        cnt = i + 1
        break
      if i == last:
        Flag = False
  if x != 1:
    p[x] = 1
  return p

def lcm(x, y):
  return (x * y) // math.gcd(x,y)


N, M = list(map(int, input().split()))
S = list(input())
T = list(input())

L = lcm(N, M)

x = L // N
y = L // M
for i in range(N):
  if (i * x) % y == 0:
    if S[i] != T[(i * x) // y]:
      L = -1
      break

print(L)


Fixed submission:
def gcd(x, y):
  n = min(x, y)
  for i in range(n, 0, -1):
    if x % i == 0 and y % i == 0:
      return i

def lcm(x, y):
  return (x * y) // gcd(x,y)


N, M = list(map(int, input().split()))
S = list(input())
T = list(input())

L = lcm(N, M)

x = L // N
y = L // M
for i in range(N):
  if (i * x) % y == 0:
    if S[i] != T[(i * x) // y]:
      L = -1
      break

print(L)
Buggy python submission (verdict: Runtime Error):
import math

N = int(input())
A = list(map(int, input().split()))

mod = 10**9 + 7

F = 1
for i in range(2, N + 1):
	F *= i

D = [1]
for i in range(2, N + 1):
	D.append(D[-1] + 1 / i)

L = [0] * N
for i in range(N // 2 + N % 2):
  L[i] = F * (D[-1 - i] + D[i] - 1) % mod
  L[-1 - i] = L[i]

Ans = 0
for i in range(N):
  Ans += math.ceil(L[i] * A[i]) % mod
print(Ans % mod)

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

mod = 10**9 + 7

F = 1
for i in range(2, N + 1):
	F = F * i % mod

D = [0]
for i in range(2, N + 1):
	D.append(D[-1] + pow(i, mod - 2, mod))

L = [0] * N
for i in range(N // 2 + N % 2):
  t = round(F * (D[-1 - i] + D[i] + 1)) % mod
  L[i] = t
  L[-1 - i] = t

Ans = 0
for i in range(N):
  Ans += L[i] * A[i] % mod

print(Ans % mod)
Buggy python submission (verdict: Runtime Error):
####################
def pri(n):
  i = 2
  X = {}
  while i * i <= n:
    while n % i == 0:
      n /= i
      if i in X:
        X[i] = X[i] + 1
      else:
        X[i] = 1
    i += 1
  if n > 1:
    X[n] = 1
  return X
####################


N,X = list(map(int, input().split()))

x = list(map(int, input().split()))
x.append(X)

x.sort()

d = []
for i in range(N):
  dif = x[i+1] - x[i]
  if dif not in d:
    d.append(dif)

d.sort()

if len(d) == 1:
  print(d[0])
  exit()

min = d[0]
P = pri(d[0])

for i in range(1,len(d)):
  if d[i] % min != 0:
    t = pri(d[0])
    min = 1
    for j in P:
      if j in t:
        P[j] = min(P[j], t[j])
        min *= j ** P[j]
      else:
        del P[j]

print(min)


Fixed submission:
####################
def pri(n):
  i = 2
  X = {}
  while i * i <= n:
    while n % i == 0:
      n /= i
      if i in X:
        X[i] = X[i] + 1
      else:
        X[i] = 1
    i += 1
  if n > 1:
    X[n] = 1
  return X
####################


N,X = list(map(int, input().split()))

x = list(map(int, input().split()))
x.append(X)

x.sort()

d = []
for i in range(N):
  dif = x[i+1] - x[i]
  if dif not in d:
    d.append(dif)

d.sort()

if len(d) == 1:
  print(d[0])
  exit()

m = d[0]
P = pri(d[0])

for i in range(1,len(d)):
  if d[i] % m != 0:
    t = pri(d[i])
    m = 1
    for j in list(P):
      if j in t:
        P[j] = min(P[j], t[j])
        m *= j ** P[j]
      else:
        del P[j]

print(int(m))
Buggy python submission (verdict: Runtime Error):
import re
S = input()
K = int(input())

d = re.search('[2-9]', S)
if d.start() >= K:
  print("1")
else:
  print(d.group())

Fixed submission:
import re
S = input()
K = int(input())

d = re.search('[2-9]', S)
if d == None or d.start() >= K:
  print("1")
else:
  print(d.group())
Buggy python submission (verdict: Time Limit Exceeded):
N, M, Q = list(map(int, input().split()))

C = [[0] * (N+1) for i in range(N+1)]
for i in range(M):
  L, R = list(map(int, input().split()))
  for j in range(1, L+1):
    for k in range(R, N+1):
      C[j][k] += 1

for i in range(Q):
  p, q = list(map(int, input().split()))
  print(C[p][q])

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

C = [[0] * (N+1) for i in range(N+1)]
for i in range(M):
  L, R = list(map(int, input().split()))
  C[L][R] += 1

A = [[0] * (N+1) for i in range(N)]
for i in range(1,N+1):
  A[0][i] = C[i][i]
for i in range(1,N):
  A[1][i] = A[0][i] + A[0][i+1] + C[i][i+1]
for i in range(2,N):
  for j in range(1,N+1-i):
    A[i][j] = A[i-1][j] + A[i-1][j+1] - A[i-2][j+1] + C[j][i+j]
    
for i in range(Q):
  p, q = list(map(int, input().split()))
  print(A[q-p][p])

Buggy python submission (verdict: Time Limit Exceeded):
N, M, Q = list(map(int, input().split()))
LR = []
pq = []
for i in range(M):
  LR.append(list(map(int, input().split())))
for i in range(Q):
  pq.append(list(map(int, input().split())))

C = [[0] * (N+1) for i in range(N+1)]
for i in range(M):
  for j in range(1, LR[i][0]+1):
    for k in range(LR[i][1], N+1):
      C[j][k] += 1
      
for i in range(Q):
  print(C[pq[i][0]][pq[i][1]])

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

C = [[0] * (N+1) for i in range(N+1)]
for i in range(M):
  L, R = list(map(int, input().split()))
  C[L][R] += 1

A = [[0] * (N+1) for i in range(N)]
for i in range(1,N+1):
  A[0][i] = C[i][i]
for i in range(1,N):
  A[1][i] = A[0][i] + A[0][i+1] + C[i][i+1]
for i in range(2,N):
  for j in range(1,N+1-i):
    A[i][j] = A[i-1][j] + A[i-1][j+1] - A[i-2][j+1] + C[j][i+j]
    
for i in range(Q):
  p, q = list(map(int, input().split()))
  print(A[q-p][p])
Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
D = []
L = [0] * N
Ans = 0
for i in range(M):
  D.append(list(map(int, input().split())))
D.sort(key = lambda x: x[1])

for i in D:
  if 1 not in L[i[0]:i[1]]:
    L[i[1]-1] = 1
    Ans += 1
print(Ans)

Fixed submission:
N, M = list(map(int, input().split()))
D = []
L = [0] * N
for i in range(M):
  D.append(list(map(int, input().split())))
D.sort(key = lambda x: x[1])

Ans = 0
Re = 0
for i in D:
  if Re < i[0]:
    Re = i[1]-1
    Ans += 1
print(Ans)
Buggy python submission (verdict: Time Limit Exceeded):
def Yes():
  print("Yes")
def No():
  print("No")

def gcd(x, y):
  n = min(x, y)
  for i in range(n, 0, -1):
    if x % i == 0 and y % i == 0:
      return i

def lcm(x, y):
  return (x * y) // gcd(x,y)

def main():
  T = int(input())
  AD = [list(map(int, input().split())) for i in range(T)]

  for i in AD:
    A = i[0]
    B = i[1]
    C = i[2]
    D = i[3]
    if A < B:
      No()
      continue
    if B > D:
      No()
      continue
    add = D - B
    d = gcd(B, D)
    
    C += 1
    t = C % d
    k = A % d
    if k == t:
      LD = C
    elif k > t:
      LD = C + k - t
    else:
      LD = C + d - t + k
    if LD < B:
      No()
    else:
      Yes()

main()

Fixed submission:
def Yes():
  print("Yes")
def No():
  print("No")

def gcd(x, y):
  b = max(x, y)
  s = min(x, y)
  r = b % s
  while r != 0:
    b = s
    s = r
    r = b % s
  return s

def lcm(x, y):
  return (x * y) // gcd(x,y)

def main():
  T = int(input())
  AD = [list(map(int, input().split())) for i in range(T)]

  for i in AD:
    A = i[0]
    B = i[1]
    C = i[2]
    D = i[3]
    if A < B:
      No()
      continue
    if B > D:
      No()
      continue
    add = D - B
    d = gcd(B, D)
    
    C += 1
    t = C % d
    k = A % d
    if k == t:
      LD = C
    elif k > t:
      LD = C + k - t
    else:
      LD = C + d - t + k
    if LD < B:
      No()
    else:
      Yes()

main()
Buggy python submission (verdict: Runtime Error):
def su(c):
  if c == 1:
    return 1
  else:
    return c + su(c - 1)

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

c = b - a

east = su(c)

print(east - b)

Fixed submission:
a, b = list(map(int, input().split()))

c = b - a

east = (1 + c) * c // 2

print(east - b)
Buggy python submission (verdict: Runtime Error):
N = int(input())
P = [int(input()) for i in range(N)]

T = [1] * N
L = []
for i in P:
  for j in L:
    if T[j] + j == i:
      T[j] += 1
      break
  else:
    L.append(i)

print(N - max(T))

Fixed submission:
N = int(input())
P = [int(input()) for i in range(N)]

T = [0] * (N + 1)
for i in P:
  if T[i - 1] == 0:
    T[i] = -1
  elif T[i - 1] < 0:
    T[i - 1] -= 1
    T[i] = i - 1
  else:
    T[T[i - 1]] -= 1
    T[i] = T[i - 1]

print(N + min(T))
Buggy python submission (verdict: Runtime Error):
def Root(x):
  if L[x] == x:
    return x
  else:
    return Root(L[x])

N, M = list(map(int, input().split()))
p = list(map(int, input().split()))
L = [i for i in range(N + 1)]
for i in range(M):
  t = list(map(int, input().split()))
  L[Root(min(t))] = L[Root(max(t))]

Ans = 0
for i in range(N):
  if Root(i + 1) == Root(p[i]):
    Ans += 1
print(Ans)
  


Fixed submission:
def Root(x, cnt):
  cnt += 1
  if L[x] == x:
    return x, cnt
  else:
    return Root(L[x], cnt)

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

Data = []
for i in range(M):
  Data.append(list(map(int, input().split())))

L = [i for i in range(N + 1)]
for i in Data:
  a = Root(i[0], 0)
  b = Root(i[1], 0)
  if a[1] > b[1]:
    L[b[0]] = L[a[0]]
  else:
    L[a[0]] = L[b[0]]
    
Ans = 0
for i in range(N):
  if Root(i + 1, 0)[0] == Root(p[i], 0)[0]:
    Ans += 1
print(Ans)
Buggy python submission (verdict: Runtime Error):
S = input()

if "a" not in S:
  print("No")
  exit()

if "b" not in S:
  print("No")
  exit()

if "c" not in S:
  print("No")
  exit()

 print("Yes")

Fixed submission:
S = input()

if "a" not in S:
  print("No")
  exit()

if "b" not in S:
  print("No")
  exit()

if "c" not in S:
  print("No")
  exit()

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

L = []

for i in range(A, B + 1):
  if i < A + K or i > B - K:
    L.append(i)

for i in L:
  print(i)



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

L = []

for i in range(A, min(A + K, B + 1)):
  L.append(i)

for i in range(max(B - K + 1, A + K), B + 1):
  L.append(i)

for i in L:
  print(i)
Buggy python submission (verdict: Runtime Error):
N = int(ipnut())

print(3 // N)

Fixed submission:
N = int(input())

print(N // 3)
Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = list(map(int, input().split()))

A = []
for i in range(H):
  A.append(list(map(int, input().split())))
  
Q = int(input())

LR = []

for i in range(Q):
  LR.append(list(map(int, input().split())))

List = [[0, 0] for i in range(H * W)]
for i in range(H):
  for j in range(W):
    List[A[i][j] - 1] = [i, j]
    
Data = [0 for i in range(H * W)]
for i in range(D):
  for j in range(i, H * W - D, D):
    a = List[j]
    b = List[j + D]
    Data[j] = abs(a[0] - b[0]) + abs(a[1] - b[1])
    
Ans = [[0 for i in range(H * W)] for j in range(H * W)]
for i in range(H * W - D):
  t = Data[i]
  for j in range(i + D, H * W, D):
    Ans[i][j] = t
    t += Data[j]
    
for i in range(Q):
  print(Ans[LR[i][0] - 1][LR[i][1] - 1])
    

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

A = []
for i in range(H):
  A.append(list(map(int, input().split())))
  
Q = int(input())

LR = []

for i in range(Q):
  LR.append(list(map(int, input().split())))

List = [[0, 0] for i in range(H * W)]
for i in range(H):
  for j in range(W):
    List[A[i][j] - 1] = [i, j]
    
Data = [0 for i in range(H * W)]
for i in range(D):
  for j in range(D + i, H * W, D):
    a = List[j - D]
    b = List[j]
    Data[j] = abs(a[0] - b[0]) + abs(a[1] - b[1]) + Data[j - D]

for i in range(Q):
  print(Data[LR[i][1] - 1] - Data[LR[i][0] - 1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int, input().split()))

L = []

def ans(tf):
  if tf:
    print("Yes")
  else:
    print("No")

for x in a:
  for i in range(len(L)):
    if L[i][0] == x:
      L[i][1] += 1
      break
  else:
    L.append([x, 1])
    if len(L) >= 3:
      ans(False)

if len(L) == 1:
  x = L[0][0]
  if x == N - 1 or x <= N // 2:
    ans(True)
  else:
    ans(False)
else:
  x, xn = L[0]
  y, yn = L[1]
  if abs(x - y) != 1:
    ans(False)
    exit()
  if x < y:
    x, y = y, x
    xn, yn = yn, xn
  if yn >= x:
    ans(False)
    exit()
  n = x - yn
  if n <= xn // 2:
    ans(True)
  else:
    ans(False)

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

L = []

def ans(tf):
  if tf:
    print("Yes")
  else:
    print("No")
  exit()

for x in a:
  for i in range(len(L)):
    if L[i][0] == x:
      L[i][1] += 1
      break
  else:
    L.append([x, 1])
    if len(L) >= 3:
      ans(False)

if len(L) == 1:
  x = L[0][0]
  if x == N - 1 or x <= N // 2:
    ans(True)
  else:
    ans(False)
else:
  x, xn = L[0]
  y, yn = L[1]
  if abs(x - y) != 1:
    ans(False)
    exit()
  if x < y:
    x, y = y, x
    xn, yn = yn, xn
  if yn >= x:
    ans(False)
    exit()
  n = x - yn
  if n <= xn // 2:
    ans(True)
  else:
    ans(False)