Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

#!python3

import sys

from bisect import bisect, insort_left

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    S1 = [[] for i in range(26)]
    for i, c1 in enumerate(S):
        ci = ord(c1) - c0
        S1[ci].append(i)

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            c1 = ord(S[i]) - c0
            s1 = S1[c1]
            s1.remove(i)
            S[i] = j
            c1 = ord(j) - c0
            insort_left(S1[c1], i)
        elif cmd == "2":
            j = int(j) - 1
            num = 0

            for s1 in S1:
                ls = len(s1)
                k = bisect(s1, i-1, 0, ls)

                if k == ls:
                    continue
                if i <= s1[k] <= j:
                    num += 1

            ans.append(num)

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

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys

from bisect import bisect, insort_left

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    S1 = [[] for i in range(26)]
    for i, c1 in enumerate(S):
        ci = ord(c1) - c0
        S1[ci].append(i)

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            c1 = ord(S[i]) - c0
            s1 = S1[c1]
            s1.pop(bisect(s1, i)-1)
            S[i] = j
            c1 = ord(j) - c0
            insort_left(S1[c1], i)
        elif cmd == "2":
            j = int(j) - 1
            num = 0

            for s1 in S1:
                ls = len(s1)
                k = bisect(s1, i-1, 0, ls)

                if k == ls:
                    continue
                if i <= s1[k] <= j:
                    num += 1

            ans.append(num)

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

if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

import math

def Show(n):
	s = str(n)
	m = len(s)
	for i in range(6 - m):
		print("0",end = "")
	print("{0}".format(n),end = "")

s = input().split()
n = int(s[0])
m = int(s[1])
p = []
y = []
for i in range(m):
	s = input().split()
	p.append(int(s[0]))
	y.append(int(s[1]))
x = [[] for i in range(n)]
for i in range(m):
	x[p[i] - 1].append(y[i])
for i in range(n):
	x[i].sort()
for i in range(m):
	Show(p[i])
	Show(x[p[i] - 1].index(y[i]) + 1)
	print()

### FIXED CODE ###

import math

def Show(n):
	s = str(n)
	m = len(s)
	for i in range(6 - m):
		print("0",end = "")
	print("{0}".format(n),end = "")

class city:
	year = 0
	p = 0
	number = 0
	def __init__(self,y,pi,n):
		self.year = y
		self.p = pi
		self.number = n

s = input().split()
n = int(s[0])
m = int(s[1])
cities = []
for i in range(m):
	s = input().split()
	p = int(s[0])
	y = int(s[1])
	cities.append(city(y,p,i))
x = [[] for i in range(n)]
for i in range(m):
	x[cities[i].p - 1].append(cities[i])
for i in range(n):
	x[i].sort(key = lambda x : x.year)
ans = []
for i in range(m):
	ans.append([0,0])
for i in range(n):
	for j in range(len(x[i])):
		ans[x[i][j].number][0] = x[i][j].p
		ans[x[i][j].number][1] = j + 1
for i in range(m):
	Show(ans[i][0])
	Show(ans[i][1])
	print()
### BUGGY CODE ###

def check(g,h,w,s):
    if (g[0]<0 or g[0]>=h) or (g[1]<0 or g[1]>=w):
        return False
    if s[g[0]][g[1]]==-1:
        return True
    else:
        return False



h,w=map(int,input().split())
c=[int(x)-1 for x in input().split()]
d=[int(x)-1 for x in input().split()]
s=[]
for j in range(h):
    l=[-1 if x=="." else -2 for x in list(input())]
    s.append(l)
s[c[0]][c[1]]=0
u=[c]
i=0
t=0
while t==0:
    for j in u:
        if j==d:
            t=1
            break
        for k in [[j[0]-1,j[1]],[j[0]+1,j[1]],[j[0],j[1]-1],[j[0],j[1]+1]]:
            if check(k,h,w,s):
                s[k[0]][k[1]]=i
                u.append(k)
    i+=1
    v=[]
    for j in u:
        if j==d:
            t=1
            break
        for k1 in range(-2,3):
            for k2 in range(-2,3):
                k=[j[0]+k1,j[1]+k2]
                if check(k,h,w,s):
                    s[k[0]][k[1]]=i
                    v.append(k)
    if v==[]:
        t=1
    u=v
print(s[d[0]][d[1]])

### FIXED CODE ###

def check(g,h,w,s):
    if (g[0]<0 or g[0]>=h) or (g[1]<0 or g[1]>=w):
        return False
    if s[g[0]][g[1]]==-1:
        return True
    else:
        return False



h,w=map(int,input().split())
c=[int(x)-1 for x in input().split()]
d=[int(x)-1 for x in input().split()]
s=[]
for j in range(h):
    l=[-1 if x=="." else -2 for x in list(input())]
    s.append(l)
s[c[0]][c[1]]=0
u=[c]
i=0
t=0
while t==0:
    for j in u:
        if j==d:
            t=1
            break
        for k in [[j[0]-1,j[1]],[j[0]+1,j[1]],[j[0],j[1]-1],[j[0],j[1]+1]]:
            if check(k,h,w,s):
                s[k[0]][k[1]]=i
                u.append(k)
    i+=1
    v=[]
    for j in u:
        if j==d:
            t=1
            break
        for k1 in range(-2,3):
            for k2 in range(-2,3):
                k=[j[0]+k1,j[1]+k2]
                if check(k,h,w,s):
                    s[k[0]][k[1]]=i
                    v.append(k)
    if v==[]:
        t=1
    u=v
print(s[d[0]][d[1]])
### BUGGY CODE ###

mod = 10**9+7
n,a,b = [int(i) for i in input().split()]
k = min(n,2*(10**5))
def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return (K * x - 1) % mod
def modinv(a, mod):
    return pow(a, mod-2, mod)
def combination_list(n, mod):
    lst = [1]
    for i in range(1, k+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst
ans = pow_k(2,n)
cmb = combination_list(n,mod)
ans %= mod
ans -= cmb[a]
if ans < 0:
    ans += mod
ans -= cmb[b]
if ans <0:
    ans += mod
print(ans)

### FIXED CODE ###

mod = 10**9+7
n,a,b = [int(i) for i in input().split()]
k = min(n,2*(10**5))
import sys
sys.setrecursionlimit(100000000)
def pow_k(a,n,mod):
    if n == 0:
        return 1
    if n % 2 ==0:
        return pow_k(a*a % mod,n//2,mod)
    else:
        return a * pow_k(a,n-1,mod) % mod
def modinv(a, mod):
    return pow(a, mod-2, mod)
def combination_list(n, mod):
    lst = [1]
    for i in range(1, k+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst
ans = pow_k(2,n,mod)
cmb = combination_list(n,mod)
ans -=1
ans -= cmb[a]
if ans < 0:
    ans += mod
ans -= cmb[b]
if ans <0:
    ans += mod
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
a = 0
b = 0
for i in range(n - k + 1):
    b = 0
    for j in range(i, i + k):
        b += p[j]
    if b > a:
        a = b
print((a + k) / 2)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
a = 0
b = 0
for i in range(k):
    a += p[i]
    b += p[i]
for i in range(n - k):
    a += p[i + k]
    a -= p[i]
    if b < a:
        b = a
    
print((b + k) / 2)
### BUGGY CODE ###

from math import factorial
def ncm(n,m):
    return factorial(n)//factorial(m)//factorial(n-m)
from itertools import permutations
ans=0
n=int(input())
for num3 in range(1,11):
    for num5 in range(1,11):
        for num7 in range(1,11):
            if int("3"*num3+"5"*num5+"7"*num7)>n:
                continue
            elif int("7"*num7+"5"*num5+"3"*num3)<n:
                ans+=ncm(num7+num5+num3,num7)*ncm(num5+num3,num5)
            else:
                tmp=set()
                for i in permutations(list("7"*num7+"5"*num5+"3"*num3)):
                    tmp.add(int("".join(i)))
                for i in tmp:
                    if i<=n:
                        ans+=1
print(ans)

### FIXED CODE ###

from itertools import product
ans=0
n=int(input())
for i in range(3,11):
    for m in product(["3","5","7"],repeat=i):
        if "3"not in m or "5"not in m or "7"not in m:
            continue
        if int("".join(m))<=n:
            ans+=1
        else:
            break
print(ans)
### BUGGY CODE ###

import sys
import itertools
sys.setrecursionlimit(10**6)
def MAP(): return [int(s) for s in input().split()]

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline

N = int(input())
S = input().rstrip()
s = [int(x) for x in S]

remove= list(itertools.combinations(range(len(S)), N-3))
#print('to remove: ', remove)

ans = []
for i in range(len(remove)):
	ans.append([num for idx,num in enumerate(s) if not idx in remove[i]])

#print('answer: ',ans)
answer = len(set(map(tuple, ans)))
print(answer)

### FIXED CODE ###

#encoding: utf-8
import sys

input = sys.stdin.readline
def MAP(): return [int(s) for s in input().split()]

N = int(input())
S = input()

# 入力の網羅は 30,000C3 の組み合わせとなり全探索は不可能
# 出力は000〜999までの10**3であり、3*10**4とのかけあわせで
# O(10**7)であれば、制限時間内に計算が可能（出力全探索による貪欲法）

# PIN[0]に該当する文字が入力Sから見つかった場合、
# そのSを利用するのが最も効果的であるので貪欲法が利用できる
# (最初に見つかったものを使うとのちのちの制約に引っかかる、というような場合はDPなどを考慮)

# s in S に対し、PIN[0]に該当するsがあれば PIN[1]に該当するsを探索、、という繰り返しで3桁分見つかればans+=1

ans = 0
for i in range(1000):
	pin = str(i).zfill(3)
	cnt = 0 # 該当するsのカウント
	idx = 0 # 探索するPINのインデックス
	for s in S:
		if s==pin[idx]:
			cnt += 1 # カウントアップ
			idx += 1 # インデックスをPINの次の文字へ送る
			if idx == 3:
				break
	if cnt == 3:
		#print(pin)
		ans += 1
				
print(ans)
### BUGGY CODE ###

import numpy as np
from numba import jit
@jit(cache=True)

def solve(n,k,A):
    l,r=0,0
    for ki in range(k):
        B=np.zeros(n+1,dtype=int)
        for i,j in enumerate(A):
            l=max(0,i-j)
            r=min(n,i+j+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        if A[A==n].size==n:
            break
    return A

n,k=map(int,input().split())
A=list(map(int,input().split()))
x=solve(n,k,A)
print(*x)
    


### FIXED CODE ###

import numpy as np
from numba import jit
@jit(cache = True)
def solve(n,k,A):
    l,r=0,0
    for i in range(k):
        B=np.zeros(n+1,dtype=np.int64)
        for x,y in enumerate(list(A)):
            l=max(0,x-y)
            r=min(n,x+y+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        if A[A==n].size==n:
            break
    return A
n,k=map(int,input().split())
a=list(map(int,input().split()))
A=np.array(a)
X=solve(n,k,A)
print(*X,sep=' ')
### BUGGY CODE ###

import math

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
pgcd = True
sgcd = a[n-1]

for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
    if sgcd==1:
        break
if sgcd!=1:
    print('not coprime')
else:
    l = [a[0]]
    for i in range(1,n):
        for aa in l:
            if math.gcd(aa, a[i]) != 1:
                print('setwise coprime')
                break
        else:
            l.append(a[i])
            continue
        break
    else:
        print('pairwise coprime')

### FIXED CODE ###

import math

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
NUM = 1_000_005
aa = [0]*NUM
pgcd = True
sgcd = a[n-1]
aa[a[n-1]]+=1
for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
    aa[a[i]]+=1

for i in range(2,NUM):
    tmp = sum(aa[i::i])
    if tmp >= 2:
        pgcd = False
        break
        
if sgcd!=1:
    print('not coprime')
elif pgcd:
    print('pairwise coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

n, k = map(int,input().split())
arr = list(map(int, input().split()))
big = 0
kitai = 0
for i in range(n-k+1):
    kitai = 0
    for j in range(i,i+k):
        kitai = kitai + (arr[j]+1)/2
    if big < kitai:
        big = kitai
print(big)


### FIXED CODE ###

n, k = map(int,input().split())
arr = list(map(int, input().split()))
kitai = 0
biglist = []
if k ==1:
    kitai = (max(arr)+1)/2
    print(kitai)
else:
    for i in range(n-k+1):
        if i == 0:
            big = 0
            for j in range(i+k):
                big = big + arr[j]
        else:
            big = biglist[i-1] - arr[i-1] + arr[i+k-1]
        biglist.append(big)
    max_value = max(biglist)
    max_index = biglist.index(max_value)
    for j in range(max_index,max_index+k):
        kitai = kitai + (arr[j]+1)/2
    print(kitai)
### BUGGY CODE ###

N = int(input())
N_list = [int(i) for i in input().split()]

counter = 0
for i in range(len(N_list)):
    if N_list[i] == min(N_list[:i+1]):
        counter += 1
print(counter)


### FIXED CODE ###

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

counter = 0
min = N_list[0]
for i in range(N):
    if N_list[i] <= min:
        min = N_list[i]
        counter += 1
print(counter)
print()
### BUGGY CODE ###

def main():
    N = int(input())
    X = input()

    memo = [-1] * 21

    def f(x):
        ret = 0
        while x > 0:
            x = x % bin(x)[2:].count('1')
            ret += 1
        return ret

    for x in range(21):
        memo[x] = f(x)

    ans = []
    for j in range(N):
        t = X[:j] + ('0' if X[j] == '1' else '1') + X[j + 1:]
        t = int(t, 2)

        add_v = 0
        while t > 20 or memo[t] == -1:
            t = t % bin(t)[2:].count('1')
            add_v += 1
        ans.append(memo[t] + add_v)

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


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok


### FIXED CODE ###

def main():
    N = int(input())
    *X, = map(int, input())

    memo = [-1] * 21

    def f(x):
        ret = 0
        while x > 0:
            x = x % bin(x)[2:].count('1')
            ret += 1
        return ret

    for x in range(21):
        memo[x] = f(x)

    cnt = X.count(1)

    if cnt == 1:
        ans = []
        i = 0
        for d in reversed(X):
            if d:
                ans.append(0)
                continue
            if i == 0 or X[-1]:
                ans.append(2)
            else:
                ans.append(1)
            i += 1
            
        ans.reverse()

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

    pow2_0_1 = [1]
    pow2_1_0 = [1]

    t_0_1 = 1
    t_1_0 = 1
    for i in range(N):
        t_0_1 = t_0_1 * 2 % (cnt + 1)
        pow2_0_1.append(t_0_1)

        t_1_0 = t_1_0 * 2 % (cnt - 1)
        pow2_1_0.append(t_1_0)

    chg_0_1 = 0
    chg_1_0 = 0
    i = 0
    for d in reversed(X):
        if d:
            chg_0_1 = (chg_0_1 + pow2_0_1[i]) % (cnt + 1)
            chg_1_0 = (chg_1_0 + pow2_1_0[i]) % (cnt - 1)
        i += 1

    ans = []
    i = 0
    for d in reversed(X):
        if d:
            t = (chg_1_0 - pow2_1_0[i]) % (cnt - 1)
        else:
            t = (chg_0_1 + pow2_0_1[i]) % (cnt + 1)
        i += 1

        add_v = 1
        while t > 20 or memo[t] == -1:
            t = t % bin(t)[2:].count('1')
            add_v += 1
        ans.append(memo[t] + add_v)

    ans.reverse()

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


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
#
# sys.setrecursionlimit(10 ** 7)
#
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok
### BUGGY CODE ###

N = int(input())
L_list = sorted([int(x) for x in input().split()])
cnt = 0
for i in range(N-2):
    if (L_list[i] == 1): continue
    for j in range(i+1, N-1):
        if (L_list[j] == 1): continue
        for k in range(j+1, N):
            a, b, c = L_list[i], L_list[j], L_list[k]
            if (c < a+b):
                cnt += 1
            else:
                break
print(cnt)


### FIXED CODE ###

import bisect
N = int(input())
L = sorted([int(x) for x in input().split()])
cnt = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        cnt +=  bisect.bisect_left(L, L[i]+L[j]) - (j+1)
print(cnt)
### BUGGY CODE ###


import numpy as np
from numba import jit

n = int(input())
sa = np.cumsum(np.array([0]+list(map(int,input().split()))))

@jit
def solve():
    ans = 10**15
    for i in range(1,n-2):
        left = sa[i+1]
        right = sa[-1] - sa[i+1]
        lsplit = min(sa[:i+1].searchsorted(left//2, side="right") - 2, i-1)
        rsplit = min(sa[i+1:].searchsorted(right//2 + left, side="right") + i-1, n-2)
        lleft = [(sa[lsplit + 1],sa[i+1] - sa[lsplit + 1]),(sa[lsplit + 2],sa[i+1] - sa[lsplit + 2])]
        rright = [(sa[rsplit+1] - sa[i+1],sa[-1] - sa[rsplit+1]),(sa[rsplit+2] - sa[i+1],sa[-1] - sa[rsplit+2])]
        for s,t in [(0,0),(0,1),(1,0),(1,1)]:
            l = lleft[s]
            r = rright[t]
            m = min(l+r)
            M = max(l+r)
            ans = min(ans,M-m)
    return ans

print(solve())

### FIXED CODE ###

# arc 100 D

def ruiseki(n,array):
    res = [0]*(n)
    for i in range(n):
        res[i] = res[i-1] + array[i]
    return res

n = int(input())
A = list(map(int,input().split()))
sa = ruiseki(n,A)

ans = 10**15
left_c = 0
right_c = 2
for center in range(1,n-1):
    while left_c+1 < center:
        if abs(sa[center]-2*sa[left_c]) > abs(sa[center]-2*sa[left_c+1]):
            left_c+=1
        else:
            break

    right_c = max(right_c, center+1)
    while right_c+1 < n-1:
        if abs(sa[-1] + sa[center] - 2*sa[right_c]) > abs(sa[-1] + sa[center] - 2*sa[right_c+1]):
            right_c+=1
        else:
            break
    
    x = max(sa[left_c], sa[center]-sa[left_c], sa[right_c]-sa[center], sa[-1]-sa[right_c])
    y = min(sa[left_c], sa[center]-sa[left_c], sa[right_c]-sa[center], sa[-1]-sa[right_c])
    ans = min(ans, x-y)

print(ans)
### BUGGY CODE ###

d,g=[int(c) for c in input().split(" ")]

p=[0]*d
c=[0]*d

for i in range(d):
    pp,cc=[int(c) for c in input().split(" ")]
    p[i]=pp
    c[i]=cc

ans=1001

def calc(g,n):
    if g<=0:
        return 0
    elif n==d:
        return 100001
    cnt=100001
    for i in range(p[n]):
        cnt=min(cnt,i+calc(g-100*i*(n+1),n+1))
    cnt=min(cnt,p[n]+calc(g-p[n]*(n+1)*100-c[n],n+1))

    return cnt

print(calc(g,0))


### FIXED CODE ###

import numpy as np

d,g=[int(c) for c in input().split(" ")]

p=[0]*(d+1)
c=[0]*(d+1)

for i in range(1,d+1):
    pp,cc=[int(c) for c in input().split(" ")]
    p[i]=pp
    c[i]=cc

def rec(i,g,flag):
    if i==d+1:
        cnt=0
        if g<=0:
            return 0

        for j in range(d,0,-1):
            bit=flag%2
            flag//=2

            if bit==0:
                ptsperprob=j*100
                psolved=min(p[j]-1,int(np.ceil(g/ptsperprob)))

                g-=psolved*ptsperprob
                cnt+=psolved

                if g<=0:
                    return cnt
        
        return 10000

    return min(p[i]+rec(i+1,g-c[i]-p[i]*100*i,2*flag+1),rec(i+1,g,2*flag))

print(rec(1,g,0))
### BUGGY CODE ###

n = int(input())
d = {}
key = []
s = 0
for i in range(n):
    a, b = map(int, input().split())
    if b not in key:
        key.append(b)
        d.update({b:a})
    else:
        d[b] += a
    s += a
key.sort(reverse = True)
ans = True
for k in key:
    if k < s:
        ans = False
        break
    s -= d[k]
if ans:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = int(input())
d = {}
s = 0
for i in range(n):
    a, b = map(int, input().split())
    if b not in d:
        d.update({b:a})
    else:
        d[b] += a
    s += a
key = list(d.keys())
key.sort(reverse = True)
ans = True
for k in key:
    if k < s:
        ans = False
        break
    s -= d[k]
if ans:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
s = list(input())

ans = float("inf")
for i in range(n):
    cnt = 0
    for j in range(n):
        if j < i and s[j] == "W":
            cnt += 1
        if i < j and s[j] == "E":
            cnt += 1
    ans = min(ans,cnt)

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

n = int(input())
s = list(input())
w = [0] * n
e = [0] * n

cntw = 0
cnte = 0
for i in range(n):
    if s[i] == "W":
        cntw += 1
        w[i] = cntw
    else:
        w[i] = cntw
    if s[i] == "E":
        cnte += 1
        e[i] = cnte
    else:
        e[i] = cnte

ans = float("inf")

for i in range(n):
    num = 0
    if i-1 >= 0:
        num += w[i-1]
    num += e[-1] - e[i]
    ans = min(num,ans)

print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
p = list(map(int, input().split()))
g = [[] for _ in range(0,n+1)]
visit = [None] * (n+1)
ans = 0
for _ in range(0,m):
    x,y = map(int, input().split())
    g[x].append(y)
    g[y].append(x)
for i in range(1,n+1):
    if visit[i] is not None:
        continue
    stack = [i]
    part = [i]
    visit[i] = 0
    while len(stack) > 0:
        q = stack.pop()
        for qq in g[q]:
            if visit[qq] is None:
                visit[qq] = 0
                part.append(qq)
                stack.append(qq)
    part2 = []
    for i in part:
        part2.append(p[i-1])
    for i in part:
        if i in part2:
            ans += 1
print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
p = list(map(int, input().split()))
g = [[] for _ in range(0,n+1)]
visit = [None] * (n+1)
ans = 0
for _ in range(0,m):
    x,y = map(int, input().split())
    g[x].append(y)
    g[y].append(x)
for i in range(1,n+1):
    if visit[i] is not None:
        continue
    stack = [i]
    part = [i]
    visit[i] = 0
    while len(stack) > 0:
        q = stack.pop()
        for qq in g[q]:
            if visit[qq] is None:
                visit[qq] = 0
                part.append(qq)
                stack.append(qq)
    part2 = []
    for i in part:
        part2.append(p[i-1])
    ans += len(list(set(part) & set(part2)))
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
score = list(map(int, input().split()))
t = input()
hand = 'rsp'

d = {'': 0}
for i in range(n):
    h = hand.index(t[i])
    dd = {}
    for s, x in d.items():
        for j in range(3):
            if i < k or s[0] != hand[j]:
                point = 0
                if (j - h) % 3 == 2:
                    point = score[j]
                if k == 1:
                    news = hand[j]
                else:
                    news = s[-k+1:] + hand[j]
                if news in dd:
                    dd[news] = max(dd[news], x + point)
                else:
                    dd[news] = x + point
    d = dd
print(max(d.values()))

### FIXED CODE ###

n, k = map(int, input().split())
score = list(map(int, input().split()))
t_str = input()
hand = 'rsp'
t = []
for x in t_str:
    t.append(hand.index(x))

ans = 0
for r in range(k):
    d = [0] * 3
    for h in t[r::k]:
        dd = [0] * 3
        for i in range(3):
            for j in range(3):
                if i != j:
                    point = 0
                    if (j - h) % 3 == 2:
                        point = score[j]
                    dd[j] = max(dd[j], d[i] + point)
        d = dd
    ans += max(d)
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())

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

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

for i in range(n):
	b[i+1] = b[i]+a[i]


ans = 0
for i in range(n):
	for j in range(1,n-i+1):
		if (b[i+j] - b[i]) % m == 0:
			ans += 1

print(ans)

### FIXED CODE ###

n,m = map(int,input().split())

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

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

for i in range(n):
	b[i+1] = (b[i]+a[i])%m

c = {}
for i in b:
	if i in c:
		c[i] += 1
	else:
		c[i] = 1

ans = 0

for i in c:
	ans += (c[i]*(c[i]-1)//2)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(input())
p = list(map(int, input().split()))
count = 0
for i in range(n):
    if p[i] <= min(p[:i+1]):
        count += 1
print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
p = list(map(int, input().split()))
count = 0
tmp_min = n
for pi in p:
    if pi < tmp_min:
        tmp_min = pi
    if pi <= tmp_min:
        count += 1
print(count)