Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

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

Sample Output 3

1 3 5 4 3 3 3 3 1 0



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


Sample output:
0 1 0 1

Submission status: Runtime Error

Solution code:
# import numpy as np
class UnionFind:
    def __init__(self, n):
        # self.parent = np.array([-1] * n)
        # self.size = np.array([1] * n)
        self.parent = [-1] * n
        self.size = [1] * n
    def find(self, x):
        if self.parent[x] == -1:
            return x
        else:
            a = self.find(self.parent[x])
            self.parent[x] = a
            return a
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.parent[x] = y
            self.size[y] += self.size[x]
    def get_size(self, x):
        return self.size[self.find(x)]
    def printout(self):
        print(self.parent)
        print(self.size)

N, M, K = map(int, input().split())
uf = UnionFind(N)

ab = [[int(i)-1 for i in input().split()] for j in range(M)]
cd = [[int(i)-1 for i in input().split()] for j in range(K)]

for a, b in ab:
    uf.union(a, b)

ans =[uf.get_size(i)-1 for i in range(N)]

# for a, b in ab:
#     ans[a] -= 1
#     ans[b] -= 1

# for c, d in cd:
#     if uf.find(c) == uf.find(d):
#         ans[c] -= 1
#         ans[d] -= 1

# print(*ans)

Submission status: Runtime Error

Solution code:
# import numpy as np
class UnionFind:
    def __init__(self, n):
        # self.parent = np.array([-1] * n)
        # self.size = np.array([1] * n)
        self.parent = [-1] * n
        self.size = [0] * n
    def find(self, x):
        if self.parent[x] == -1:
            return x
        else:
            a = self.find(self.parent[x])
            self.parent[x] = a
            return a
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.parent[x] = y
            self.size[y] += self.size[x]
    def get_size(self, x):
        return self.size[self.find(x)]
    def printout(self):
        print(self.parent)
        print(self.size)

N, M, K = map(int, input().split())
uf = UnionFind(N)

ab = [[int(i)-1 for i in input().split()] for j in range(M)]
cd = [[int(i)-1 for i in input().split()] for j in range(K)]

for a, b in ab:
    uf.union(a, b)

ans =[uf.get_size(i) for i in range(N)]

for a, b in ab:
    ans[a] -= 1
    ans[b] -= 1

for c, d in cd:
    if uf.find(c) == uf.find(d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Submission status: Runtime Error

Solution code:
# import numpy as np
class UnionFind:
    def __init__(self, n):
        # self.parent = np.array([-1] * n)
        # self.size = np.array([1] * n)
        self.parent = [-1] * n
        self.size = [1] * n
    def find(self, x):
        if self.parent[x] == -1:
            return x
        else:
            a = self.find(self.parent[x])
            self.parent[x] = a
            return a
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.parent[x] = y
            self.size[y] += self.size[x]
    def get_size(self, x):
        return self.size[self.find(x)]
    def printout(self):
        print(self.parent)
        print(self.size)

N, M, K = map(int, input().split())
uf = UnionFind(N)

ab = [[int(i)-1 for i in input().split()] for j in range(M)]
cd = [[int(i)-1 for i in input().split()] for j in range(K)]

for a, b in ab:
    uf.union(a, b)

ans =[uf.get_size(i) -1 for i in range(N)]

for a, b in ab:
    ans[a] -= 1
    ans[b] -= 1

for c, d in cd:
    if uf.find(c) == uf.find(d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Submission status: Runtime Error

Solution code:
import numpy as np
class UnionFind:
    def __init__(self, n):
        self.parent = np.array([-1] * n)
        self.size = np.array([1] * n)
        # self.parent = [-1] * n
        # self.size = [1] * n
    def find(self, x):
        if self.parent[x] == -1:
            return x
        else:
            a = self.find(self.parent[x])
            self.parent[x] = a
            return a
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.parent[x] = y
            self.size[y] += self.size[x]
    def get_size(self, x):
        return self.size[self.find(x)]
    def printout(self):
        print(self.parent)
        print(self.size)

N, M, K = map(int, input().split())
uf = UnionFind(N)

ab = [[int(i)-1 for i in input().split()] for j in range(M)]
cd = [[int(i)-1 for i in input().split()] for j in range(K)]

for a, b in ab:
    uf.union(a, b)

ans =[uf.get_size(i) -1 for i in range(N)]

for a, b in ab:
    ans[a] -= 1
    ans[b] -= 1

for c, d in cd:
    if uf.find(c) == uf.find(d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.size = [1] * n
    def find(self, x):
        if self.parent[x] == -1:
            return x
        else:
            a = self.find(self.parent[x])
            self.parent[x] = a
            return a
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.parent[x] = y
            self.size[y] += self.size[x]
    def get_size(self, x):
        return self.size[self.find(x)]

N, M, K = map(int, input().split())
uf = UnionFind(N)

ab = [[int(i)-1 for i in input().split()] for j in range(M)]
cd = [[int(i)-1 for i in input().split()] for j in range(K)]

for a, b in ab:
    uf.union(a, b)

ans =[uf.get_size(i) -1 for i in range(N)]

for a, b in ab:
    ans[a] -= 1
    ans[b] -= 1

for c, d in cd:
    if uf.find(c) == uf.find(d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Submission status: Runtime Error

Solution code:
a, b = [0] * m, [0] * m
c, d = [0] * k, [0] * k

direct =[[] for _ in range(n)]
uf = UnionFind(n)

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

for i in range(k):
    c[i], d[i] = map(int, input().split())
    c[i] -= 1
    d[i] -= 1
    if uf.same(c[i], d[i]):
        direct[c[i]].append(d[i])
        direct[d[i]].append(c[i])

ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - len(direct[i]) - 1

print(*ans)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
matrix = [['X'] * n for _ in range(n)]
friend_list = []

for i in range(m):
    friend = list(map(int, input().split()))
    matrix[friend[0] - 1][friend[1] - 1] = 'friend'
    matrix[friend[1] - 1][friend[0] - 1] = 'friend'
    if i == 0:
        friend_list.append(friend)
    else:
        flag = 0
        for j in range(len(friend_list)):
            if friend[0] in friend_list[j] or friend[1] in friend_list[j]:
                friend_list[j].extend(friend)
                flag = 1
                continue
        if flag == 0:
            friend_list.append(friend)

for i in range(len(friend_list)):
    for j in range(i + 1, len(friend_list)):
        inter = set(friend_list[i]) & set(friend_list[j])
        if len(inter) > 0:
            friend_list[i].extend(friend_list[j])
            friend_list.pop(j)
            j -= 1

for i in range(len(friend_list)):
    friend_list[i] = list(set(friend_list[i]))

for i in range(k):
    block = list(map(int, input().split()))
    matrix[block[0] - 1][block[1] - 1] = 'block'
    matrix[block[1] - 1][block[0] - 1] = 'block'

answer = []
for i in range(n):
    for j in range(len(friend_list)):
        if i + 1 in friend_list[j]:
             answer.append(len(friend_list[j]) - 1)
             for k in range(n):
                 if (matrix[i][k] == 'block' or matrix[i][k] == 'friend') and k + 1 in friend_list[j]:
                     answer[i] -= 1
             continue

print(' '.join(answer))

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
matrix = [['X'] * n for _ in range(n)]
friend_list = []

for i in range(m):
    friend = list(map(int, input().split()))
    matrix[friend[0] - 1][friend[1] - 1] = 'friend'
    matrix[friend[1] - 1][friend[0] - 1] = 'friend'
    if i == 0:
        friend_list.append(friend)
    else:
        flag = 0
        for j in range(len(friend_list)):
            if friend[0] in friend_list[j] or friend[1] in friend_list[j]:
                friend_list[j].extend(friend)
                flag = 1
                continue
        if flag == 0:
            friend_list.append(friend)

for i in range(len(friend_list)):
    for j in range(i + 1, len(friend_list)):
        inter = set(friend_list[i]) & set(friend_list[j])
        if len(inter) > 0:
            friend_list[i].extend(friend_list[j])
            friend_list.pop(j)
            j -= 1

for i in range(len(friend_list)):
    friend_list[i] = list(set(friend_list[i]))

for i in range(k):
    block = list(map(int, input().split()))
    matrix[block[0] - 1][block[1] - 1] = 'block'
    matrix[block[1] - 1][block[0] - 1] = 'block'

answer = []
for i in range(n):
    for j in range(len(friend_list)):
        if i + 1 in friend_list[j]:
             answer.append(len(friend_list[j]) - 1)
             for k in range(n):
                 if (matrix[i][k] == 'block' or matrix[i][k] == 'friend') and k + 1 in friend_list[j]:
                     answer[i] -= 1
             continue

print(answer)

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
par=[]
rank=[]
friends=[]
anti=[]
friend=[]
for i in range(n):
    par.append(i)
    rank.append(0)
    friends.append(set())
    anti.append(set())
    friends.append(set())
# this par & rank are initialized lists
def find_par(x):
    global par
    if par[x]==x:
        return x
    else:
        par[x]= find_par(par[x])
        return par[x]
def unite(x,y):
    x,y=find_par(x),find_par(y)
    global rank,par
    if x==y:return
    if rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1

for i in range(m):
    a,s=map(int,input().split())
    a-=1;s-=1
    unite(a,s)
    friend[a].add(s)
    friend[s].add(a)
for i in range(k):
    a,b=map(int,input().split())
    a-=1;b-=1
    anti[a].add(b)
    anti[b].add(a)
for i in range(n):
    find_par(i)
    friends[par[i]].add(i)
for i in range(n):
    print(len(friends[par[i]]-anti[i]-friend[i]-set([i])))

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
matrix = [['X'] * n for _ in range(n)]
friend_list = []

def search_friend(own, other, own_friend_list):
    for i in range(n):
        if (other != i and own != i and i not in own_friend_list and
            matrix[other][i] == 'friend' and matrix[own][i] != 'friend'):
            if matrix[own][i] != 'block':
                own_friend_list.append(i)
            search_friend(own, i, own_friend_list)
    return own_friend_list

for i in range(m):
    friend = list(map(int, input().split()))
    matrix[friend[0] - 1][friend[1] - 1] = 'friend'
    matrix[friend[1] - 1][friend[0] - 1] = 'friend'

for i in range(k):
    block = list(map(int, input().split()))
    matrix[block[0] - 1][block[1] - 1] = 'block'
    matrix[block[1] - 1][block[0] - 1] = 'block'

for i in range(n):
    own_friend_list = []
    for j in range(n):
        if i != j and matrix[i][j] == 'friend':
            search_friend(i, j, own_friend_list)
    friend_list.append(str(len(own_friend_list)))

print(' '.join(friend_list))

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
matrix = [['X'] * n for _ in range(n)]
friend_list = []

def search_friend(own, other, own_friend_list):
    for i in range(n):
        if (other != i and own != i and i not in own_friend_list and
            matrix[other][i] == 'friend' and matrix[own][i] != 'friend'):
            if matrix[own][i] != 'block':
                own_friend_list.append(i)
            search_friend(own, i, own_friend_list)

    return own_friend_list

for i in range(m):
    friend = list(map(int, input().split()))
    matrix[friend[0] - 1][friend[1] - 1] = 'friend'
    matrix[friend[1] - 1][friend[0] - 1] = 'friend'

for i in range(k):
    block = list(map(int, input().split()))
    matrix[block[0] - 1][block[1] - 1] = 'block'
    matrix[block[1] - 1][block[0] - 1] = 'block'

for i in range(n):
    own_friend_list = []
    for j in range(n):
        if i != j and matrix[i][j] == 'friend':
            search_friend(i, j, own_friend_list)
    friend_list.append(len(own_friend_list))

print(friend_list)

Submission status: Runtime Error

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

def main():
    n, m, k = map(int, input().split())
    friends = [set() for i in range(n)]
    blocks = [set() for i in range(n)]
    parents = [i for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        friends[a - 1].add(b - 1)
        friends[b - 1].add(a - 1)
        unite(a - 1, b - 1, parents)
    for i in range(k):
        c, d = map(int, input().split())
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)
    groups = [set() for i in range(n)]
    for i in range(n):
        p = find(i, parents)
        groups[p].add(i)
    res = []
    for i in range(n):
        p = find(i, parents)
        
        res.append(len(groups[p]) - len(friends[i]) - len(groups[p] & blocks[i]) - 1)
    print(" ".join([str(x) for x in res]))

def unite(x, y, parents):
    px = find(x, parents)
    py = find(y, parents)
    parents[py] = px

def find(x, parents):
    if parents[x] == x:
        return x
    fx = find(parents[x], parents)
    parents[x] = fx
    return fx

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def main():
    n, m, k = map(int, input().split())
    friends = [set() for i in range(n)]
    blocks = [set() for i in range(n)]
    parents = [i for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        friends[a - 1].add(b - 1)
        friends[b - 1].add(a - 1)
        unite(a - 1, b - 1, parents)
    for i in range(k):
        c, d = map(int, input().split())
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)
    groups = [set() for i in range(n)]
    for i in range(n):
        p = find(i, parents)
        groups[p].add(i)
    res = []
    for i in range(n):
        p = find(i, parents)
        res.append(len(groups[p] - friends[i] - blocks[i]) - 1)
    print(" ".join([str(x) for x in res]))

def unite(x, y, parents):
    px = find(x, parents)
    py = find(y, parents)
    parents[py] = px

def find(x, parents):
    if parents[x] == x:
        return x
    fx = find(parents[x], parents)
    parents[x] = fx
    return fx

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def main():
    n, m, k = map(int, input().split())
    friends = [set() for i in range(n)]
    blocks = [set() for i in range(n)]
    parents = [i for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        friends[a - 1].add(b - 1)
        friends[b - 1].add(a - 1)
        unite(a - 1, b - 1, parents)
    for i in range(k):
        c, d = map(int, input().split())
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)
    groups = {}
    for i in range(n):
        p = find(i, parents)
        if p not in groups:
            groups[p] = set()
        groups[p].add(i)
    res = []
    for i in range(n):
        p = find(i, parents)
        res.append(len(groups[p] - friends[i] - blocks[i]) - 1)
    print(" ".join([str(x) for x in res]))

def unite(x, y, parents):
    px = find(x, parents)
    py = find(y, parents)
    parents[py] = px

def find(x, parents):
    if parents[x] == x:
        return x
    fx = find(parents[x], parents)
    parents[x] = fx
    return fx
if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

S = [[i,100001,[]] for i in range(1,n+1)]
count = 0
for num in range(0, m+k):
    i1, i2 = map(int,input().split())
    a = S[i1-1][1]
    b = S[i2-1][1]
    a_1, a_2 = S[i1-1][1], []
    b_1, b_2 = S[i2-1][1], []
    t = min(a, b)
    
    if t == 100001 and num < m:
        a_1 = b_1 = count
        count += 1
    elif num < m:
        a_1 = b_1 = t
        if max(a, b) != 100001:
                xc = [x[1] for x in S]
                indexes = [j+1 for j, x in enumerate(xc) if x == max(a, b)]
                for f in range(len(indexes)):
                    S[indexes[f]-1][1:] = [t, S[indexes[f]-1][2]]
                    
    a_2 = S[i1-1][2]; b_2 = S[i2-1][2]
    a_2.append(i2); b_2.append(i1)
    
    S[i1-1][1:] = [a_1, a_2]; S[i2-1][1:] = [b_1, b_2]
friend = [0]*n
for i in range(0,count):
    xc = [x[1] for x in S]
    indexes = [j+1 for j, x in enumerate(xc) if x == i]
    for z in range(len(indexes)):

        S[indexes[z]-1][2].append(S[indexes[z]-1][0])
        V = S[indexes[z]-1][2]#+indexes[:z]
        result = (set(indexes) - set(V))
        S[indexes[z]-1][2].append(z)
        friend[indexes[z]-1] = str(len(result))
    #print(indexes)

print(' '.join(friend))

Submission status: Runtime Error

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


if __name__ == '__main__':
    n, m, k = list(map(int, input().split()))
    friends = UnionFind(n)
    ng_dict = {}
    for i in range(m):
        data = list(map(int, input().split()))
        friends.union(data[0] - 1, data[1] - 1)
        if (data[0] - 1) in ng_dict:
            ng_dict[data[0] - 1].append(data[1] - 1)
        else:
            ng_dict[data[0] - 1] = [(data[1] - 1)]
        if (data[1] - 1) in ng_dict:
            ng_dict[data[1] - 1].append(data[0] - 1)
        else:
            ng_dict[data[1] - 1] = [(data[0] - 1)]

    for i in range(k):
        data = list(map(int, input().split()))
        if friends.same(data[0] - 1, data[1] - 1):
            if (data[0] - 1) in ng_dict:
                ng_dict[data[0] - 1].append(data[1] - 1)
            else:
                ng_dict[data[0] - 1] = [(data[1] - 1)]
            if (data[1] - 1) in ng_dict:
                ng_dict[data[1] - 1].append(data[0] - 1)
            else:
                ng_dict[data[1] - 1] = [(data[0] - 1)]

    for i in range(n):
        print(friends.size(i) - len(ng_dict[i]) - 1, end=" ")

Submission status: Runtime Error

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

friends = [[] for _ in range(n+1)]
blocks = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    friends[a].append(b)
    friends[b].append(a)

for _ in range(k):
    c, d = map(int, input().split())
    blocks[c].append(d)
    blocks[d].append(c)

groups = []
nseen = {i for i in range(1, n+1)}
while len(nseen)>0:
    stack = [nseen.pop()]
    tmp = set()
    while len(stack)>0:
        node = stack.pop()
        tmp.add(node)
        nseen.remove(node)
        for c_node in friends[node]:
            if c_node not in nseen:
                continue
            stack.append(c_node)
    groups.append(tmp)

for i in range(1, n+1):
    for j in groups:
        if i in j:
            print(len(j - set(friends[i]) - set(blocks[i]))-1, end=' ')
            break

Submission status: Runtime Error

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

def get_shortest_shop(t, shops):
    shortest_i = 0
    shortest_t = shops[0][0]*t + shops[0][1]

    for i, l in enumerate(shops):
        shop_t = l[0]*t + l[1]
        if shortest_t > shop_t:
            shortest_t = shop_t
            shortest_i = i
    
    return shortest_i, shortest_t


n, t_limit = map(int, input().split())
shops = []
for _ in range(n):
    shops.append(list(map(int, input().split())))

t = 1
shop_limit = 0
while t_limit > t:
    shortest_i, shortest_t = get_shortest_shop(t, shops)
    if t_limit >= t + shortest_t:
        t = t + shortest_t + 1
        del shops[shortest_i]
        shop_limit += 1
        if len(shops) == 0:
            break
    else:
        break

print(shop_limit)

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = map(int,input().split())
friends = np.array([list(map(int,input().split())) for i in range(M)])
blocks = np.array([list(map(int,input().split())) for i in range(K)])

friends -= 1#0始まり
blocks -= 1

# union-find
PNUM = N
par = np.arange(PNUM)

def root(x):
    if x == par[x]:
        return x
    return root(par[x])

def unite(x, y):
    """xが親、yが子の木を作る"""
    px, py = root(x), root(y)
    par[py] = px

def flush():
    """全ての根を整理する"""
    for i, _ in enumerate(par):
        par[i] = root(i)

for x, y in friends:
    unite(x, y)
flush()

# 集計(cluster)
suggest = np.bincount(par)[par]

# 集計(friends)
for i, j in friends:
    suggest[i] -= 1
    suggest[j] -= 1

# 集計(blocks)
for i, j in blocks:
    if par[i] == par[j]:
        suggest[i] -= 1
        suggest[j] -= 1

# 自分を引く
suggest -= 1

# 出力
print(*suggest)

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = map(int,input().split())
friends = np.array([list(map(int,input().split())) for i in range(M)])
blocks = np.array([list(map(int,input().split())) for i in range(K)])

friends -= 1#0始まり
blocks -= 1

# 集計(blocks)
blist = [set() for _ in range(N)]
for i, j in blocks:
    blist[i] |= {j}
    blist[j] |= {i}

# 集計(friends)
flist = [set() for _ in range(N)]
for i, j in friends:
    flist[i] |= {j}
    flist[j] |= {i}
    
# union-find
PNUM = N
par = np.arange(PNUM)

def root(x):
    if x == par[x]:
        return x
    return root(par[x])

def unite(x, y):
    """xが親、yが子の木を作る"""
    px, py = root(x), root(y)
    par[py] = px

def flush():
    """全ての根を整理する"""
    for i, _ in enumerate(par):
        par[i] = root(i)

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

flush()

# 集計(cluster)
from collections import defaultdict
cdic = defaultdict(set)
for p, label in enumerate(par):
    cdic[label] |= {p}

# フレンド提案
res = [len(cdic[par[p]] - blist[p] - flist[p] - {p}) for p in range(N)]

# 出力
print(" ".join(list(map(str, res))))

Submission status: Runtime Error

Solution code:
class UF():
    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]
n,m,k=map(int,input().split())
uf=UF(n)
F=[set()for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    F[a-1].add(b-1)
    F[b-1].add(a-1)
    B=[0 for _ in range(n)]
for i in range(k):
    c,d=map(int,input().split())
    if uf.same(c-1,d-1):
        B[c-1]-=1
        B[d-1]-=1

A=[]
for i in range(n):
    A.append(uf.size(i)-len(F[i])+B[i]-1)
print(*A)

Submission status: Runtime Error

Solution code:
class UF():
    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,k=map(int,input().split())
uf=UF(n)
F=[set()for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    F[a-1].add(b-1)
    F[b-1].add(a-1)
    B=[0 for _ in range(n)]
for i in range(k):
    c,d=map(int,input().split())
    if uf.same(c-1,d-1):
        B[c-1]-=1
        B[d-1]-=1

A=[]
for i in range(n):
    A.append(uf.size(i)-1-len(F[i])+B[i])
print(*A)

Submission status: Runtime Error

Solution code:
class UF():
    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,k=map(int,input().split())
uf=UF(n)
F=[set()for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    F[a-1].add(b-1)
    F[b-1].add(a-1)
    B=[0]*n
for i in range(k):
    c,d=map(int,input().split())
    if uf.same(c-1,d-1):
        B[c-1]-=1
        B[d-1]-=1

A=[]
for i in range(n):
    A.append(uf.size(i)-1-len(F[i])+B[i])
print(*A)

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
c=[[0 for _ in range(N)]for __ in range(N)]
d=[0]*N
for ___ in range(M):
  a,b=int(input().split())
print(a)

Submission status: Runtime Error

Solution code:
def dfs(cur_node, candidates, visited, level, cnt):

  while len(candidates) > 0:
    node, level = candidates.pop(0)

    if visited[node]: continue
    visited[node] = True

    if level > 0: cnt += 1

    for n in adj_list[node][FRIEND]:
      if n in adj_list[cur_node][BLOCK]:
        candidates.append((n, 0))
      if visited[n] == False:
        candidates.append((n, level+1))

  return cnt

# -----------------------------------------

FRIEND, BLOCK = 0, 1

N, F, B = list(map(int, input().split()))
adj_list = defaultdict(dict)
for i in range(1, N+1):
  adj_list[i][0] = set()
  adj_list[i][1] = set()

for _ in range(F):
  u, v = list(map(int, input().split()))
  adj_list[u][FRIEND].add(v)
  adj_list[v][FRIEND].add(u)

for _ in range(B):
  u, v = list(map(int, input().split()))
  adj_list[u][BLOCK].add(v)
  adj_list[v][BLOCK].add(u)

ans = []

for i in range(1, N+1):
  visited = [False] * (N+1)
  visited[i] = True
  candidates = []
  for node in adj_list[i][FRIEND]:
    # node, level
    candidates.append((node, 0))

  cnt = 0
  cnt = dfs(i, candidates, visited, 0, 0)
  ans.append(cnt)

print(" ".join([str(i) for i in ans]))