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):
from collections import deque
 
def dfs(friends, x):
    visited = [0] * n
    d = deque([x])
    ans = []
    while d:
        num = d.pop()
        
        #print(num, '->',end='')
        
        if visited[num] == 1:
            #print('x')
            continue
        
        visited[num] = 1
        ans.append(num)
        
        for a in friends[num]:
            d.append(a)
        
    #print()
    return ans
        
if __name__ == "__main__":    
    n, m, k = map(int, input().split())
     
    friends = [[] for _ in range(n)]
    for i in range(m):
        x, y = map(lambda z: int(z) - 1, input().split())
        friends[x].append(y)
        friends[y].append(x)
         
    blocks = [[] for _ in range(n)]
    for i in range(k):
        x, y = map(lambda z: int(z) - 1, input().split())
        blocks[x].append(y)
        blocks[y].append(x)
        
    #print(friends)
    #print(blocks)
    
    for i in range(n):
        vec = dfs(friends, i)
        ans = len(vec)
        
        ans -= len(friends[i])
        
        for b in blocks[i]:
            if b in vec:
                ans -= 1
        
        ans -= 1
                
        print(ans, end=' ')

from collections import deque
 
def dfs(friends, x):
    visited = [0] * n
    d = deque([x])
    ans = []
    while d:
        num = d.pop()
        
        #print(num, '->',end='')
        
        if visited[num] == 1:
            #print('x')
            continue
        
        visited[num] = 1
        ans.append(num)
        
        for a in friends[num]:
            d.append(a)
        
    #print()
    return ans
        
if __name__ == "__main__":    
    n, m, k = map(int, input().split())
     
    friends = [[] for _ in range(n)]
    for i in range(m):
        x, y = map(lambda z: int(z) - 1, input().split())
        friends[x].append(y)
        friends[y].append(x)
         
    blocks = [[] for _ in range(n)]
    for i in range(k):
        x, y = map(lambda z: int(z) - 1, input().split())
        blocks[x].append(y)
        blocks[y].append(x)
        
    #print(friends)
    #print(blocks)
    
    for i in range(n):
        vec = dfs(friends, i)
        ans = len(vec)
        
        for f in friends[i]:
            if f in vec:
                ans -= 1
        
        for b in blocks[i]:
            if b in vec:
                ans -= 1
        
        ans -= 1
                
        print(ans, end=' ')

from collections import deque

def dfs(friend, group, number, s):
    d = deque([s])
    
    while d:
        num = d.pop()
        if group[num] != 0:
            continue
        
        group[num] = number
        
        for n in friend[num]:
            d.append(n)
    
    return group
    
def main():
    n, m, k = map(int, input().split())
    
    friend = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        friend[a].append(b)
        friend[b].append(a)
    
    block = [[] for _ in range(n)]
    for _ in range(k):
        a, b = map(lambda x: int(x) - 1, input().split())
        block[a].append(b)
        block[b].append(a)
    
    group = [0] * n
    number = 1
    for i in range(n):
        if group[i] != 0:
            continue
        
        group = dfs(friend, group, number, i)
        number += 1
        
    link = []
    for i in range(number + 1):
        link.append(group.count(i))
        
    for i in range(n):
        ans = 0
        ans += link[group[i]]
        ans -= len(friend)
        for b in block[i]:
            if group[i] == group[b]:
                ans -= 1
        
        print(ans, end=' ')
        
if __name__ == "__main__":
    main()

from collections import deque
 
def dfs(friends, x):
    visited = [0] * n
    d = deque([x])
    ans = []
    while d:
        num = d.pop()
        
        #print(num, '->',end='')
        
        if visited[num] == 1:
            #print('x')
            continue
        
        visited[num] = 1
        ans.append(num)
        
        for a in friends[num]:
            d.append(a)
        
    #print()
    return ans
        
if __name__ == "__main__":    
    n, m, k = map(int, input().split())
     
    friends = [[] for _ in range(n)]
    for i in range(m):
        x, y = map(lambda z: int(z) - 1, input().split())
        friends[x].append(y)
        friends[y].append(x)
         
    blocks = [[] for _ in range(n)]
    for i in range(k):
        x, y = map(lambda z: int(z) - 1, input().split())
        blocks[x].append(y)
        blocks[y].append(x)
        
    #print(friends)
    #print(blocks)
    
    label = [-1] * n
    vec_len = []
    num = 0
    for i in range(n):
        if label[i] != -1:
            continue
        
        vec = dfs(friends, i)
        vec_len.append(len(vec))
        for j in vec:
            label[j] = num
        
        num += 1
        
    for i in range(n):
        ans = 0
        ans += vec_len[label[i]]
        ans -= len(friends[i])
        
        for b in blocks[i]:
            if label[i] == label[b]:
                ans -= 1
            
        ans -= 1
        
        print(ans, end=' ')

import sys
sys.setrecursionlimit(10**5)

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n 
        self.size = [1] * 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 same(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] = self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
                
n, m, k = map(int, input().split())
friends = [[] for _ in range(n)]
blocks = [[] for _ in range(n)]

for i in range(m):
    x, y = map(lambda x: int(x) - 1, input().split())
    friends[x].append(y)
    friends[y].append(x)

for i in range(k):
    x, y = map(lambda x: int(x) - 1, input().split())
    blocks[x].append(y)
    blocks[y].append(x)

uf = UnionFind(n)
for i in range(n):
    for f in friends[i]:
        uf.union(i, f)


ans = [uf.size[uf.find(i)] - 1 for i in range(n)]

for i in range(n):
    ans[i] -= len(friends[i])

for i in range(n):
    for b in blocks[i]:
        if uf.same(i, b):
            ans[i] -= 1

print(*ans)


Verdicts: Time Limit Exceeded

Time Limit Exceeded

Wrong Answer

Time Limit Exceeded

Accepted