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
from io import StringIO
import unittest

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

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

def resolve():
    int1 = lambda x: int(x) - 1
    readline=sys.stdin.readline

    n,m,k=map(int, readline().strip().split())

    uf = UnionFind(n)

    exc=[0]*n

    for i in range(m):
        a,b=map(int1, readline().strip().split())
        uf.Unite(a,b)
        exc[a]+=1
        exc[b]+=1
    
    for i in range(k):
        a,b=map(int1, readline().strip().split())
        if uf.isSameGroup(a,b):
            exc[a]+=1
            exc[b]+=1
    
    rescnt=[]

    for i in range(n):
        ri=uf.Count(i)-1-exc[i]
        rescnt.append(str(ri))
    
    print(" ".join(rescnt))



import sys
from io import StringIO
import unittest

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

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

def resolve():
    n,m,k=map(int, sys.stdin.readline().strip().split())
    #list(map(int,input().strip().split()))

    uf = UnionFind(n)

    res=[[] for i in range(n)]
    frd=[0 for i in range(n)]
    blk=[0 for i in range(n)]

    for i in range(m):
        #a,b=list(map(int,input().strip().split()))
        a,b=map(int, sys.stdin.readline().strip().split())
        a-=1
        b-=1
        uf.Unite(a,b)
        frd[a]+=1
        frd[b]+=1
    
    for i in range(k):
        #a,b=list(map(int,input().strip().split()))
        a,b=map(int, sys.stdin.readline().strip().split())
        a-=1
        b-=1
        if uf.isSameGroup(a,b):
            blk[a]+=1
            blk[b]+=1
    
    rescnt=[]

    for i in range(n):
        ri=uf.Count(i)-1-blk[i]-frd[i]
        rescnt.append(str(ri))
        
    
    print(" ".join(rescnt))



import sys
from io import StringIO
import unittest

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

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

def resolve():
    int1 = lambda x: int(x) - 1
    readline=sys.stdin.readline

    n,m,k=map(int, readline().strip().split())

    uf = UnionFind(n)

    exc=[0]*n

    for i in range(m):
        a,b=map(int1, readline().strip().split())
        uf.Unite(a,b)
        exc[a]+=1
        exc[b]+=1
    
    for i in range(k):
        a,b=map(int1, readline().strip().split())
        if uf.isSameGroup(a,b):
            exc[a]+=1
            exc[b]+=1
    
    rescnt=[]

    for i in range(n):
        ri=uf.Count(i)-1-exc[i]
        rescnt.append(str(ri))
    
    print(" ".join(rescnt))

resolve()

Verdicts: Wrong Answer

Wrong Answer

Accepted