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):
def main():
    
    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 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[x] += 1

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

        
        def getSize(self, x):
            return self.size[self.find(x)]

    N,M,K = map(int, input().split())
    
    
    uftree = UnionFind(N)
    count = [0] * N
    for i in range(M):
        A,B = map(lambda x:x-1, map(int, input().split()))
        uftree.union(A,B)
        count[A] += 1
        count[B] += 1
    for i in range(K):
        C,D = map(lambda x:x-1, map(int, input().split()))
        if uftree.same_check(C,D):
            count[C] += 1
            count[D] += 1
    ans = [0] * N
    for i in range(N):
        print(uftree.getSize(i))
        print(count[i])
        ans[i] = uftree.getSize(i) - 1 - count[i] 
    print(*ans)

main()



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 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[x] += 1

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

    
    def getSize(self, x):
        return self.size[self.find(x)]

def main():
    N,M,K = map(int, input().split())
    
    
    uftree = UnionFind(N)
    count = [0] * N
    for i in range(M):
        A,B = map(lambda x:x-1, map(int, input().split()))
        uftree.union(A,B)
        count[A] += 1
        count[B] += 1
    for i in range(K):
        C,D = map(lambda x:x-1, map(int, input().split()))
        if uftree.same_check(C,D):
            count[C] += 1
            count[D] += 1
    ans = [""] * N
    for i in range(N):
        print(uftree.getSize(i))
        print(count[i])
        ans[i] = str(uftree.getSize(i) - 1 - count[i]) 
    print(" ".join(ans))

main()



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 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[x] += 1

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

    
    def getSize(self, x):
        return self.size[self.find(x)]

def main():
    N,M,K = map(int, input().split())
    
    
    uftree = UnionFind(N)
    count = [0] * N
    for i in range(M):
        A,B = map(lambda x:x-1, map(int, input().split()))
        uftree.union(A,B)
        count[A] += 1
        count[B] += 1
    for i in range(K):
        C,D = map(lambda x:x-1, map(int, input().split()))
        if uftree.same_check(C,D):
            count[C] += 1
            count[D] += 1
    ans = [0] * N
    for i in range(N):
        print(uftree.getSize(i))
        print(count[i])
        ans[i] = uftree.getSize(i) - 1 - count[i] 
    print(*ans)

main()



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 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[x] += 1

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

    
    def getSize(self, x):
        return self.size[self.find(x)]

def main():
    N,M,K = map(int, input().split())
    
    
    uftree = UnionFind(N)
    count = [0] * N
    for i in range(M):
        A,B = map(lambda x:x-1, map(int, input().split()))
        uftree.union(A,B)
        count[A] += 1
        count[B] += 1
    for i in range(K):
        C,D = map(lambda x:x-1, map(int, input().split()))
        if uftree.same_check(C,D):
            count[C] += 1
            count[D] += 1
    ans = [""] * N
    for i in range(N):
        print(uftree.getSize(i))
        print(count[i])
        ans[i] = str(uftree.getSize(i) - 1 - count[i]) 
    print(*ans, sep=" ")

main()



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 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[x] += 1

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

    
    def getSize(self, x):
        return self.size[self.find(x)]

N,M,K = map(int, input().split())


uftree = UnionFind(N)
count = [0] * N
for i in range(M):
    A,B = map(lambda x:x-1, map(int, input().split()))
    uftree.union(A,B)
    count[A] += 1
    count[B] += 1
for i in range(K):
    C,D = map(lambda x:x-1, map(int, input().split()))
    if uftree.same_check(C,D):
        count[C] += 1
        count[D] += 1
ans = [0] * N
for i in range(N):
    print(uftree.getSize(i))
    print(count[i])
    ans[i] = uftree.getSize(i) - 1 - count[i] 

print(*ans)



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 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[x] += 1

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

    
    def getSize(self, x):
        return self.size[self.find(x)]

def main():
    N,M,K = map(int, input().split())
    
    
    uftree = UnionFind(N)
    count = [0] * N
    for i in range(M):
        A,B = map(lambda x:x-1, map(int, input().split()))
        uftree.union(A,B)
        count[A] += 1
        count[B] += 1
    for i in range(K):
        C,D = map(lambda x:x-1, map(int, input().split()))
        if uftree.same_check(C,D):
            count[C] += 1
            count[D] += 1
    ans = [""] * N
    for i in range(N):
        print(uftree.getSize(i))
        print(count[i])
        ans[i] = str(uftree.getSize(i) - 1 - count[i]) 
    print(*ans)

main()



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 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[x] += 1

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

    
    def getSize(self, x):
        return self.size[self.find(x)]

def main():
    N,M,K = map(int, input().split())
    
    
    uftree = UnionFind(N)
    count = [0] * N
    for i in range(M):
        A,B = map(lambda x:x-1, map(int, input().split()))
        uftree.union(A,B)
        count[A] += 1
        count[B] += 1
    for i in range(K):
        C,D = map(lambda x:x-1, map(int, input().split()))
        if uftree.same_check(C,D):
            count[C] += 1
            count[D] += 1
    ans = [0] * N
    for i in range(N):
        ans[i] = uftree.getSize(i) - 1 - count[i] 
    print(*ans)

main()


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted