Problem:
 Score : 400 points    Problem Statement 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?      Constraints  All values in input are integers.  2 ≤ N ≤ 10^5  0 \leq M \leq 10^5  0 \leq K \leq 10^5  1 \leq A_i, B_i \leq N  A_i \neq B_i  1 \leq C_i, D_i \leq N  C_i \neq D_i  (A_i, B_i) \neq (A_j, B_j) (i \neq j)  (A_i, B_i) \neq (B_j, A_j)  (C_i, D_i) \neq (C_j, D_j) (i \neq j)  (C_i, D_i) \neq (D_j, C_j)  (A_i, B_i) \neq (C_j, D_j)  (A_i, B_i) \neq (D_j, C_j)         Input Input is given from Standard Input in the following format:  N  M  K  A_1  B_1  \vdots  A_M  B_M  C_1  D_1  \vdots  C_K  D_K       Output Print the answers in order, with space in between.        Sample Input 1 4 4 1
2 1
1 3
3 2
3 4
4 1      Sample Output 1 0 1 0 1  There is a friendship between User 2 and 3 , and between 3 and 4 . Also, there is no friendship or blockship between User 2 and 4 . Thus, User 4 is a friend candidate for User 2 .  However, neither User 1 or 3 is a friend candidate for User 2 , so User 2 has one friend candidate.       Sample Input 2 5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5      Sample Output 2 0 0 0 0 0  Everyone is a friend of everyone else and has no friend candidate.       Sample Input 3 10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1      Sample Output 3 1 3 5 4 3 3 3 3 1 0

Solution (Python):
class Tree:
    def __init__(self, v: int):
        self.value = v
        self.size = 1
        self.depth = 1
        self.parent = None
        self.friends = set()
        self.blocked = 0

    def get_root(self):
        t = self
        while(t.parent != None):
            t = t.parent
        return t

    def merge(self, t):
        p, c = (self, t) if self.depth > t.depth else (t, self)
        c.parent = p
        p.depth = max(p.size, c.size + 1)
        p.size += c.size

def main():
    n, m, k = [int(s) for s in input().split()]
    forest = [Tree(i+1) for i in range(n)]

    for i in range(m):
        a, b = [int(s) for s in input().split()]
        ta, tb = forest[a-1], forest[b-1]
        ta.friends.add(b)
        tb.friends.add(a)
        ra = ta.get_root()
        rb = tb.get_root()
        if ra != rb:
            ra.merge(rb)

    roots = [t.get_root() for t in forest]
    for i in range(k):
        c, d = [int(s) for s in input().split()]
        tc, td = forest[c-1], forest[d-1]
        rc = roots[c-1]
        rd = roots[d-1]
        if rc == rd:
            tc.blocked +=1
            td.blocked +=1

    cands = []
    for t in forest:
        root = roots[t.value - 1]
        cand = root.size - len(t.friends) - t.blocked - 1
        cands.append(str(cand))
    print(" ".join(cands))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())


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

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

    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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


uf = UnionFind(N)

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

out = []
for x in range(N):
    out.append(uf.size(x)-1)
    

for x in ab:
    out[x[0] - 1] -= 1
    out[x[1] - 1] -= 1

cd = []
for _ in range(K):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        out[c - 1] -= 1
        out[d - 1] -= 1
print(" ".join(map(str, out)))

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    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
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n, frnd, blck = map(int, input().split())
    blst = [set() for i in range(n)]
    flst = [set() for i in range(n)]
    uf = UnionFind(n)
    for _ in range(frnd):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        flst[a].add(b)
        flst[b].add(a)
        uf.union(a, b)
    for _ in range(blck):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        blst[c].add(d)
        blst[d].add(c)
    for i in range(n):
        ans = uf.size(i) - len(flst[i]) - 1
        for v in blst[i]:
            if uf.same(i, v):
                ans -= 1
        print(ans, end="")
        if i < n:
            print(" ", end="")

if __name__ == "__main__":
    main()

Solution (Python):
class UnionFind:

    def __init__(self, n):
        self.p, self.d = [-1] * n, [0] * n

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

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

    def unite(self, x, y):
        if self.isSame(x, y):
            return
        x, y = self.find(x), self.find(y)

        if self.d[x] > self.d[y]:
            self.p[x] += self.p[y]
            self.p[y] = x
        else:
            self.p[y] += self.p[x]
            self.p[x] = y
            if self.d[x] == self.d[y]:
                self.d[y] += 1

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


N, M, K = map(int, input().split())
Frd, Blk = {i: [] for i in range(N)}, {i: [] for i in range(N)}

uni = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    uni.unite(A - 1, B - 1)
    Frd[A - 1].append(B - 1)
    Frd[B - 1].append(A - 1)
for _ in range(K):
    C, D = map(int, input().split())
    Blk[C - 1].append(D - 1)
    Blk[D - 1].append(C - 1)

ans = []
for i in range(N):
    nBlk = sum([1 for b in Blk[i] if uni.isSame(i, b)])
    ans.append(str(uni.size(i) - 1 - len(Frd[i]) - nBlk))
print(' '.join(ans))

Solution (Python):
class UnionFind:
    def __init__(self,n):
        self.d = []
        for i in range(n):
            self.d.append(-1)
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            y, x = x, y
        self.d[x] += self.d[y]
        self.d[y] = x
        return True
    def same(self, x, y):
        return self.find(x) == self.find(y)

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

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

dame = [set() for _ in range(n)]
uf = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.unite(a, b)
    dame[a].add(b)
    dame[b].add(a)

for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if not uf.same(c, d):
        continue
    dame[c].add(d)
    dame[d].add(c)

for i in range(n):
    ans = uf.size(i) - 1
    ans -= len(dame[i])
    print(ans, end=" ")
print()

Solution (Python):
class UnionFind:
    def __init__(self,n):
        self.d = []
        for i in range(n):
            self.d.append(-1)
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            y, x = x, y
        self.d[x] += self.d[y]
        self.d[y] = x
        return True
    def same(self, x, y):
        return self.find(x) == self.find(y)

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

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

dame = [set() for _ in range(n)]
uf = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.unite(a, b)
    dame[a].add(b)
    dame[b].add(a)

for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if not uf.same(c, d):
        continue
    dame[c].add(d)
    dame[d].add(c)

for i in range(n):
    ans = uf.size(i) - 1
    ans -= len(dame[i])
    print(ans, end=" ")
print()

Solution (Python):
n, m, k = map(int, input().split())
par = [-1 for _ in range(n)]

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])  
        return par[x]

def same(x, y):
    return find(x) == find(y)

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    
    
    if par[x] < par[y]:
        par[x] += par[y]
        par[y] = x
    else:
        par[y] += par[x]
        par[x] = y
    return True

friends_num = [0] * 100005
for _ in range(m):
    num_from, num_to = map(int, input().split())
    num_from -= 1
    num_to -= 1
    friends_num[num_from] += 1
    friends_num[num_to] += 1
    unite(num_from, num_to)

blocks = [[] * n for i in range(n)]
for _ in range(k):
    num_from, num_to = map(int, input().split())
    num_from -= 1
    num_to -= 1
    blocks[num_from].append(num_to)
    blocks[num_to].append(num_from)

ans_list = []
for i in range(n):
    ans = -par[find(i)] - friends_num[i] - 1
    for b in blocks[i]:
        if same(i, b):
            ans -= 1
    ans_list.append(ans)

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

Solution (Python):



class UF:
    
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) 
        self.rnks = [0] * (n+1)

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


    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        
        if self.rnks[a_par] < self.rnks[b_par]: 
            a_par,b_par = b_par,a_par
        if self.rnks[a_par] == self.rnks[b_par]:
            self.rnks[a_par] += 1


        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def size(self,n):
        par = self.find(n)
        return abs(self.parents[par])

    def is_same(self,a,b):
        return self.find(a) == self.find(b)



def main():
    n,m,k = map(int,input().split())
    uf = UF(n)
    block_lst = [0 for _ in range(n+1)]
    friend_lst = [0 for _ in range(n+1)]
    
    for i in range(m):
        a,b = map(int,input().split())
        friend_lst[a] += 1
        friend_lst[b] += 1
        uf.union(a,b)
    

    
    for i in range(k):
        c,d = map(int,input().split())
        if uf.is_same(c,d):
            block_lst[c] += 1
            block_lst[d] += 1
    
    
    answer = []

    for i in range(1,n+1):
        f_o_f = uf.size(i)
        answer.append(f_o_f - friend_lst[i] - block_lst[i] - 1)


    print(" ".join(map(str,answer)))






if __name__ == '__main__':
    main()

Solution (Python):



class UF:
    
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) 
        self.rnks = [0] * (n+1)

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


    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        
        
        
        
        
        if self.size(a_par) < self.size(b_par): 
            a_par,b_par = b_par,a_par
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def size(self,n):
        par = self.find(n)
        return abs(self.parents[par])

    def is_same(self,a,b):
        return self.find(a) == self.find(b)



def main():
    n,m,k = map(int,input().split())
    uf = UF(n)
    block_lst = [0 for _ in range(n+1)]
    friend_lst = [0 for _ in range(n+1)]
    
    for i in range(m):
        a,b = map(int,input().split())
        friend_lst[a] += 1
        friend_lst[b] += 1
        uf.union(a,b)
    

    
    for i in range(k):
        c,d = map(int,input().split())
        if uf.is_same(c,d):
            block_lst[c] += 1
            block_lst[d] += 1
    
    
    answer = []

    for i in range(1,n+1):
        f_o_f = uf.size(i)
        answer.append(f_o_f - friend_lst[i] - block_lst[i] - 1)


    print(" ".join(map(str,answer)))






if __name__ == '__main__':
    main()

Solution (Python):



class UF:
    
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) 
        self.rnks = [0] * (n+1)

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

    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        
        
        
        
        
        if self.size(a_par) < self.size(b_par): 
            a_par,b_par = b_par,a_par
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def size(self,n):
        par = self.find(n)
        return abs(self.parents[par])

    def is_same(self,a,b):
        return self.find(a) == self.find(b)



def main():
    n,m,k = map(int,input().split())
    uf = UF(n)
    block_lst = [0 for _ in range(n+1)]
    friend_lst = [0 for _ in range(n+1)]
    
    for i in range(m):
        a,b = map(int,input().split())
        friend_lst[a] += 1
        friend_lst[b] += 1
        uf.union(a,b)
    

    
    for i in range(k):
        c,d = map(int,input().split())
        if uf.is_same(c,d):
            block_lst[c] += 1
            block_lst[d] += 1
    
    
    answer = []

    for i in range(1,n+1):
        f_o_f = uf.size(i)
        answer.append(f_o_f - friend_lst[i] - block_lst[i] - 1)


    print(" ".join(map(str,answer)))






if __name__ == '__main__':
    main()

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

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

    
    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

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

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

    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    
    def group_count(self):
        return len(self.roots())

    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m, k = map(int,input().split())
ab = []
cd = []


frineds = [0] * n

block = [0] * n

for i in range(m):
    ab.append(list(map(int,input().split())))
    frineds[ab[i][0]-1] += 1
    frineds[ab[i][1]-1] += 1


uf = UnionFind(n)

for _ab in ab:
    uf.union(_ab[0]-1, _ab[1]-1)

for i in range(k):
    cd.append(list(map(int,input().split())))
    
    
    if uf.same(cd[i][0]-1, cd[i][1]-1):
        block[cd[i][0]-1] += 1
        block[cd[i][1]-1] += 1

for i in range(n):
    ans = uf.size(i) - 1 - frineds[i] - block[i]
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
class UnionFind:
    def __init__(self,N):
        self.parent=[i for i in range(N)]
        self.rank=[0]*N
    def root(self,a):
        if self.parent[a]==a:
            return a
        else:
            self.parent[a]=self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a)==self.root(b)
    def unite(self,a,b):
        ra=self.root(a)
        rb=self.root(b)
        if ra==rb:
            return
        if self.rank[ra]<self.rank[rb]:
            self.parent[ra]=rb
        else:
            self.parent[rb]=ra
            if self.rank[ra]==self.rank[rb]:
                self.rank[ra]+=1
N,M,K=map(int,input().split())
uf=UnionFind(N)
lfriend=[0 for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    uf.unite(a-1,b-1)
    lfriend[a-1]+=1
    lfriend[b-1]+=1
lnfam=[0 for i in range(N)]
for i in range(N):
    rt=uf.root(i)
    lnfam[rt]+=1
lnblock=[0 for i in range(N)]
for i in range(K):
    c,d=map(int,input().split())
    if uf.root(c-1)==uf.root(d-1):
        lnblock[c-1]+=1
        lnblock[d-1]+=1
for i in range(N):
    print(lnfam[uf.root(i)]-lfriend[i]-lnblock[i]-1,end=" ")
print()

Solution (Python):
import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
parent=list(range(n))
rank=[0]*n
def root(x):
	if x!=parent[x]:
		x=root(parent[x])
	return x
def same(x,y):
	return root(x)==root(y)
def unite(x,y):
	rx=root(x)
	ry=root(y)
	if rank[rx]<rank[ry]:
		parent[rx]=ry
	else:
		parent[ry]=rx
		if rank[rx]==rank[ry]:
			rank[rx]+=1
f_b=[0]*n
for i in range(m):
	a,b=map(int,input().split())
	unite(a-1,b-1)
	f_b[a-1]+=1
	f_b[b-1]+=1
for j in range(k):
	c,d=map(int,input().split())
	if root(c-1)==root(d-1):
		f_b[c-1]+=1
		f_b[d-1]+=1
p=[0]*n
ans=[]
for i in range(n):
	p[root(i)-1]+=1
for i in range(n):
	r=p[root(i)-1]-f_b[i]-1
	ans.append(r)
print(*ans)

Solution (Python):
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq


def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()


class union_find:
    def __init__(self, n):
        self.N = n
        self._parent = [i for i in range(self.N)]
        self._mem = [1] * self.N
        self.compo = self.N

    def parent(self, a):
        if self._parent[a] == a:
            return a
        self._parent[a] = self.parent(self._parent[a])
        return self._parent[a]

    def united(self,a, b):
        return self.parent(a) == self.parent(b)
    
    def unite(self,a, b):
        a = self.parent(a)
        b = self.parent(b)
        if(a == b): return False
        if self._mem[a] > self._mem[b]: a, b = b, a
        self._parent[a] = b
        self._mem[b] += self._mem[a]
        self.compo -= 1
        return True
    
    def is_root(self,a):
        return a == self._parent[a]
    def mem_cnt(self,a):
        return self._mem[self.parent(a)]
    def dump(self):
        print(self._parent)
    

def main():
    N, M, K = rip()
    A = [0] * M
    B = [0] * M
    for i in range(M):
        A[i], B[i] = rip()
    C = [0] * K
    D = [0] * K
    for i in range(K):
        C[i], D[i] = rip()

    uf = union_find(N)
    for i in range(M):
        uf.unite(A[i] - 1, B[i] - 1)

    ans = [0] * N
    for i in range(N):
        ans[i] = uf.mem_cnt(i) - 1
    for i in range(K):
        if uf.united(C[i] - 1, D[i] - 1):
            ans[C[i] - 1] -= 1
            ans[D[i] - 1] -= 1
    for i in range(M):
        ans[A[i] - 1] -= 1
        ans[B[i] - 1] -= 1

    print(" ".join([str(n) for n in ans]))

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N,M,K = map(int,input().split())
    friend = [[] 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)
        
    brock = [[] for _ in range(N)]
    for _ in range(K):
        c,d = map(int,input().split())
        brock[c-1].append(d-1)
        brock[d-1].append(c-1)
        
    parent = [-1 for _ in range(N)]
    group = [0 for _ in range(N)]
    
    for i in range(N):
        put = []
        if parent[i] == -1:
            q = deque([i])
            parent[i] = i
            while q:
                now = q.pop()
                put.append(now)
                for fol in friend[now]:
                    if parent[fol] == -1:
                        parent[fol] = i
                        q.append(fol)
            l = len(put)
            for num in put:
                group[num] = l-1
                
        else:
            continue

    for i in range(N):
        group[i] -= len(friend[i])
        for dis in brock[i]:
            if parent[i] == parent[dis]:
                group[i] -= 1
    
    print(*group)
    
if __name__ == "__main__":
    main()

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

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

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

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

    def member(self,x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.root) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_member(self):
        return {r:self.member(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{}: {}".format(r,self.member(r)) for r in self.roots())

def main():
    N,M,K = map(int,input().split())
    adj = [[] for _ in range(N)]
    ans = [None]*N
    uf = UnionFind(N)
    for i in range(M+K):
        a,b = map(lambda x : int(x)-1,input().split())
        if i < M:
            uf.unite(a,b)
            adj[a].append(b)
            adj[b].append(a)
        elif uf.same(a,b):
            adj[a].append(b)
            adj[b].append(a)
    for i in range(N):
        ans[i] = uf.size(i) - len(adj[i]) - 1
    print(*ans,sep=" ")


if __name__ == '__main__':
    main()

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

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

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

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

    def member(self,x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.root) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_member(self):
        return {r:self.member(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{}: {}".format(r,self.member(r)) for r in self.roots())

def main():
    N,M,K = map(int,input().split())
    adj = [[] for _ in range(N)]
    ans = [None]*N
    uf = UnionFind(N)
    for i in range(M+K):
        a,b = map(int,input().split())
        if i < M:
            uf.unite(a-1,b-1)
            adj[a-1].append(b-1)
            adj[b-1].append(a-1)
        elif uf.same(a-1,b-1):
            adj[a-1].append(b-1)
            adj[b-1].append(a-1)
    for i in range(N):
        ans[i] = uf.size(i) - len(adj[i]) - 1
    print(*ans,sep=" ")


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict


class UnionFind:
    def __init__(self, n=0):
        self.d = {i: -1 for i in range(n)}

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if (x == y):
            return False
        if (self.d[x] > self.d[y]):
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

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

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


N, M, K = map(int, input().split(' '))
deg = defaultdict(int)
to = defaultdict(list)
uf = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split(' '))
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.unite(a, b)

for _ in range(K):
    c, d = map(int, input().split(' '))
    c -= 1
    d -= 1
    to[c].append(d)
    to[d].append(c)

for i in range(N):
    ans = uf.size(i) - 1 - deg[i]
    for u in to[i]:
        if uf.same(i, u):
            ans -= 1
    print(ans, end=' ' if i != (N - 1) else '\n')

Solution (Python):
from collections import deque

N,M,K = map(int,input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int,input().split())) for _ in range(K)]

f = [set() for _ in range(N+1)]
b = [set() for _ in range(N+1)]

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

stack=deque()
ans = [0]*(N+1)
visited = [0]*(N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in f[n]:
            if j in f[n] and visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    for i in link:
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1
print(*ans[1:])

Solution (Python):
from collections import deque

N,M,K = map(int,input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int,input().split())) for _ in range(K)]

f = [set() for _ in range(N+1)]
b = [set() for _ in range(N+1)]

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

stack=deque()
ans = [0]*(N+1)
visited = [0]*(N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in f[n]:
            if j in f[n] and visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    for i in link:
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1
print(*ans[1:])

Solution (Python):
from collections import deque

N,M,K = map(int,input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int,input().split())) for _ in range(K)]

f = [set() for _ in range(N+1)]
b = [set() for _ in range(N+1)]

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

stack=deque()
linkList = []
ans = [0] *(N+1)
visited = [0] * (N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in f[n]:
            if j in f[n] and visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    linkList.append(link)
    for i in link:
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1
print(*ans[1:])