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

N = int(input())
S = input()
ans = 0
l, r = 0, 1

while l<N:
    s1 = S[l]
    v = 0
    while r<N:
        s2 = S[r]
        if s1!=s2:
            r+=1
            continue
        v = 1
        for i in range(1, r-l):
            if r+i>=N or l+i>=r:break
            if S[l+i]!=S[r+i]:continue
            v+=1
        ans = max(ans, v)
        r+=1
    l+=1
    r=l+1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
dp = [[0]*(N+1) for _ in range(N+1)]

for l in range(N)[::-1]:
    for r in range(l+1, N)[::-1]:
        dp[l][r] = dp[l+1][r+1]+1 if S[l]==S[r] else 0

ans = 0 
for l in range(N)[::-1]:
    for r in range(l+1, N)[::-1]:
        ans = max(ans, min(r-l, dp[l][r]))
print(ans)
### BUGGY CODE ###

N,W = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(N)]
DP = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
  for j in range(1,W+1):
    DP[i][j] = max(DP[i][j],DP[i-1][j])
    if j-wv[i-1][0] >= 0:
      DP[i][j] = max(DP[i][j],DP[i-1][j-wv[i-1][0]]+wv[i-1][1])
print(DP[-1][-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for i in range(N)]
DP = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
  for j in range(1,W+1):
    DP[i][j] = max(DP[i][j],DP[i-1][j])
    if j-wv[i-1][0] >= 0:
      DP[i][j] = max(DP[i][j],DP[i-1][j-wv[i-1][0]]+wv[i-1][1])
print(DP[-1][-1])
### BUGGY CODE ###

def Q3(N, M, *arg):
    import numpy as np
    route = np.reshape(np.array(*arg), (M, 2))
    for x in route:
        if x[0] == 1:
            for y in route:
                if x[1] == y[0] and y[1] == N:
                    return 'POSSIBLE'
    return 'IMPOSSIBLE'

N, M = map(int, input().split())
l = [list(map(lambda x: int(x), input().split())) for i in range(M)]
l = [flatten for inner in l for flatten in inner]
print(Q3(N,M,l))

### FIXED CODE ###

def Q3(N, M, *arg):
    import numpy as np
    route = np.reshape(np.array(*arg), (M, 2))
    string = 'IMPOSSIBLE'
    p = [False] * N
    q = [False] * N
    for x in route:
        if x[0] == 1:
            p[x[1]] = True
        elif x[1] == N:
            q[x[0]] = True
    for i in range(N):
        if p[i] and q[i]:
            string = 'POSSIBLE'
            break
    return string

N, M = map(int, input().split())
l = [list(map(lambda x: int(x), input().split())) for i in range(M)]
l = [flatten for inner in l for flatten in inner]
print(Q3(N,M,l))
### BUGGY CODE ###

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

A = [[0] * 2 for k in range(M)]

for i in range(M):
    A[i][0], A[i][1] = input().split()

AC = [0] * M
WA = 0

for j in range(M)[::-1]:
    if A[j][1] == 'AC' and (A[j][0] in AC) is False:
        AC[j] = A[j][0]
    elif A[j][1] == 'WA' and (A[j][0] in AC) is True:
        WA += 1

print(len(AC) - AC.count(0), WA)


### FIXED CODE ###

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

submit = [input().split() for i in range(M)]
ans = [[0, 0] for i in range(N)]

for i in range(M):
    tmp = int(submit[i][0]) - 1
    if submit[i][1] == 'AC' and ans[tmp][0] == 0:
        ans[tmp][0] += 1
    elif submit[i][1] == 'WA' and ans[tmp][0] == 0:
        ans[tmp][1] += 1

print(sum(ans[i][0] for i in range(N)), sum(ans[i][1] for i in range(N) if ans[i][0] == 1))
### BUGGY CODE ###

k = int(input())
t = 7
kou = 1

if k % 2 != 0:
  if k % 5 != 0:
    while t % k != 0:
      kou += 1
      t = 10 * t + 7
    
    print(kou)
    quit()

print(-1)

### FIXED CODE ###

K = int(input())

if K % 2 == 0 or K % 5 == 0:
    print(-1)
    exit()

i = 0
ai = 0
while True:
    ai = (ai * 10 + 7) % K
    i += 1
    if ai == 0:
        break
print(i)
### BUGGY CODE ###

n, k = map(int, input().split())
a = [int(i) - 1 for i in input().split()]
ans = 0
while k:
    if k & 1:
        ans = a[ans]
    c = [a[a[i]] for i in range(n)]
    a = c[:]
    k >>= 1
print(ans + 1)

### FIXED CODE ###

from copy import copy
n, k = map(int, input().split())
a = [int(i) - 1 for i in input().split()]
ans = 0
while k:
    if k & 1:
        ans = a[ans]
    c = [a[a[i]] for i in range(n)]
    a = copy(c)
    k >>= 1
print(ans + 1)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

N,K = map(int,input().split())
H = list(map(int,input().split()))
inf = 10**9+7
dp = [inf] * (N+10)
dp[0] = 0
for i,h in enumerate(H):
    for j in range(1,K+1):
        if i+j < N:
            dp[i+j] = min(dp[i+j],dp[i] + abs(h-H[i+j]))

print(dp[N-1])


### FIXED CODE ###

#import sys 
#input = sys.stdin.readline

N,K = map(int,input().split())
h = list(map(int,input().split()))

dp = [0] * 100010

dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2,min(K,N)):
    Minimum = dp[i-1]+abs(h[i]-h[i-1])
    for j in range(2,i+1):
        Minimum = min(dp[i-j]+abs(h[i]-h[i-j]),Minimum)
    dp[i] = Minimum
if N > K:
    if K == 1:
        for i in range(K,N):
            Minimum = dp[i-1]+abs(h[i]-h[i-1])
            dp[i] = Minimum
        
    else:
        for i in range(K,N):
            Minimum = dp[i-1]+abs(h[i]-h[i-1])
            for (j,k) in zip(dp[i-K:i-1],h[i-K:i-1]):
                Minimum = min(j+abs(h[i]-k),Minimum)
            dp[i] = Minimum
        
print(dp[N-1])
### BUGGY CODE ###

import numpy as np
N, W0 = map(int, raw_input().split())
items = [map(int, raw_input().split()) for i in range(N)]
w0, _ = items[0]
dp = np.full((N, N*4), -1)
def dfs(i, W):
    if i < 0:
        return 0
    if (W-N*w0 >= 0) and (dp[i][W-N*w0] != -1):
        return dp[i][W-N*w0]
    w, v = items[i]
    res = dfs(i-1, W)
    if W >= w:
        res = max(res, dfs(i-1, W-w) + v)
    if (W-N*w0 >= 0):
        dp[i][W-N*w0] = res
    return res
print dfs(N-1, W0)

### FIXED CODE ###

import numpy as np
N, W0 = map(int, raw_input().split())
items = [map(int, raw_input().split()) for i in range(N)]
w0, _ = items[0]
dp = {}
def dfs(i, W):
    if i < 0:
        return 0
    if (i, W) in dp:
        return dp[i, W]
    w, v = items[i]
    res = dfs(i-1, W)
    if W >= w:
        res = max(res, dfs(i-1, W-w) + v)
    dp[i, W] = res
    return res
print dfs(N-1, W0)
### BUGGY CODE ###

#頭おかしくなりそうｗ
#大体考え方は合ってるはずだけどクラス分けするのめんどくさい
D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]
t = [int(input()) for _ in range(D)]
M = int(input())
d = []
q = []
for i in range(M):
    a, b = map(int, input().split())
    d.append(a)
    q.append(b)

    
now = 1
score = 0

decrease = 0


for i,z in enumerate(t):
    score += s[i][z - 1]

def change():
    ret = 0
    contest = [0] * 26
    date = [D * (1 + D) // 2] * 26
    for i, z in enumerate(t):
        date[z - 1] -= (D - i) * (i -contest[z-1]+ 1)
        contest[z - 1] = i + 1
    for i, z in enumerate(date):
        ret += c[i] * z
    return ret


for i, z in zip(d, q):
    score -= s[i - 1][t[i - 1] - 1]
    score += s[i - 1][z - 1]
    t[i - 1] = z
    decrease = change()
    print(score-decrease)

### FIXED CODE ###

#頭おかしくなりそうｗ
#大体考え方は合ってるはずだけどクラス分けするのめんどくさい
D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]
t = [int(input()) for _ in range(D)]
M = int(input())
d = []
q = []
for i in range(M):
    a, b = map(int, input().split())
    d.append(a)
    q.append(b)

    
now = 1
score = 0

decrease = 0


for i,z in enumerate(t):
    score += s[i][z - 1]

def change():
    ret = 0
    contest = [0] * 26
    date = [D * (1 + D) // 2] * 26
    for i, z in enumerate(t):
        date[z - 1] -= (D - i) * (i -contest[z-1]+ 1)
        contest[z - 1] = i + 1
    for i, z in enumerate(date):
        ret += c[i] * z
    return ret


for i, z in zip(d, q):
    score -= s[i - 1][t[i - 1] - 1]
    score += s[i - 1][z - 1]
    t[i - 1] = z
    decrease = change()
    print(score-decrease)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [tuple(map(int, input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x: -x[1])

count = 0
end = False
for b, c in bc:
  if end:
    break
  if len(a) <= 0:
    break
  for j in range(b):
    if a[0] < c:
      count += c
      del a[0]
    else:
      end = True

print(count + sum(a))


### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [tuple(map(int, input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x: -x[1])
# print(a)
# print(bc)

count = 0
idx = -1
end = False
for b, c in bc:
  if idx + b <= n-1 and a[idx+b] < c:
    count += b * c
    idx += b
  else:
    for i in range(idx+1, idx+1+b):
      if i >= n or end:
        break
      else:
        if a[i] < c:
          count += c
          idx += 1
        else:
          end = True
  # print((idx, count))
  if end:
    break

if idx <= n-2:
  count += sum(a[idx+1:])

print(count)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A_temp=[0]*N
    for k in range(K):
        for i in range(N):
            for j in range(max(0,i-A[i]),min(N,i+A[i]+1)):
                A_temp[j]+=1
        A=A_temp
        A_temp=[0]*N
    print(' '.join(map(str,A)))
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    for k in range(K):
        A_temp=[0]*(N+1)
        for i in range(N):
            A_temp[max(0,i-A[i])]+=1
            if i+A[i]+1<=N-1:
                A_temp[i+A[i]+1]-=1
            
        A[0]=A_temp[0]
        for j in range(1,N):
            A_temp[j]+=A_temp[j-1]
            A[j]=A_temp[j]
        for ai in A:
            if ai != N:
                break
        else:
            break
                
    print(' '.join([str(a) for a in A]))
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys 
from heapq import heappop,heappush
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
data = []
for i in range(N):
    A = list(map(int,readline().split()))
    for j in range(i):
        data.append((A[j],j+1,i+1))
        
def dijkstra(q,edges,dist):
    while q:
        cost, v_from = heappop(q)
        if dist[v_from] < cost:
            continue
        for _cost,v_to in edges[v_from]:
            newcost = cost+_cost
            if newcost < dist[v_to]:
                dist[v_to] = newcost
                heappush(q,(newcost,v_to))             
    return 

data = sorted(data)
edges = [[] for _ in range(N+1)]
INF = 10**31
ans = 0
for c,i,j in data:
    dist = [INF]*(N+1)
    dist[i] = 0
    q = [(0,i)]
    dijkstra(q,edges,dist)
    if c < dist[j]:
        edges[i].append((c,j))
        edges[j].append((c,i))
        ans += c
    elif c > dist[j]:
        print(-1)
        sys.exit()

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys 
from heapq import heappop,heappush
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
# INF = 10**31
cost = [[0]*(N+1) for _ in range(N+1)] 
tmp = [[0]*(N+1) for _ in range(N+1)] 
for i in range(N):
    A = list(map(int,readline().split()))
    for j in range(N):
        cost[i+1][j+1] = A[j]
        tmp[i+1][j+1] = A[j]
        

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if cost[i][j] > cost[i][k] + cost[k][j]:
                print(-1)
                sys.exit()
            if cost[i][k] and cost[k][j] and cost[i][j] == cost[i][k] + cost[k][j]:
                tmp[i][j] = 0

ans = sum([sum([c for c in row]) for row in tmp])
print(ans//2)
### BUGGY CODE ###

import math

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

count_l = 0
count_r = 0

if s[0] == 'B':
    s2[0] = 'L'
    count_l += 1
else:
    s2[0] = 'R'
    count_r += 1

for i in range(1,2*n): 
    if s[i-1] == s[i]:
        if s2[i-1] == 'L':
            s2[i] = 'R'
            count_r += 1
        else:
            s2[i] = 'L'
            count_l += 1
    else:
        if s2[i-1] == 'L':
            s2[i] = 'L'
            count_l += 1
        else:
            s2[i] = 'R'
            count_r += 1
        
if s2[0] == 'R' or s2[2*n-1] == 'L' or count_l != count_r:
    print(0)
    exit()
            
ans = 1
count_l = 0
for i in range(0,2*n): 
    if s2[i] == 'L':
        count_l += 1
    else:
        ans *= count_l
        count_l -= 1
    
print((ans * math.factorial(n)) % (10**9 + 7))

### FIXED CODE ###

import math

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

if s[0] == 'B':
    s2[0] = 'L'
else:
    s2[0] = 'R'

for i in range(1,2*n): 
    if s[i-1] == s[i]:
        if s2[i-1] == 'L':
            s2[i] = 'R'
        else:
            s2[i] = 'L'
    else:
        if s2[i-1] == 'L':
            s2[i] = 'L'
        else:
            s2[i] = 'R'
        
if s2[0] == 'R' or s2[2*n-1] == 'L' or s2.count('L') != s2.count('R'):
    print(0)
    exit()
            
ans = 1
count_l = 0
for s2_str in s2: 
    if s2_str == 'L':
        count_l += 1
    else:
        ans *= count_l
        ans %= 10**9 + 7
        count_l -= 1
    
print(ans * math.factorial(n) % (10**9 + 7))
### BUGGY CODE ###

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

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

le = -1
ri = max(A) + 1
mid = (le + ri) // 2
while ri - le > 1:
    Ac = [-1 + 2 * int(A[i] >= mid) for i in range(n)]
    S = [0] * n
    S[0] = Ac[0]
    for i in range(n-1):
        S[i+1] = S[i] + Ac[i+1]
    bit = Bit(n+2)
    ans = 0


    Smin = min(S)
    S = [S[i]-min(S)+1 for i in range(n)]
    #print(S)
    for i, p in enumerate(S):
        bit.add(p, 1)
        ans += bit.sum(p) - 1  # 「S[i] >= S[i]」をカウントしないように1を引く

    #print(le, ri, mid, ans)

    if ans >= n*(n-1)//(2*2):
        le = mid
    else:
        ri = mid
    mid = (le + ri) // 2

print(le)
    


### FIXED CODE ###

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

# n = 4
# A = [i+1 for i in range(n)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

#print((n*(n+1))//(2*2))

le = -1
ri = max(A) + 1
mid = (le + ri) // 2
while ri - le > 1:
    S = [0] * n
    S[0] = -1 + 2 * int(A[0] >= mid)
    for i in range(n-1):
        S[i+1] = S[i] - 1 + 2 * int(A[i+1] >= mid)
    bit = Bit(n+2)
    ans = 0
    for i in range(n):
        if S[i] >= 0:
            ans += 1

    #print("S OK")

    Smin = min(S)
    S = [S[i] - Smin + 1 for i in range(n)]

    #print("S OK2")
    #print(S)
    for i, p in enumerate(S):
        
        bit.add(p, 1)

        ans += bit.sum(p) - 1  # 「S[i] >= S[i]」をカウントしないように1を引く
        #print(i,ans)


    #print(le, ri, mid, ans)

    if ans >= (n*(n+1))//(2*2):
        le = mid
    else:
        ri = mid
    mid = (le + ri) // 2

print(le)
### BUGGY CODE ###

from collections import deque

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

graph = [[] for i in range(N)]
for i in range(M):
    L,R,D = map(int, input().split())
    graph[L-1].append([R-1, D])
    graph[R-1].append([L-1, -D])

visited = [False] * N

def bfs(id):
    dist = [int(1e10)] * N
    Q = deque()
    Q.append(id)
    dist[id] = 0

    while len(Q) != 0:
        v = Q.popleft()
        visited[v] = True

        for edge in graph[v]:
            u, d = edge[0], edge[1]

            if dist[u] == int(1e10):
                dist[u] = dist[v] + d
                Q.append(u)
            elif dist[u] != dist[v] + d:
                print("No")
                exit()


for i in range(N):
    if not visited[i]:
        bfs(i)

print("Yes")


### FIXED CODE ###

from collections import deque

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

graph = [[] for i in range(N)]
for i in range(M):
    L,R,D = map(int, input().split())
    graph[L-1].append([R-1, D])
    graph[R-1].append([L-1, -D])

dist = [int(1e10)] * N

def bfs(id):
    Q = deque()
    Q.append(id)
    dist[id] = 0

    while len(Q) != 0:
        v = Q.popleft()

        for edge in graph[v]:
            u, d = edge[0], edge[1]

            if dist[u] == int(1e10):
                dist[u] = dist[v] + d
                Q.append(u)
            elif dist[u] != dist[v] + d:
                print("No")
                exit()


for i in range(N):
    if dist[i] == int(1e10):
        bfs(i)

print("Yes")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
P = list(map(lambda x:int(x)-1,input().split()))

costs = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        costs[i][j] = min(i,j,N-1-i,N-1-j)
exist = [[1]*N for _ in range(N)]

from collections import deque
dxy = [(0,1),(1,0),(0,-1),(-1,0)]

ans = 0
for p in P:
    y,x = divmod(p,N)
    ans += costs[y][x]
    exist[y][x] = 0
    q = deque([(x,y)])
    while q:
        x,y = q.popleft()
        for dx,dy in dxy:
            nx,ny = x+dx,y+dy
            if not 0 <= nx < N: continue
            if not 0 <= ny < N: continue
            if costs[ny][nx] > costs[y][x] + exist[y][x]:
                costs[ny][nx] = costs[y][x] + exist[y][x]
                q.append((nx,ny))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
P = list(map(lambda x:int(x)-1,input().split()))

costs = [0]*(N*N)
for i in range(N):
    for j in range(N):
        costs[i*N+j] = min(i,j,N-1-i,N-1-j)
exist = [1]*(N*N)

from collections import deque
ans = 0
for p in P:
    ans += costs[p]
    exist[p] = 0
    q = deque([p])
    while q:
        p = q.popleft()
        y,x = divmod(p,N)
        if x < N-1:
            np = p + 1
            if costs[np] > costs[p] + exist[p]:
                costs[np] = costs[p] + exist[p]
                q.append(np)
        if x > 0:
            np = p - 1
            if costs[np] > costs[p] + exist[p]:
                costs[np] = costs[p] + exist[p]
                q.append(np)
        if y < N-1:
            np = p + N
            if costs[np] > costs[p] + exist[p]:
                costs[np] = costs[p] + exist[p]
                q.append(np)
        if y > 0:
            np = p - N
            if costs[np] > costs[p] + exist[p]:
                costs[np] = costs[p] + exist[p]
                q.append(np)
print(ans)
### BUGGY CODE ###

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

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

min_num = a[0]
for i in range(m):
  b,c = map(int, input().split())
  if min_num >= c:
    continue
  else:
    for j in range(b):
      if a[0] < c:
        heapq.heappop(a)
        heapq.heappush(a, c)
      else:
        break
    min_num = a[0]

print(sum(a))

### FIXED CODE ###

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

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

min_num = a[0]

tmp_array = []

for i in range(m):
  b,c = map(int, input().split())
  tmp_array.append([b,c])

sort_array = sorted(tmp_array, key=lambda x: -x[1])

for i in range(m):
  b = sort_array[i][0]
  c = sort_array[i][1]
  if min_num >= c:
    continue
  else:
    for j in range(b):
      if a[0] < c:
        heapq.heappop(a)
        heapq.heappush(a, c)
      else:
        break
    min_num = a[0]

#for i in range(m):
#  b,c = map(int, input().split())
#  if min_num >= c:
#    continue
#  else:
#    for j in range(b):
#      if a[0] < c:
#        heapq.heappop(a)
#        heapq.heappush(a, c)
#      else:
#        break
#    min_num = a[0]

print(sum(a))
### BUGGY CODE ###

a = []
n = int(input())
for i in range(n):
    a.append(int(input()))
for i in range(n):
    if i == 0 : print(max(a[1:]))
    elif i == n - 1 : print(max(a[:i]))
    else:
        maxa = max(a[:i])
        maxb = max(a[i + 1:])
        print(max(maxa, maxb))

    


### FIXED CODE ###

a = []
c = []
n = int(input())
max_i = 0
max_s = 0
b = False
for i in range(n):
    aa = int(input())
    a.append(aa) 
    c.append(aa)   
    if max_i < aa : max_i = aa

c.remove(max_i)
max_s = max(c)

for i in range(n):
    if a[i] != max_i : print(max_i)
    else:print(max_s)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

List2=[list(map(int,input().split())) for i in range(M)]
uf = UnionFind(N+1)

for i in range(M):
  a = List2[i][0]
  b = List2[i][1]  
  uf.union(a, b)
  
cnt = 0
G = uf.all_group_members()
for i in range(N):
  a = uf.find(List[i])
  b = G[a]
  if i+1 in b:
    cnt += 1
  
print(cnt)

### FIXED CODE ###

class UnionFindTree():
    
    def __init__(self, N):
        self.parent = [-1]*(N+1)
        self.rank = [1]*(N+1)
        self.size = [1]*(N+1)
  
    def find(self, i):
        if self.parent[i] == -1:
            group = i
        else:
            group = self.find(self.parent[i]) 
            self.parent[i] = group
        return group
      
    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] == self.rank[py]: # rank is same
                self.rank[px] += 1
            elif self.rank[px] < self.rank[py]:
                px, py = py, px
                
            self.parent[py] = px
            self.size[px] += self.size[py]
    
    def getsize(self, x):
        return self.size[self.find(x)]
    
    def groups(self, index1=True):
        return set([self.find(i) for i in range(0+index1, N+index1)])
      
N,M = map(int,input().split())
List=list(map(int,input().split()))

List2=[list(map(int,input().split())) for i in range(M)]
uf = UnionFindTree(N+1)

for i in range(M):
  a = List2[i][0]
  b = List2[i][1]  
  uf.unite(a, b)
  
cnt = 0
for i,w in enumerate(List):
  if uf.find(i+1) == uf.find(w):
    cnt += 1
  
print(cnt)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = list(input())
num = list(range(N))
dic1 = dict(zip(num,S))
q = [list(map(lambda x: int(x)-1,input().split())) for _ in range(Q)]
dic2 = {}
for i in range(N-1):
    if dic1[i]+dic1[i+1] == "AC":
        dic2[i] = i
vl = list(dic2.values())
num = list(range(len(vl)))
dic3 = dict(zip(num,vl))
for i in range(Q):
    ans = 0
    for j in range(len(vl)):
        if q[i][0] <= dic3[j] < q[i][1]:
            ans += 1
    print(ans)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
ac = [0]*(N+1)
for i in range(N):
    ac[i+1] = ac[i] + (1 if S[i:i+2] == "AC" else 0)
for i in range(Q):
    l,r = map(int,input().split())
    print(ac[r-1]-ac[l-1])