Problem: 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?

Submission attempts (in order):
import sys
input = sys.stdin.buffer.readline

class UnionFind():
    
    def __init__(self, n):
        self.n = n
        self.parent = [-1]*(n+1)    
        self.rank   = [0]*(n+1)     

    def root(self, x):
        
        if self.parent[x] < 0:      
            return x
        else:
            self.parent[x] = self.root(self.parent[x])  
            return self.parent[x]
            
    def unite(self, x, y):
        
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return 0
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def isSame(self, x, y):
        
        return self.root(x) == self.root(y) or x==y

N, M, K = map(int, input().split())
friend = [[0]*N for _ in range(N)]
block = [[0]*N for _ in range(N)]
uf = UnionFind(N)
for i in range(M):
    A, B = map(int, input().split())
    friend[A-1][B-1] = 1
    friend[B-1][A-1] = 1
    uf.unite(A-1, B-1)
for j in range(K):
    C, D = map(int, input().split())
    block[C-1][D-1] = 1
    block[D-1][C-1] = 1

for i in range(N):
    ans = 0
    for j in range(N):
        if i == j:
            continue
        elif uf.isSame(i,j) and friend[i][j] == 0 and block[i][j] == 0:
            ans += 1
    print(ans, end= ' ')


import sys

def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    
    def __init__(self, n):
        self.n = n
        self.parent = [-1]*(n+1)    
        self.rank   = [0]*(n+1)     

    def root(self, x):
        
        if self.parent[x] < 0:      
            return x
        else:
            self.parent[x] = self.root(self.parent[x])  
            return self.parent[x]
            
    def unite(self, x, y):
        
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return 0
        elif self.rank[x] > self.rank[y]:
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def isSame(self, x, y):
        
        return self.root(x) == self.root(y) or x==y
    
    def size(self, x):
        
        return -self.parent[self.root(x)]


N, M, K = map(int, input().split())
uf = UnionFind(N)
friends = [[] for _ in range(N)]
blocks = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1; B -= 1
    uf.unite(A, B)
    friends[A].append(B)
    friends[B].append(A)
for i in range(K):
    C, D = map(int, input().split())
    C -= 1; D -= 1
    blocks[C].append(D)
    blocks[D].append(C)

ans = [0] * N
for i in range(N):
    ans[i] = uf.size(i) - 1   
    ans[i] -= len(friends[i]) 
    block_num = 0
    for j in blocks[i]:
        if uf.isSame(i,j):
            block_num += 1
    ans[i] -= block_num

print(*ans)


Verdicts: Time Limit Exceeded

Accepted