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

n,m,k = map(int,input().split())
ans = [[0]*n for i in range(n)]

fre = [[] for i in range(n)]
blo = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    fre[a-1].append(b-1)
    fre[b-1].append(a-1)
for i in range(k):
    a,b = map(int,input().split())
    blo[a-1].append(b-1)
    blo[b-1].append(a-1)

group = [-1]*n
def check():
    
    count = 1
    for i in range(n):
        if group[i] == -1:
            dfs(i,count)
            count += 1
    return group

def dfs(i,count):
    q = deque([])
    q.append(i)
    while q:
        bef = q.pop()

        for nex in fre[bef]:
            if group[nex] == -1:
                group[nex] = count
                q.append(nex)
    
check()
for i in range(n):
    if group[i] == -1:
        print(0,end=" ")
    else:
        num = group.count(group[i])
        num -= len(fre[i])
        for j in blo[i]:
            if group[j] == group[i]:
                num -= 1
        print(num-1,end=" ")






class Unionfind:

    def __init__(self,n):
        self.uf = [-1]*n

    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[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 False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True

    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

n,m,k = map(int,input().split())
un = Unionfind(n)
fre = [1]*n
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    un.union(a,b)
    fre[a] += 1

ans = [un.size(i)-fre[i] for i in range(n)]

for i in range(k):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    if un.same(a,b):
        ans[a] -= 1
        ans[b] -= 1
print(*ans)
    

class Unionfind:

    def __init__(self,n):
        self.uf = [-1]*n

    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[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 False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True

    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

n,m,k = map(int,input().split())
un = Unionfind(n)
fre = [1]*n
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    un.union(a,b)
    fre[a] += 1
    fre[b] += 1

ans = [un.size(i)-fre[i] for i in range(n)]

for i in range(k):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    if un.same(a,b):
        ans[a] -= 1
        ans[b] -= 1
print(*ans)
    

Verdicts: Time Limit Exceeded

Wrong Answer

Accepted