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):
n, m, k = map(int, input().split())

friend = [[] for _ in range(n)]
block = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
for _ in range(k):
    c, d = map(int, input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)

size = [0] * n
seen = [0] * n 
todo = [] 

#DFS
for i in range(n):
    if seen[i] == 0:
        element = [] 
        seen[i] = 1
        todo.append(i)
        element.append(i)
        while todo != []:
            for j in friend[todo[-1]]:
                if seen[j] == 0:
                    seen[j] = 1
                    todo.append(j)
                    element.append(j)
                    break
            else:
                del todo[-1]
        length = len(element)
        for j in element:
            block[j] = [k for k in block[j] if k in element]
            size[j] = length - len(friend[j]) - len(block[j]) - 1
        
    print(size[i])

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

friend = [[] for _ in range(n)]
block = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
for _ in range(k):
    c, d = map(int, input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)

ans = [0] * n #answer
seen = [0] * n 
todo = [] 

#DFS
for i in range(n):
    if seen[i] == 0:
        element = [] 
        seen[i] = 1
        todo.append(i)
        element.append(i)
        size = 0

        while todo != []:
            for j in friend[todo[-1]]:
                if seen[j] == 0:
                    seen[j] = 1
                    todo.append(j)
                    element.append(j)
                    size += 1
                    break
            else:
                del todo[-1]

        for j in element:
            bl = 0
            for k in block[j]:
                if k in element:
                    bl += 1

            #size = len(element) - 1
            ans[j] = size - len(friend[j]) - bl
        
    print(ans[i])

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

friend = [[] for _ in range(n)]
block = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
for _ in range(k):
    c, d = map(int, input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)

ans = [0] * n #answer
seen = [0] * n 
todo = [] 

#DFS
for i in range(n):
    if seen[i] == 0:
        element = [] 
        seen[i] = 1
        todo.append(i)
        element.append(i)
        size = 0

        while todo != []:
            for j in friend[todo[-1]]:
                if seen[j] == 0:
                    seen[j] = 1
                    todo.append(j)
                    element.append(j)
                    size += 1
                    break
            else:
                del todo[-1]

        for j in element:
            bl = 0
            for k in block[j]:
                if k in element:
                    bl += 1

            #size = len(element) - 1
            ans[j] = size - len(friend[j]) - bl
        
    print(ans[i])


class UnionFind():
    # parents
    
    
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # find(x)
    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # union(x, y)
    
    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

    # same(x, y)
    
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # size(x)
    
    def size(self, x):
        return -self.parents[self.find(x)]

import sys
def input():
    return sys.stdin.readline().strip()

n, m, k = map(int, input().split())
ans = [-1 for _ in range(n)]
uf = UnionFind(n)

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

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

for i in range(n):
    ans[i] += uf.size(i)

print(' '.join(map(str, ans)))

Verdicts: Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Accepted