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: Runtime Error

Solution code:
import sys

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.par[x]
        y = self.par[y]
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
p = [0] + [int(_) for _ in input().split()]
pair = [[int(_) for _ in input().split()] for _ in range(M)]
sys.setrecursionlimit(max(1000, N+1))
uf = UnionFind(N+1)
ans = 0

for i in pair:
    uf.union(i[0], i[1])

for i in range(1, N+1):
    if uf.find(i) == uf.find(p[i]):
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.par[x]
        y = self.par[y]
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
p = [0] + [int(_) for _ in input().split()]
pair = [[int(_) for _ in input().split()] for _ in range(M)]
uf = UnionFind(N+1)
ans = 0

for i in pair:
    uf.union(i[0], i[1])

for i in range(1, N+1):
    if uf.find(i) == uf.find(p[i]):
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
rank = [0] * N
parent = [i for i in range(N)]


def find(i):
    if parent[i] == i:
        return i
    else:
        parent[i] = find(parent[i])
        return parent[i]


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


def unite(x, y):
    x = parent[x]
    y = parent[y]
    if x == y:
        return

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


for i in range(M):
    x, y = map(int, input().split())
    unite(x - 1, y - 1)

num = 0
for i in range(N):
    num += same(i, P[i])

print(num)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
rank = [0] * N
parent = [i for i in range(N)]


def find(i):
    if parent[i] == i:
        return i
    else:
        parent[i] = find(parent[i])
        return parent[i]


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


def unite(x, y):
    x = parent[x]
    y = parent[y]

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


for i in range(M):
    x, y = map(int, input().split())
    unite(x - 1, y - 1)

num = 0
for i in range(N):
    num += same(i, P[i])

print(num)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
rank = [0] * N
parent = [i for i in range(N)]


def find(i):
    if parent[i] == i:
        return i
    else:
        parent[i] = find(parent[i])
        return parent[i]


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


def unite(x, y):
    x = parent[x]
    y = parent[y]

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


for i in range(M):
    x, y = map(int, input().split())
    unite(x - 1, y - 1)

rec = [[] for i in range(N)]
rec2 = [[] for i in range(N)]
for i in range(N):
    rec[parent[i]].append(P[i])
    rec2[parent[i]].append(i)

num = 0
for i in range(N):
    num += same(i, P[i])

print(num)

Submission status: Runtime Error

Solution code:
group_id = 0
groups = []

def solve(graphs, ps):
    global group_id, groups
    groups = [-1] * (len(ps) + 1)

    for key in range(1, len(ps) + 1):
        if key < len(graphs) and groups[key] == -1:
            group_id += 1
            dfs(graphs, key)

    ans = 0
    for key, value in enumerate(ps, 1):
        if key < len(groups) and value < len(groups) and groups[key] == groups[value]:
            ans += 1
    return ans

def dfs(graphs, key):
    if key >= len(groups):
        return

    global groups
    groups[key] = group_id

    for graph_key in graphs[key]:
        if graph_key < len(groups) and groups[graph_key] == -1:
            dfs(graphs, graph_key)

def main():
    n, m = map(int, input().split())
    ps = list(map(int, input().split()))

    # 隣接リスト作成 (0, n]
    graphs = [[] for i in range(n + 1)]
    for i in range(m):
        x, y = map(int, input().split())
        graphs[x].append(y)
        graphs[y].append(x)

    ans = solve(graphs, ps)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
group_id = 0
groups = []

def solve(graphs, ps):
    global group_id, groups
    groups = [-1] * (len(ps) + 1)

    for key in range(1, len(ps) + 1):
        if key < len(graphs) and groups[key] == -1:
            group_id += 1
            dfs(graphs, key)

    ans = 0
    for key, value in enumerate(ps, 1):
        if key < len(groups) and value < len(groups) and groups[key] == groups[value]:
            ans += 1
    return ans

def dfs(graphs, key):
    global groups
    groups[key] = group_id

    for graph_key in graphs[key]:
        if graph_key < len(graphs) and groups[graph_key] == -1:
            dfs(graphs, graph_key)

def main():
    n, m = map(int, input().split())
    ps = list(map(int, input().split()))

    # 隣接リスト作成 (0, n]
    graphs = [[] for i in range(n + 1)]
    for i in range(m):
        x, y = map(int, input().split())
        graphs[x].append(y)
        graphs[y].append(x)

    ans = solve(graphs, ps)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
group_id = 0
groups = []

def solve(graphs, ps):
    global group_id, groups
    groups = [-1] * (len(ps) + 1)

    for key in range(1, len(ps) + 1):
        if groups[key] == -1:
            group_id += 1
            dfs(graphs, key)

    ans = 0
    for key, value in enumerate(ps, 1):
        if groups[key] == groups[value]:
            ans += 1
    return ans

def dfs(graphs, key):
    if key >= len(graphs):
        return

    global groups
    groups[key] = group_id

    for graph_key in graphs[key]:
        if groups[graph_key] == -1:
            dfs(graphs, graph_key)

def main():
    n, m = map(int, input().split())
    ps = list(map(int, input().split()))

    # 隣接リスト作成 (0, n]
    graphs = [[] for i in range(n + 1)]
    for i in range(m):
        x, y = map(int, input().split())
        graphs[x].append(y)
        graphs[y].append(x)

    ans = solve(graphs, ps)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
group_id = 0
groups = []

def solve(graphs, ps):
    global group_id, groups
    groups = [-1] * (len(ps) + 1)

    # (0, n]
    for key in range(1, len(ps) + 1):
        if groups[key] == -1:
            group_id += 1
            groups[key] = group_id
            dfs(graphs, key)

    ans = 0
    for key, value in enumerate(ps, 1):
        if groups[key] == groups[value]:
            ans += 1
    return ans

def dfs(graphs, key):
    global groups

    for graph_key in graphs[key]:
        if groups[graph_key] == -1:
            groups[graph_key] = group_id
            dfs(graphs, graph_key)

def main():
    n, m = map(int, input().split())
    ps = list(map(int, input().split()))

    # (0, n]
    graphs = [[] for i in range(n + 1)]
    for i in range(m):
        x, y = map(int, input().split())
        graphs[x].append(y)
        graphs[y].append(x)

    ans = solve(graphs, ps)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, M = [int(_) for _ in input().split()]
P = [0] + [int(_) for _ in input().split()]
XY = sorted([sorted([int(_) for _ in input().split()]) for _ in range(M)],
            key=lambda xy: -xy[0] - N * xy[1])

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = min(UF[x], find(y))
    UF[UF[y]] = UF[x]


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


for x, y in XY:
    unite(x, y)

ans = 0
for i in range(1, N + 1):
    if same(i, P[i]):
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(_) for _ in input().split()]
P = [0] + [int(_) for _ in input().split()]
XY = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = min(find(x), find(y))
    UF[find(y)] = UF[x]


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


for x, y in XY:
    unite(x, y)

ans = 0
for i in range(1, N + 1):
    if same(i, P[i]):
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


def getList():
    return list(map(int, input().split()))

class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N+20)]

    def root(self, n):
        if self.par[n] == n:
            return n
        else:
            return self.root(self.par[n])

    def isgroup(self, a, b):
        if self.root(a) == self.root(b):
            return True
        else:
            return False

    def merge(self, m, n):
        rm = self.root(m)
        rn = self.root(n)
        if rm == rn:
            pass
        else:
            self.par[rn] = rm

N,M = getNM()
pos = getList()
uf = UnionFind(N)
for i in range(M):
    x, y = getNM()
    uf.merge(x,y)

ans = 0

for i, p in enumerate(pos):
    if uf.isgroup(i+1, p):
        #print(i+1, p)
        ans += 1
    else:
        pass

#roots = [uf.root(i) for i in range(N+1)]
print(ans)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


def getList():
    return list(map(int, input().split()))

class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N+2)]

    def root(self, n):
        if self.par[n] == n:
            return n
        else:
            return self.root(self.par[n])

    def isgroup(self, a, b):
        if self.root(a) == self.root(b):
            return True
        else:
            return False

    def merge(self, m, n):
        if self.isgroup(m,n):
            pass
        else:
            self.par[self.root(n)] = self.root(m)

N,M = getNM()
pos = getList()
uf = UnionFind(N)
for i in range(M):
    x, y = getNM()
    uf.merge(x,y)

ans = 0

for i, p in enumerate(pos):
    if uf.isgroup(i+1, p):
        #print(i+1, p)
        ans += 1
    else:
        pass

#roots = [uf.root(i) for i in range(N+1)]
print(ans)

Submission status: Runtime Error

Solution code:
debug = False

def find(i,par):
    if par[i]==i:
        return i
    else:
        return find(par[i],par)

def isSame(i,j,par):
    if find(i,par)==find(j,par):
        return True
    else:
        return False

def union(i,j,par):
    if isSame(i,j,par):
        return
    else:
        par[find(i,par)]=find(j,par)

def main():
    N, M = map(int,input().split(' '))
    p = list(map(int,input().split(' ')))
    par = []
    for i in range(N):
        par.append(i)

    for i in range(M):
        X, Y =map(int,input().split(' '))
        union(X-1,Y-1,par)
        if debug:
            print("union:",par)

    if debug:   
        print("p  :",p)
        print("par:",par)
    cnt=0
    for i in range(N):
        if find(p[i]-1,par) == find(par[i],par):
            if debug:
                print("i:",i)
            cnt +=1
    print(cnt)

if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
par = []
debug = False

def find(i):
    if par[i]==i:
        return i
    else:
        return find(par[i])

def isSame(i,j):
    if find(i)==find(j):
        return True
    else:
        return False

def union(i,j):
    if isSame(i,j):
        return
    else:
        par[find(i)]=find(j)

def main():
    N, M = map(int,input().split(' '))
    p = list(map(int,input().split(' ')))
    for i in range(N):
        par.append(i)

    for i in range(M):
        X, Y =map(int,input().split(' '))
        union(X-1,Y-1)
        if debug:
            print("union:",par)

    if debug:   
        print("p  :",p)
        print("par:",par)
    cnt=0
    for i in range(N):
        if find(p[i]-1) == find(par[i]):
            if debug:
                print("i:",i)
            cnt +=1
    print(cnt)

if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
par = []
debug = False

def find(i):
    if par[i]==i:
        return i
    else:
        return find(par[i])

def isSame(i,j):
    if find(i)==find(j):
        return True
    else:
        return False

def union(i,j):
    if isSame(i,j):
        return
    else:
        par[find(i)]=find(j)

def main():
    N, M = map(int,input().split(' '))
    p = list(map(int,input().split(' ')))
    for i in range(N):
        par.append(i)

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

    for i in range(M):
        union(XY[i][0]-1,XY[i][1]-1)
        if debug:
            print("union:",par)

    if debug:   
        print("p  :",p)
        print("par:",par)
    cnt=0
    for i in range(N):
        if find(p[i]-1) == find(par[i]):
            if debug:
                print("i:",i)
            cnt +=1
    print(cnt)

if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

def create_dict(N):
    d = {}
    key2rep = {}
    for i in range(N):
        d[i+1] = set([i+1])
        key2rep[i+1] = i+1
    return d, key2rep

def add_x2y(x, y, d, key2rep):
#    print(y)
    rep = key2rep[y]
    big_rep = key2rep[x]
    for old in d[big_rep]:
        d[rep].add(old)
        key2rep[old] = rep
    del d[big_rep]
#    print(d)

N, M = map(int,input().split(' '))
d, key2rep = create_dict(N)
p_list = list(map(int,input().split(' ')))

for line in sys.stdin:
    x,y = map(int, line.strip().split(' '))
    add_x2y(max(x,y), min(x,y), d, key2rep)

score = 0
for i in d:
    for x in d[i]:
        if p_list[x-1] in d[i]:
            score += 1
print(score)

Submission status: Runtime Error

Solution code:
import sys

def create_dict(N):
    d = {}
    for i in range(N):
        d[i+1] = set([i+1])
    return d

N, M = map(int,input().split(' '))
d = create_dict(N)
p_list = list(map(int,input().split(' ')))

x_list = []
y_list = []
for line in sys.stdin:
    x,y = map(int, line.strip().split(' '))
    d[min(x, y)].add(max(x,y))
    del d[max(x,y)]

score = 0
for i in d:
    for x in d[i]:
        if p_list[x-1] in d[i]:
            score += 1
print(score)

Submission status: Runtime Error

Solution code:
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const int MAXN = 120000;

int n, m;

vector<int> eds[MAXN];
int was[MAXN];
set<int> v1, v2;
int p[MAXN];

void dfs1(int v) {
	v1.insert(v);
	v2.insert(p[v]);
	was[v] = 1;
	for (int u: eds[v])
		if (!was[u])
			dfs1(u);
}

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		cin >> p[i], --p[i];
	}
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		eds[a].push_back(b);
		eds[b].push_back(a);
	}
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (was[i])
			continue;
		v1.clear();
		v2.clear();
		dfs1(i);
		for (int j: v1)
			if (v2.count(j))
				ans += 1;
	}
	cout << ans << "\n";
	return 0;
}

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

parents = [i for i in range(10 ** 5)]

def find(p):
    return p if parents[p] == p else find(parents[p])

def union(x, y):
    parents[find(y)] = find(x)

def main():
    n, m = map(int, input().split())
    pn = list(map(int, input().split()))
    for i in range(n):
        pn[i] -= 1
    xym = []
    for i in range(m):
        x1, y1 = map(int, input().split())
        xym.append((x1 - 1, y1 - 1))

    for j in range(m):
        x, y = xym[j]
        union(x, y)

    nodes = [[] for i in range(n)]
    for i in range(n):
        j = find(i)
        nodes[j].append(i)

    res = 0
    for j in range(n):
        iset = set(nodes[j])
        pset = set(pn[i] for i in nodes[j])
        cm = iset & pset
        res += len(cm)

    print(res)


main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

def find(parents, p):
    return p if parents[p] == p else find(parents, parents[p])

def union(parents, x, y):
    parents[find(parents, y)] = find(parents, x)

def main():
    n, m = map(int, input().split())
    pn = list(map(int, input().split()))
    for i in range(n):
        pn[i] -= 1
    xym = []
    for i in range(m):
        x1, y1 = map(int, input().split())
        xym.append((x1 - 1, y1 - 1))

    parents = [i for i in range(n)]
    for j in range(m):
        x, y = xym[j]
        union(parents, x, y)

    nodes = [[] for i in range(n)]
    for i in range(n):
        j = find(parents, i)
        nodes[j].append(i)

    res = 0
    for j in range(n):
        iset = set(nodes[j])
        pset = set(pn[i] for i in nodes[j])
        cm = iset & pset
        res += len(cm)

    print(res)


main()

Submission status: Runtime Error

Solution code:
class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x]) #xをxの根に直接つなぐ
            return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		else:
			st1 = self.table[s1]
			st2 = self.table[s2]
			if st1 > st2:
				self.table[s2] = s1
			elif st1 < st2:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

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

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return x

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		elif:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

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

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

Submission status: Runtime Error

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

x = []
for i in range(m):
    x.append(list(map(int, input().split(" "))))

a = [0 for i in range(n)]
kind = 1
k_list = []
for i in x:
    t = 0
    i[0] -= 1
    i[1] -= 1

    if a[i[0]] == 0:
        t += 1
    if a[i[1]] == 0:
        t += 1

    if t == 2:
        a[i[0]] = kind
        a[i[1]] = kind
        k_list.append(kind)
        kind += 1
    elif t == 1:
        if a[i[0]] == 0:
            a[i[0]] = a[i[1]]
        if a[i[1]] == 0:
            a[i[1]] = a[i[0]]
    elif t == 0:
        old = a[i[1]]
        new = a[i[0]]
        for j in range(n):
            if a[j] == old:
                a[j] = new
        k_list.pop(k_list.index(old))

result = 0
for i in k_list:
    temp1 = []
    temp2 = []
    for j in range(n):
        if a[j] == i:
            temp1.append(p[j] - 1)
            temp2.append(j)
    temp = temp1 + temp2
    result += len(temp) - len(set(temp))

for i in range(n):
    if a[i] == 0 and p[i] == i + 1:
        result += 1

print(result)

Submission status: Runtime Error

Solution code:
import numpy as np

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

A = np.identity(N, dtype=int)
for i in range(M):
    x_i, y_i = map(int, input().split())
    A[x_i-1][y_i-1] = 1
    A[y_i-1][x_i-1] = 1

B = A
for i in range(N + 1):
    B = np.dot(B, A)

for i in range(N):
    for j in range(N):
        if B[i][j] > 0:
            B[i][j] = j + 1


F = {tuple(C) for C in B}
G = [set(C) - {0} for C in F]

count = 0

for i in range(N):
    for C in G:
        if P[i] in C and i + 1 in C:
            count += 1

print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = list(map(int, input().split()))
p = list(map(int, input().split()))
x = []
y = []
for _ in range(M):
    xi, yi = list(map(int, input().split()))
    x.append(xi - 1)
    y.append(yi - 1)

def count(l):
    out = 0
    for i, v in enumerate(l):
        if i + 1 == v:
            out += 1
    return out

def swap(l, a, b):
    va = l[a]
    vb = l[b]
    l1 = l.copy()
    l1[a] = vb
    l1[b] = va
    return l1

depth = 0
max_count = count(p)
max_d = M**5
children = [p]
next_children = []
while depth <= max_d:
    for child in children:
        for i in range(M):
            pi = swap(child, x[i], y[i])
            ci = count(pi)
            if ci > max_count:
                max_count = ci
	    if not pi in next_children:
                next_children.append(pi)
    depth += 1
    children = next_children
    next_chldren = []
    if max_count == len(p):
        break

print(max_count)

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = list(map(int, input().split()))
p = list(map(int, input().split()))
x = []
y = []
for _ in range(M):
    xi, yi = list(map(int, input().split()))
    x.append(xi - 1)
    y.append(yi - 1)

def count(l):
    out = 0
    for i, v in enumerate(l):
        if i + 1 == v:
            out += 1
    return out

def swap(l, a, b):
    va = l[a]
    vb = l[b]
    l1 = l.copy()
    l1[a] = vb
    l1[b] = va
    return l1

depth = 0
max_count = count(p)
max_d = M**5
children = [p]
next_children = []
while depth <= max_d:
    for child in children:
        for i in range(M):
            pi = swap(child, x[i], y[i])
            ci = count(pi)
            if ci > max_count:
                max_count = ci
            next_children.append(pi)
    depth += 1
    children = next_children
    children = list(set(children))
    next_chldren = []
    if max_count == len(p):
        break

print(max_count)

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
p = list(map(int, input().split()))
x = []
y = []
for _ in range(M):
    xi, yi = list(map(int, input().split()))
    x.append(xi)
    y.append(yi)

def count(l):
    out = 0
    for i, v in enumerate(l):
        if i + 1 == v:
            out += 1
    return out

def swap(l, a, b):
    va = l[a]
    vb = l[b]
    l1 = l.copy()
    l1[a] = vb
    l1[b] = va
    return l1

depth = 0
max_count = count(p)
max_d = M**(N*np.log(N))
children =	[p]
next_children =	[]
while depth <= max_d:
    for child in children:
        for i in range(M):
	    pi = swap(child)
            ci = count(pi)
            if ci > max_count:
		max_count = ci
	    next_children.append(pi)
    depth += 1
    children = next_children
    next_chldren = []
    if max_count = len(p):
	break

print(max_count)

Submission status: Runtime Error

Solution code:
import numpy as np

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

A = np.identity(N, dtype=int)
for i in range(M):
    x_i, y_i = map(int, input().split())
    A[x_i-1][y_i-1] = 1
    A[y_i-1][x_i-1] = 1

B = A
for i in range(N + 1):
    B = np.dot(B, A)

for i in range(N):
    for j in range(N):
        if B[i][j] > 0:
            B[i][j] = j + 1


F = {tuple(C) for C in B}
G = [set(C) -{0} for C in F]

count = 0

for C in G:
        count += len(C & {P[j-1] for j in C})

print(count)

Submission status: Runtime Error

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

parent = list(range(N))
rank = [0] * N
key = [[i] for i in range(N)]
val = [[p-1] for p in P]

# union-find
def getRoot(x):
  p = parent[x]
  if p == x:
    return p
  ret = getRoot(p)
  parent[x] = ret
  return ret

def join(x, y):
  rx = getRoot(x)
  ry = getRoot(y)
  if rank[rx] < rank[ry]:
    parent[rx] = ry
    key[ry] += key[rx]
    val[ry] += val[rx]
  else:
    parent[y] = x
    key[rx] += key[ry]
    val[rx] += val[ry]
    if rank[rx] == rank[ry]:
      rank[rx] += 1

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

ans = 0
for i in range(N):
  if parent[i] == i:
    ans += len(set(key[i]).intersection(set(val[i])))

print(ans)

Submission status: Runtime Error

Solution code:
import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(100000)

n, m = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
g = [list() for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
v = [False] * n
s = set()
def dfs(i):
    if v[i]: return
    s.add(i)
    v[i] = True
    for k in g[i]: dfs(k)

c = 0
for i in range(n):
    if v[i]: continue
    s = set()
    dfs(i)
    for k in s:
        if p[k] in s: c += 1
print(c)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

n, m = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
g = [list() for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
v = [False] * n
s = set()
def dfs(i):
    if v[i]: return
    s.add(i)
    v[i] = True
    for k in g[i]: dfs(k)

c = 0
for i in range(n):
    if v[i]: continue
    s = set()
    dfs(i)
    for k in s:
        if p[k] in s: c += 1
print(c)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

n, m = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
g = [list() for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
v = [False] * n
s = set()
def dfs(i):
    if v[i]: return
    s.add(i)
    v[i] = True
    for k in g[i]: dfs(k)

c = 0
for i in range(n):
    if v[i]: continue
    s = set()
    dfs(i)
    t = {p[k] for k in s}
    c += len(s.intersection(t))
print(c)

Submission status: Runtime Error

Solution code:
ALPHA = "abcdefghijklmnopqrstuvwxyz"


def solve(pi, tuples):
    # ids = {i + 1: None for i in range(len(pi))}
    leave = set(range(1, len(pi) + 1))
    connects_sets_new = {0: set()}
    aaaaa = 0
    ids = [None] * len(pi)
    for x, y in tuples:
        if x in leave:
            leave.remove(x)
        if y in leave:
            leave.remove(y)
        x, y = x - 1, y - 1
        if ids[x] is not None:
            if ids[y] is not None:
                n_from = ids[y]
                n_to = ids[x]
                s = connects_sets_new[n_to]
                for n in connects_sets_new[n_from]:
                    ids[n] = n_to
                    s.add(n)
                del connects_sets_new[n_from]
            else:
                ids[y] = ids[x]
                connects_sets_new[ids[x]].add(y)
        else:
            if ids[y] is not None:
                ids[x] = ids[y]
                connects_sets_new[ids[y]].add(x)
            else:
                ids[x] = aaaaa
                ids[y] = aaaaa
                s = {x, y}
                connects_sets_new[aaaaa] = s
                aaaaa += 1

    # for n in range(len(pi)):
    #     if ids[n] not in connects_sets_new:
    #         connects_sets_new[ids[n]] = set()
    #     connects_sets_new[ids[n]].add(n)

    # leave = connects_sets_new[None] if None in connects_sets_new else []

    res = 0
    for l in leave:
        if l == pi[l - 1]:
            res += 1

    for s in connects_sets_new.values():
        indexies = set([pi[i]-1 for i in s])
        inter = indexies.intersection(s)
        res += len(inter)
    return res


def main():
    N, M = [int(a) for a in input().split()]
    pi = [int(a) for a in input().split()]
    tuples = [[int(a) for a in input().split()] for _ in range(M)]
    res = solve(pi, tuples)
    print(res)


if __name__ == '__main__':
    main()