Problem:


Score : 400 points

Problem Statement

We have a permutation of the integers from 1 through N, p_1, p_2, .., p_N.
We also have M pairs of two integers between 1 and N (inclusive), represented as (x_1,y_1), (x_2,y_2), .., (x_M,y_M).
AtCoDeer the deer is going to perform the following operation on p as many times as desired so that the number of i (1 ≤ i ≤ N) such that p_i = i is maximized:

Choose j such that 1 ≤ j ≤ M, and swap p_{x_j} and p_{y_j}.

Find the maximum possible number of i such that p_i = i after operations.

Constraints

2 ≤ N ≤ 10^5

1 ≤ M ≤ 10^5

p is a permutation of integers from 1 through N.

1 ≤ x_j,y_j ≤ N

x_j ≠ y_j

If i ≠ j, \{x_i,y_i\} ≠ \{x_j,y_j\}.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
p_1 p_2 .. p_N
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the maximum possible number of i such that p_i = i after operations.

Sample Input 1

5 2
5 3 1 4 2
1 3
5 4

Sample Output 1

2

If we perform the operation by choosing j=1, p becomes 1 3 5 4 2, which is optimal, so the answer is 2.

Sample Input 2

3 2
3 2 1
1 2
2 3

Sample Output 2

3

If we perform the operation by, for example, choosing j=1, j=2, j=1 in this order, p becomes 1 2 3, which is obviously optimal.
Note that we may choose the same j any number of times.

Sample Input 3

10 8
5 3 6 8 7 10 9 1 2 4
3 1
4 1
5 9
2 5
6 5
3 5
8 9
7 9

Sample Output 3

8

Sample Input 4

5 1
1 2 3 4 5
1 5

Sample Output 4

5

We do not have to perform the operation. 



Sample input:
5 2
5 3 1 4 2
1 3
5 4


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
P = list(map(int, input().split()))
K = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    K[x].append(y)
    K[y].append(x)
used = [0]*N
OK = [0]*N
Origin = []
for i in range(N):
    P[i] -= 1
    if i == P[i]:
        OK[i] = 1
        Origin.append(i)
ans = 0
for i in range(N):
    c = 0
    if used[i] == 0:
        used[i] = 1
        S = deque([i])
        Enable = Origin.copy()
        Enable.append(i)
        T = OK.copy()
        T[P[i]] = 1
        while S:
            t = S.popleft()
            for j in K[t]:
                if used[j] == 0:
                    used[j] = 1
                    Enable.append(j)
                    T[P[j]] = 1
                    S.append(j)
    Enable = list(set(Enable))
    for j in Enable:
        if T[j] == 1:
            c += 1
    ans = max(ans, c)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
P = list(map(int, input().split()))
K = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    K[x].append(y)
    K[y].append(x)
used = [0]*N
OK = []
for i in range(N):
    P[i] -= 1
    if i == P[i]:
        OK.append(i)
ans = 0
for i in range(N):
    if used[i] == 0:
        used[i] = 1
        S = deque([i])
        Enable = [i]
        Origin = [P[i]]
        while S:
            t = S.popleft()
            for j in K[t]:
                if used[j] == 0:
                    used[j] = 1
                    Enable.append(j)
                    Origin.append(P[j])
                    S.append(j)
    T_1 = set(OK + Enable)
    T_2 = set(OK + Origin)
    T_3 = set(OK + Enable + Origin)
    ans = max(ans, len(T_1) + len(T_2) - len(T_3))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
N, M = map(int, input().split())
P = list(map(int, input().split()))
K = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    K[x].append(y)
    K[y].append(x)
used = [0]*N
OK = []
for i in range(N):
    P[i] -= 1
    if i == P[i]:
        OK.append(i)
ans = 0
for i in range(N):
    if used[i] == 0:
        used[i] = 1
        S = deque([i])
        Enable = deque(OK.copy())
        Origin = deque(OK.copy())
        T_3 = deque(OK.copy())
        Enable.append(i)
        Origin.append(P[i])
        T_3.append(i)
        T_3.append(P[i])
        while S:
            t = S.popleft()
            for j in K[t]:
                if used[j] == 0:
                    used[j] = 1
                    Enable.append(j)
                    Origin.append(P[j])
                    T_3.append(j)
                    T_3.append(P[j])
                    S.append(j)
    T_1 = list(set(Enable))
    T_2 = list(set(Origin))
    ans = max(ans, len(T_1) + len(T_2) - len(set(T_3)))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
P = list(map(int, input().split()))
K = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    K[x].append(y)
    K[y].append(x)
used = [0]*N
OK = []
for i in range(N):
    P[i] -= 1
    if i == P[i]:
        OK.append(i)
ans = 0
for i in range(N):
    if used[i] == 0:
        used[i] = 1
        S = deque([i])
        Enable = [i]
        Origin = [P[i]]
        while S:
            t = S.popleft()
            for j in K[t]:
                if used[j] == 0:
                    used[j] = 1
                    Enable.append(j)
                    Origin.append(P[j])
                    S.append(j)
    T_1 = list(set(OK + Enable))
    T_2 = list(set(OK + Origin))
    ans = max(ans, len(T_1) + len(T_2) - len(set(T_1 + T_2)))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
q=[0]+list(map(int,input().split()))
e=[[]for _ in range(n+1)]
for i in range(m):
  x,y=map(int,input().split())
  e[x]+=[y]
  e[y]+=[x]
cnt=0
for i in range(n+1):
  que=[q[i]]
  a=[1]*(n+1)
  while que:
    now=que.pop()
    a[now]=0
    if now==i:
      cnt+=1
      break
    for to in e[now]:
      if a[to]==0:continue
      que+=[to]
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(100000)
    n, m, *pxy = map(int, open(0).read().split())
    p = pxy[:n]
    xy = pxy[n:]

    nb = [[] for _ in range(n)]
    for i, j in zip(xy[::2], xy[1::2]):
        i -= 1
        j -= 1
        nb[i].append(j)
        nb[j].append(i)

    f = [0 for _ in range(n)]

    def Q(i):
        if f[i]:
            return set()
        f[i] = 1
        tmp = nb[i]
        st = set(tmp)
        for j in tmp:
            st |= Q(j)
        return st

    gr = [-1 for _ in range(n)]
    c = 0
    for i in range(n):
        if f[i]:
            continue
        st = Q(i)
        if len(st) == 0:
            continue

        for k in list(st):
            gr[k] = c
        c += 1

    ans = 0
    for i in range(n):
        x = p[i] - 1
        if x == i:
            ans += 1
            continue
        a = gr[x]
        b = gr[i]
        if a == -1 or b == -1:
            continue
        elif a == b:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution 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())
p = list(map(int, input().split()))

uf = UnionFind(N)

for _ in range(M):
  x, y = map(lambda x: int(x)-1, input().split())
  uf.union(x, y)

D = uf.all_group_members()

ans = 0

for L in D.values():
  check = set(L)
  for i in L:
    if p[i]-1 in check:
      ans += 1 

print(ans)

Submission status: Time Limit Exceeded

Solution 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())
p = list(map(int, input().split()))

uf = UnionFind(N)

for _ in range(M):
  x, y = map(lambda x: int(x)-1, input().split())
  uf.union(x, y)

D = uf.all_group_members()

ans = []

for L in D.values():
  temp = set()
  for i in L:
    temp.add(p[i]-1)
  for i in set(L)&temp:
    ans.append(i)
 
print(len(ans))

Submission status: Time Limit Exceeded

Solution 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())
p = list(map(int, input().split()))

uf = UnionFind(N)

for _ in range(M):
  x, y = map(lambda x: int(x)-1, input().split())
  uf.union(x, y)

D = uf.all_group_members()

ans = 0

for L in D.values():
  check = set(L)
  for i in L:
    if p[i]-1 in L:
      ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution 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())
p = list(map(int, input().split()))

uf = UnionFind(N)

for _ in range(M):
  x, y = map(lambda x: int(x)-1, input().split())
  uf.union(x, y)

D = uf.all_group_members()

ans = 0

for L in D.values():
  temp = set()
  for i in L:
    temp.add(p[i]-1)
  ans += len(set(L) & temp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numba import jit

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


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
    @jit
    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]

uf = UnionFind(n)

for i in range(m):
    x , y = map(int, input().split())
    x-=1
    y-=1
    uf.union(x,y)
ans = 0

ro=uf.roots()

for i in ro:
    mem = uf.members(i)
    for j in mem:
        if p[j]-1 in mem:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n , m = map(int, input().split())
p = list(map(int,input().split()))

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 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]

uf = UnionFind(n)

for i in range(m):
    x , y = map(int, input().split())
    x-=1
    y-=1
    uf.union(x,y)
ans = 0

ro=uf.roots()

for i in ro:
    mem = uf.members(i)
    for j in mem:
        if p[j]-1 in mem:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n , m = map(int, input().split())
p = list(map(int,input().split()))

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 members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]


uf = UnionFind(n)

for i in range(m):
    x , y = map(int, input().split())
    x-=1
    y-=1
    uf.union(x,y)
ans = 0
for i in range(n):
    if i in uf.members(p[i]-1):
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
P = list(map(int, input().split()))

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())
      
uf = UnionFind(N)
for _ in range(M):
  x,y = map(int, input().split())
  uf.union(x-1,y-1)
  
ans = 0
for lis in uf.all_group_members().values():
  s = set(lis)
  for a in s:
    if P[a]-1 in s:
      ans += 1
      
print(ans)

Submission status: Time Limit Exceeded

Solution 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())
p = [int(i)-1 for i in input().split() ]

uf = UnionFind(n)
for i in range(m):
    x,y = map(int,input().split())
    uf.union(x-1,y-1)

ans=0
groups = uf.all_group_members().values()

for c in groups:
    ans+= len( set(c) & set(p[i] for i in c ) ) 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
p = list(map(int,input().split()))
ikeru = [[] for _ in range(n)]

for i in range(m):
	a, b = map(int, input().split())
	ikeru[a-1].append(b-1)
	ikeru[b-1].append(a-1)

union = []
imada = list(range(n))

while len(imada) != 0:
	kaisuu = 0
	settansaku = set([])
	setmada = {imada[0]}
	kouho = 1
	
	while kouho != 0:
		kaisuu += 1
		for i in list(setmada):
			settansaku.add(i)
			setmada.remove(i)
			imada.remove(i)
			kouho -= 1
			for k in ikeru[i]:
				if not k in setmada:
					if not k in settansaku:
						setmada.add(k)
						kouho += 1
	
	union.append(settansaku)


ans = 0
for i in range(len(union)):
	for j in union[i]:
		if p[j]-1 in union[i]:
			ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


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())


def main():
    N, M = in_nn()
    p = in_nl()

    uni = UnionFind(N)
    for i in range(M):
        x, y = in_nn()
        x, y = x - 1, y - 1
        uni.union(x, y)

    ans = 0
    for root, group in uni.all_group_members().items():
        s = set(group)
        for g in group:
            if p[g] - 1 in s:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


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())


def main():
    N, M = in_nn()
    p = in_nl()

    uni = UnionFind(N)
    for i in range(M):
        x, y = in_nn()
        x, y = x - 1, y - 1
        uni.union(x, y)

    ans = 0
    for root, group in uni.all_group_members().items():
        s = set()
        for g in group:
            s |= {p[g]}
        for g in group:
            if g + 1 in s:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,M = IL()
N = N+1
L = [0] + IL()

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())
      
U = UnionFind(N)
for _ in range(M):
  u,v = IL()
  U.union(u,v)

count = 0
for r in U.roots():
  MEMBER = U.members(r)
  NUMBER = [L[i] for i in MEMBER]
  NUMBER.sort()
  while MEMBER and NUMBER:
    if MEMBER[-1] == NUMBER[-1]:
      count += 1
      MEMBER.pop()
      NUMBER.pop()
    elif MEMBER[-1]>NUMBER[-1]:
      MEMBER.pop()
    else:
      NUMBER.pop()
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
import queue

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
route = [[] for i in range(n)]
dic = {}
for i in range(n):
  dic[a[i]-1]=i
for i in range(m):
  a, b = list(map(int, input().split()))
  a -= 1
  b -= 1
  route[a].append(b)
  route[b].append(a)
vis2 = [0]*n
q = queue.Queue()
ans = 0
for i in range(n):
  if vis2[i]==0:
    vis2[i]=1
    vis=[0]*n
    visited=[]
    visited.append(dic[i])
    vis[i]=1
    for j in route[i]:
      vis[j]=1
      vis2[j]=1
      q.put(j)
    while not q.empty():
      nex = q.get()
      vis2[nex]=1
      visited.append(dic[nex])
      for j in route[nex]:
        if vis[j] == 0:
          vis[j]=1
          q.put(j)
    for j in visited:
      if vis[j] ==1:
        ans+=1 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
route = [[] for i in range(n)]
dic = {}
for i in range(n):
  dic[a[i]-1]=i
for i in range(m):
  a, b = list(map(int, input().split()))
  a -= 1
  b -= 1
  route[a].append(b)
  route[b].append(a)
visited = [[] for i in range(n)]
vis = [0]*n
vis2 = [0]*n

q = queue.Queue()
ans = 0

for i in range(n):
  if vis2[i]==0:
    vis2[i]=1
    vis=[0]*n
    visited[i].append(dic[i])
    vis[i]=1
    for j in route[i]:
      visited[j]=visited[i]
      vis[j]=1
      vis2[j]=1
      q.put(j)
    while not q.empty():
      nex = q.get()
      vis2[nex]=1
      visited[nex]=visited[i]
      visited[i].append(dic[nex])
      for j in route[nex]:
        if vis[j] == 0:
          vis[j]=1
          q.put(j)
    for j in visited[i]:
      if vis[j] ==1:
        ans+=1 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
route = [[] for i in range(n)]
dic = {}
for i in range(n):
  dic[a[i]-1]=i
for i in range(m):
  a, b = list(map(int, input().split()))
  a -= 1
  b -= 1
  route[a].append(b)
  route[b].append(a)
visited = [[] for i in range(n)]
vis = [0]*n
vis2 = [0]*n

q = queue.Queue()
ans = 0

for i in range(n):
  if vis2[i]==0:
    vis2[i]=1
    vis=[0]*n
    visited[i].append(dic[i])
    vis[i]=1
    for j in route[i]:
      visited[j]=visited[i]
      vis[j]=1
      vis2[j]=1
      q.put(j)
    while not q.empty():
      nex = q.get()
      vis2[nex]=1
      visited[nex]=visited[i]
      visited[i].append(dic[nex])
      for j in route[nex]:
        if vis[j] == 0:
          vis[j]=1
          q.put(j)
  
  if i in visited[i]:
    ans += 1 
print(ans)
#print(visited)