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

import numpy as np
import collections
H,W=map(int,input().split())
A=[input() for j in range(H)]
went=[[False]*W for i in range(H)]
queue=collections.deque()
for x,i in enumerate(A):
    for y,j in enumerate(i):
        if j=="#":
            went[x][y]=True
            queue.append((x,y,0))
while queue:
    curx,cury,ct=queue.popleft()
    for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
        newx,newy=curx+dx,cury+dy
        newct=ct+1
        if 0<=newx<H and 0<=newy<W and (not went[newx][newy]):
            went[newx][newy]=True
            queue.append((newx,newy,newct))
print(ct)

### FIXED CODE ###

import collections
H,W=map(int,input().split())
went=[[False]*W for i in range(H)]
queue=collections.deque()
for hoge in range(H):
    for huga,t in enumerate(input()):
        if t=="#":
            went[hoge][huga]=True
            queue.append([hoge,huga,0])
while queue:
    curx,cury,ct=queue.popleft()
    for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
        newx,newy=curx+dx,cury+dy
        newct=ct+1
        if 0<=newx<H and 0<=newy<W and (not went[newx][newy]):
            went[newx][newy]=True
            queue.append([newx,newy,newct])
print(ct)
### BUGGY CODE ###

import itertools

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


def main():
    n, k = map(int, input().split())

    num = 10*100
    nums = [num + i for i in range(0, n+1)]

    # sums = []
    total = 0
    for i in range(k, n+2):
        _min = sum(nums[:i])
        _max = sum(nums[-i:])

        total += _max - _min + 1

    print(total)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())

    num = 10*100
    nums = [num + i for i in range(0, n+1)]

    # sums = []
    total = 0
    for i in range(k, n+2):
        _min = int((nums[0]+nums[i-1])*(nums[i-1]-nums[0]+1)/2)
        _max = int((nums[-i]+nums[-1])*(nums[-1]-nums[-i]+1)/2)

        total += _max - _min + 1

    print(total%(10**9+7))

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

a,b,x = map(int,input().split())
ans=0
for i in range(a,b+1):
    if i%x==0:
        ans+=1
print(ans)

### FIXED CODE ###

a,b,x = map(int,input().split())
print(b//x-(a-1)//x)
### BUGGY CODE ###

from queue import Queue
h, w = map(int, input().split())
MAZE = ['#'*(w+2)]
for _ in range(h):
    MAZE.append("#"+input()+"#")
else:
    MAZE.append('#'*(w+2))

INF = 10**3
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def bfs(init_x, init_y):
    dp = [[INF]*(w+2) for _ in range(h+2)]
    q = Queue()
    q.put((init_x, init_y))
    dp[init_x][init_y] = 0
    while not q.empty():
        x, y = q.get()
        for i, j in directions:
            if MAZE[x+i][y+j] == '#':
                continue
            if dp[x+i][y+j] != INF:
                continue
            q.put((x+i, y+j))
        dp[x][y] = min(dp[x][y], min(dp[x+v][y+w]+1 for v, w in directions))
    return dp


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if MAZE[i][j] == '#':
            continue
        dp = bfs(i, j)
        ans = max(
            ans,  max(max([x for x in row if x < INF]+[0]) for row in dp))
print(ans)


### FIXED CODE ###

# 上下左右どこでもいける
# BFS
from queue import Queue
h, w = map(int, input().split())
MAZE = ['#'*(w+2)]
for _ in range(h):
    MAZE.append("#"+input()+"#")
else:
    MAZE.append('#'*(w+2))

INF = 10**3
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def bfs(init_x, init_y):
    dp = [[INF]*(w+2) for _ in range(h+2)]
    resisterd = [[0]*(w+2) for _ in range(h+2)]
    q = Queue()
    q.put((init_x, init_y))
    dp[init_x][init_y] = 0
    MAX = 0
    while not q.empty():
        x, y = q.get()
        for i, j in directions:
            if MAZE[x+i][y+j] == '#':
                continue
            if resisterd[x+i][y+j]:
                continue
            resisterd[x+i][y+j] = 1
            q.put((x+i, y+j))
        dp[x][y] = min(dp[x][y], min(dp[x+v][y+w]+1 for v, w in directions))
        MAX = max(MAX, dp[x][y])
    return MAX


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if MAZE[i][j] == '#':
            continue
        ans = max(ans, bfs(i, j))
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,T=map(int,input().split())
    A=[0]*N
    B=[0]*N
    for i in range(N):
        A[i],B[i]=map(int,input().split())
    A_argsorted=np.argsort(A)
    dp=[[0]*T for _ in range(N)]
    for i in range(N-1):
        for t in range(T-1):
            dp[i+1][t+1]=max(dp[i+1][t+1],dp[i][t+1])
            if t+1>=A[A_argsorted[i]]:
                dp[i+1][t+1]=max(dp[i+1][t+1],dp[i][t+1-A[A_argsorted[i]]]+B[A_argsorted[i]])
    ans=0
    for i in range(1,N):
        ans=max(ans,dp[i][T-1]+max([B[x] for x in A_argsorted[i:]]))
    print(ans)
        

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,T=map(int,input().split())
    l=[]
    for i in range(N):
        A,B=map(int,input().split())
        l.append((A,B))
    l.sort()
    dp=[[0]*T for _ in range(N)]
    for i in range(N-1):
        for t in range(T-1):
            dp[i+1][t+1]=max(dp[i+1][t+1],dp[i][t+1])
            if t+1>=l[i][0]:
                dp[i+1][t+1]=max(dp[i+1][t+1],dp[i][t+1-l[i][0]]+l[i][1])
    ans=0
    B_sorted=[x[1] for x in l]
    for i in range(1,N):
        ans=max(ans,dp[i][T-1]+max(B_sorted[i:]))
    print(ans)
        

if __name__ == '__main__':
    main()
### BUGGY CODE ###

h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
L = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        # if S[i][j] == '#':
        #     L[i][j] = 0
        if S[i][j] == '.':
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
R = [[0] * w for _ in range(h)]
for i in range(h):
    for j in reversed(range(w)):
        # if S[i][j] == '#':
        #     R[i][j] = 0
        if S[i][j] == '.':
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1
U = [[0] * w for _ in range(h)]
for j in range(w):
    for i in range(h):
        # if S[i][j] == '#':
        #     U[i][j] = 0
        if S[i][j] == '.':
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1
D = [[0] * w for _ in range(h)]
for j in range(w):
    for i in reversed(range(h)):
        # if S[i][j] == '#':
        #     D[i][j] = 0
        if S[i][j] == '.':
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j] + 1
tmp = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        tmp[i][j] = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, tmp[i][j])
print(ans)


### FIXED CODE ###

h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
L = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        # if S[i][j] == '#':
        #     L[i][j] = 0
        if S[i][j] == '.':
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
R = [[0] * w for _ in range(h)]
for i in range(h):
    for j in reversed(range(w)):
        # if S[i][j] == '#':
        #     R[i][j] = 0
        if S[i][j] == '.':
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1
U = [[0] * w for _ in range(h)]
for j in range(w):
    for i in range(h):
        # if S[i][j] == '#':
        #     U[i][j] = 0
        if S[i][j] == '.':
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1
D = [[0] * w for _ in range(h)]
for j in range(w):
    for i in reversed(range(h)):
        # if S[i][j] == '#':
        #     D[i][j] = 0
        if S[i][j] == '.':
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j] + 1
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
print(ans)
### BUGGY CODE ###

import sys
import os
import math


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = int(sys.stdin.buffer.readline().rstrip())
    A = list(map(int, sys.stdin.buffer.readline().split()))
    P = set(A)

    obj = {}
    for p in P:
        obj[p] = A.count(p)

    p = 0
    for v in obj.values():
        p += v * (v - 1) // 2

    for a in A:
        n = obj[a]
        t = p - n * (n - 1) // 2 + (n - 1) * (n - 2) // 2
        print(t)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import collections

def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = int(sys.stdin.buffer.readline().rstrip())
    A = list(map(int, sys.stdin.buffer.readline().split()))

    obj = collections.Counter(A)

    p = 0
    for v in obj.values():
        if v > 1:
            p += v * (v - 1) // 2

    for a in A:
        print(p - (obj[a] - 1))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
A_list = list(map(int,input().split()))
output = 1
flug = 0

for i in range(N):
    output *= A_list[i]
    if 0 in A_list:
        print(0)
        flug = 1
        break
    if (output > 10 ** 18):
        print(-1)
        flug = 1
        break
if(flug != 1):
    print(output)

### FIXED CODE ###

N = int(input())
A_list = list(map(int,input().split()))
output = 1
flug = 0

if 0 in A_list:
    print(0)
    flug = 1
if flug != 1:
    for i in range(N):
        output *= A_list[i]
        
        if (output > 10 ** 18):
            print(-1)
            flug = 1
            break
if(flug != 1):
    print(output)
### BUGGY CODE ###

num = int(input())
pole_list = [int(item) for item in input().split()]

triangle_list = []

for i, a in enumerate(pole_list):
    for k, b in enumerate(pole_list):
        for m, c in enumerate(pole_list):

            if a < b + c and b < c + a and c < a + b and i != k and k != m and m != i:
                triangle = sorted([i, k, m])
                triangle_list.append(str(triangle[0]) + str(triangle[1]) + str(triangle[2]))
# print(set(triangle_list))
print(len(set(triangle_list)))


### FIXED CODE ###

from bisect import bisect_left
 
N = int(input())
Lmat = [int(n) for n in input().split()]
Lmat.sort()
 
sum = 0

for i in range(N):
    for j in range(i + 1, N):
        sum += bisect_left(Lmat, Lmat[i]+Lmat[j]) - (j + 1)
        
print(sum)
### BUGGY CODE ###

from sys import stdin
import numpy as np

N = int(stdin.readline().rstrip().split()[0])
A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]

def G(_a, _b):
  if _a>=_b:
    a, b = _a, _b
  else:
    a, b = _b, _a
  
  while True:
    c = a%b
    if c == 0:
      break
    a,b = b,c
  
  return b
ans=0
L=list(set(A))
L_array = np.array(L)
if np.sum(L%np.min(L))==0:
  ans = min(L)
while ans==0:
  if len(L)==1:
    ans = L[0]
    break
  if min(L)==1:
    ans = 1
    break
  g = G(L[-2], L[-1])
  L[-2] = g
  L.pop()

print(ans)
    

### FIXED CODE ###

from sys import stdin
import numpy as np

N = int(stdin.readline().rstrip().split()[0])
A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]

def G(_a, _b):
  if _a>=_b:
    a, b = _a, _b
  else:
    a, b = _b, _a
  
  while True:
    c = a%b
    if c == 0:
      break
    a,b = b,c
  
  return b

L = np.array(list(set(A)))
mini = np.min(L)
yaku = [1]
i=2
r_mini = np.sqrt(mini)
while i<=r_mini:
  if mini%i==0:
    yaku.append(i)
  i+=1
yaku2 = list(map(lambda x: int(mini/x), yaku))
yaku = yaku[::-1]
yaku2.extend(yaku)
for y in yaku2:
  if np.sum(L%y)==0:
    ans = y
    break

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

def binary_search(data, value):
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2            # 探索する範囲の中央を計算
        if data[mid] == value:
            # 中央の値と一致した場合は位置を返す
            return mid
        elif data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid + 1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid - 1
    return -1            # 見つからなかった場合

import heapq

n,x,mod = map(int,input().split())
c = []
heapq.heapify(c)
cc = []
sisu = 1
count = 0
while True:
    num = pow(x, sisu, mod)
    if binary_search(c, num) != -1:
        b = cc.index(num)
        l = count - b
        cycle = cc[b:]
        startl = b
        start = cc[:b]
        break
    count += 1
    sisu *= 2
    heapq.heappush(c, num)
    cc.append(num)

# print(cc)
# print(cycle,l)
# print(start,startl)
ans = 0
if n <= startl:
    for i in range(n):
        ans += start[i]
    print(ans)
else:
    ans += sum(start)
    n -= startl
    # print(n)
    syo = n // l
    amari = n % l
    ans += sum(cycle)*syo
    for i in range(amari):
        ans += cycle[i]
    print(ans)

### FIXED CODE ###

def binary_search(data, value):
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2            # 探索する範囲の中央を計算
        if data[mid] == value:
            # 中央の値と一致した場合は位置を返す
            return mid
        elif data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid + 1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid - 1
    return -1            # 見つからなかった場合

import heapq

n,x,mod = map(int,input().split())
c = [x]
heapq.heapify(c)
cc = [x]
num = x
count = 1
while True:
    num = pow(num, 2, mod)
    if binary_search(c, num) != -1:
        b = cc.index(num)
        l = count - b
        cycle = cc[b:]
        startl = b
        start = cc[:b]
        break
    count += 1
    heapq.heappush(c, num)
    cc.append(num)

# print(cc)
# print(cycle,l)
# print(start,startl)
ans = 0
if n <= startl:
    for i in range(n):
        ans += start[i]
    print(ans)
else:
    ans += sum(start)
    n -= startl
    # print(n)
    syo = n // l
    amari = n % l
    s = [0]*(l+1)
    for i in range(1,l+1):
        s[i] = s[i-1] + cycle[i-1]
    ans += s[l]*syo + s[amari]
    print(ans)
### BUGGY CODE ###

import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
 
n, m, p = na()
 
def bf(es, n, start):
    d = [999999999999] * n
    d[start] = 0
 
    for r in range(n-1):
        updated = False
        for e in es:
            if d[e[0]] == 999999999999:
                continue
            if d[e[0]] + e[2] < d[e[1]]:
                d[e[1]] = d[e[0]] + e[2]
                updated = True
        if not updated:
            break
 
    for e in es:
        if d[e[0]] < 999999999999 and d[e[0]] + e[2] < d[e[1]]:
            return None
 
    return d
 
es = []
for i in range(m):
    a, b, c = na()
    es.append((a-1, b-1, -(c-p)))
 
import collections
q = collections.deque()
q.append(n-1)
 
valid = [False] * n
valid[n-1] = True
while len(q) > 0:
    cur = q.popleft()
    for e in es:
        if e[1] == cur and not valid[e[0]]:
            valid[e[0]] = True
            q.append(e[0])
 
nes = []
for e in es:
    if valid[e[0]] and valid[e[1]]:
        nes.append(e)
es = nes
 
d = bf(es, n, 0)
if not d:
    print(-1)
else:
    print(max(0, -d[n-1]))

### FIXED CODE ###

import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
 
n, m, p = na()
 
def bf(es, n, start):
    d = [999999999999] * n
    d[start] = 0
 
    for r in range(n-1):
        updated = False
        for e in es:
            if d[e[0]] == 999999999999:
                continue
            if d[e[0]] + e[2] < d[e[1]]:
                d[e[1]] = d[e[0]] + e[2]
                updated = True
        if not updated:
            break
 
    for e in es:
        if d[e[0]] < 999999999999 and d[e[0]] + e[2] < d[e[1]]:
            return None
 
    return d
 
es = []
for i in range(m):
    a, b, c = na()
    es.append((a-1, b-1, -(c-p)))
 
import collections
q = collections.deque()
q.append(n-1)
 
valid = [False] * n
valid[n-1] = True
while len(q) > 0:
    cur = q.popleft()
    for e in es:
        if e[1] == cur and not valid[e[0]]:
            valid[e[0]] = True
            q.append(e[0])
 
nes = []
for e in es:
    if valid[e[0]] and valid[e[1]]:
        nes.append(e)
es = nes
 
d = bf(es, n, 0)
if not d:
    print(-1)
else:
    print(max(0, -d[n-1]))
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]

# nCrの剰余
def combinations_mod(n, r, mod=1000000007):
    """Returns nCr in mod."""
    r = min(r, n - r)
    combs = 1
    for i, j in zip(range(n - r + 1, n + 1), range(1, r + 1)):
        combs *= (i % mod) * pow(j, mod - 2, mod)
        combs %= mod
    return combs


def main():
    N, K = NMI()
    A = NLI()
    A.sort()
    ans = 0
    for i in range(N):
        max_num = 0
        min_num = 0
        if i >= K-1:
            max_num = combinations_mod(i, K-1)
        if N-1-i >= K-1:
            min_num = combinations_mod(N-1-i, K-1)
        ans += (max_num - min_num) * A[i] % MOD
    print(ans%MOD)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]

# nCrの剰余
def combinations_mod(n, r, mod=1000000007):
    """Returns nCr in mod."""
    r = min(r, n - r)
    combs = 1
    for i, j in zip(range(n - r + 1, n + 1), range(1, r + 1)):
        combs *= (i % mod) * pow(j, mod - 2, mod)
        combs %= mod
    return combs


def main():
    N, K = NMI()
    A = NLI()
    A.sort()
    ans = 0
    fac = [1]*(N+1)
    inv = [1]*(N+1)

    for i in range(1, N+1):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = inv[i-1] * pow(i, -1, MOD) % MOD

    for i in range(N):
        max_num = 0
        min_num = 0
        if i >= K-1:
            max_num = fac[i] * inv[K-1] * inv[i-K+1]
        if N-1-i >= K-1:
            min_num = fac[N-1-i] * inv[K-1] * inv[N-K-i]
        ans += (max_num - min_num) * A[i] % MOD
    print(ans%MOD)


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

import bisect
from itertools import accumulate
def hsnum(ls,x):
    n = len(ls)
    num = 0
    for i in range(n):
        y = x-ls[i]
        num += n-bisect.bisect_left(ls,y)
    return num
n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
suma = [0]+list(accumulate(a))
lx = 0
rx = 10**12
error = 0
while lx < rx:
    mx = (lx+rx)//2
    if hsnum(a,mx) < m:
        rx = mx
    elif hsnum(a,mx) > m:
        if hsnum(a,mx+1) < m:
            error = hsnum(a,mx)-m
            lx = mx
            break
        lx = mx + 1
    else:
        lx = mx
        break
maxsum = lx
ans = 0
for i in range(n):
    rema = maxsum - a[i]
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*a[i]
    ans += suma[n]-suma[j]
print(ans-error*lx)

### FIXED CODE ###

def main():
  import bisect
  import sys
  from itertools import accumulate
  input = sys.stdin.readline
  def hsnum(x):
    num = 0
    for i in a:
      y = x-i
      num += n-bisect.bisect_left(a,y)
    return num
  n,m = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort()
  suma = [0]+list(accumulate(a))
  lx = 0
  rx = 2*10**5+2
  error = 0
  while lx+1 < rx:
    mx = (lx+rx)//2
    if hsnum(mx) < m:
      rx = mx
    elif hsnum(mx) > m:
      lx = mx + 1
    else:
      lx = mx
      break
  if hsnum(lx)<m:
    lx -= 1
  error = hsnum(lx)-m
  ans = 0
  for i in a:
    rema = lx - i
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*i-suma[j]
  ans += suma[n]*n
  print(ans-error*lx)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from sys import stdin
from collections import defaultdict,deque
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

    def allset(self):
        d = defaultdict(set)
        for i in range(self.n):
            d[self.find(i)].add(i)
        for i in d.keys():
            d[i] = deque(sorted(list(d[i])))
        return d

def main():
    N,M = map(int,stdin.readline().split())
    uf = UnionFind(N)
    p = list(map(int,stdin.readline().split()))
    p = list(map(lambda x: x-1,p))
    ans = 0
    for _ in range(M):
        x,y = map(int,stdin.readline().split())
        x -= 1
        y -= 1
        uf.union(x,y)
    d = uf.allset()
    for i in range(N):
        tmp = p[i]
        r = uf.find(tmp)
        if uf.same(r,i):
            pre = p[i]
            if i in d[r]:
                new = i
                #d[r].remove(i)
            else:
                new = d[r].popleft()
            swap = p.index(new)
            p[i] = new
            p[swap] = pre
    for i in range(N):
        if p[i] == i:ans += 1
    print(ans)
    #print(*list(map(lambda x:x+1,p)))
if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin
from collections import defaultdict,deque
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))



def main():
    N,M = map(int,stdin.readline().split())
    uf = UnionFind(N)
    p = list(map(int,stdin.readline().split()))
    p = list(map(lambda x: x-1,p))
    ans = 0
    for _ in range(M):
        x,y = map(int,stdin.readline().split())
        x -= 1
        y -= 1
        uf.union(x,y)
    for i in range(N):
        tmp = p[i]
        if not uf.same(tmp,i):continue
        else:ans += 1
    print(ans)
    #print(*list(map(lambda x:x+1,p)))
if __name__ == "__main__":
    main()