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 UnionFind:
    def __init__(self, n):
        self.root = list(range(n))
        self.size = [1] * (n)
    def find_root(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x
    """
    def find_root(self, x):
        root = self.root
        if root[x] == x:
            return x
        else:
            root[x] = self.find_root(root[x])
            return root[x]
    """
    def merge(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy

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

uf = UnionFind(n)

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



ans = [uf.size[uf.find_root(i)] - 1 for i in range(n)]


for a, b in ab:
    ans[a-1] -= 1
    ans[b-1] -= 1

for c, d in cd:
    
    if uf.find_root(c-1) == uf.find_root(d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(' '.join(map(lambda x: str(x), ans)))

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.root = list(range(n))
        self.size = [1] * (n)
    def find_root(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x
    """
    def find_root(self, x):
        root = self.root
        if root[x] == x:
            return x
        else:
            root[x] = self.find_root(root[x])
            return root[x]
    """
    def merge(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy

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

uf = UnionFind(n)

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



ans = [uf.size[uf.find_root(uf.root[i])] - 1 for i in range(n)]


for a, b in ab:
    ans[a-1] -= 1
    ans[b-1] -= 1

for c, d in cd:
    if uf.find_root(uf.root[c-1]) == uf.find_root(uf.root[d-1]):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(' '.join(map(lambda x: str(x), ans)))

Solution (Python):
import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

class UnionFind():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans


def main():
    N, M, K = map(int,input().split())
    friend = {}
    block = {}
    tree = UnionFind(N)

    for _ in range(M):
        a,b = map(lambda x:int(x)-1,input().split())
        tree.unite(a,b)
        for _ in range(2):
            if not a in friend.keys():
                friend[a] = [b]
            else:
                friend[a].append(b)
            a,b = b,a

    for _ in range(K):
        c,d = map(lambda x:int(x)-1,input().split())
        for _ in range(2):
            if not c in block.keys():
                block[c] = [d]
            else:
                block[c].append(d)
            c,d = d,c

    def solve(x):
        res = 0
        res += tree.get_size(x)

        if x in friend.keys():
            res -= len(friend[x])

        if x in block.keys():
            res -= len(list(filter(lambda y: tree.is_same_group(x,y),block[x])))

        return res - 1

    ans = []
    for i in range(N):
        ans.append(str(solve(i)))

    print(" ".join(ans))


if __name__ == "__main__":
  main()

Solution (Python):
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    def dfs(graph,s,r):
        if rks[s] is None:
            rks[s] = r

        for i in range(len(graph[s])):
            if rks[graph[s][i]-1] is not None:
                continue
            dfs(graph, graph[s][i]-1,r)

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

    
    
    
    c = -1
    for i in range(n):
        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        
        
        
        
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    is_all_seen = [False]*n
    cnt = 0
    seen = [None]*n
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    def dfs(graph,s,r):
        seen[s] = s+1
        if rks[s] is None:
            rks[s] = r

        for i in range(len(graph[s])):
            if seen[graph[s][i]-1]:
                continue
            dfs(graph, graph[s][i]-1,r)

    for i in range(m):
        a,b = map(int, input().split())

        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

    
    
    
    c = -1
    for i in range(n):

        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        
        
        
        
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import collections

class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * (size + 1)  

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

    def merge(self, x, y):  
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]:  
            x, y = y, x
        self.parent[x] += self.parent[y]  
        self.parent[y] = x  
        return True

    def issame(self, x, y):  
        return self.root(x) == self.root(y)

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


def do():
    sys.setrecursionlimit(100000000)

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

    uf1 = UnionFind(N + 1) 
    friends_list= [set() for _ in range(N + 1)]
    block_list = [set() for _ in range(N + 1)]

    for query in friends :
        a,b= query
        uf1.merge(a,b)
        friends_list[a].add(b)
        friends_list[b].add(a)

    for query in blocks:
        a, b = query
        block_list[a].add(b)
        block_list[b].add(a)
    anss = []
    for i in range(1,N+1):
        s = uf1.size(i) -1 

        friends = friends_list[i]
        for friend in friends:
            if uf1.issame(friend,i):
                s -=1

        blocks = block_list[i]
        for block in blocks:
            if uf1.issame(block,i):
                s -=1
        anss.append(s)
    print(*(anss))

if __name__ == "__main__":
    do()

Solution (Python):
from bisect import bisect_left


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = [-1 for _ in range(n)]
        

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        else:
            if self.size(x) < self.size(y):
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x

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

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

    def is_root(self, x):
        return self.parent[x] < 0

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


def check(i, j):
    global friends
    global blocks
    a = bisect_left(friends, [i, j])
    b = bisect_left(friends, [j, i])
    c = bisect_left(blocks, [i, j])
    d = bisect_left(blocks, [j, i])



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

blocks = [[] for _ in range(n)]
friend_num = [0] * n
uf = UnionFind(n)

for _ in range(m):
    array = list(map(int, input().split()))
    uf.unite(array[0]-1, array[1]-1)
    friend_num[array[0]-1] += 1
    friend_num[array[1]-1] += 1

for _ in range(k):
    array = list(map(int, input().split()))
    blocks[array[0]-1].append(array[1]-1)
    blocks[array[1]-1].append(array[0]-1)

for i in range(n):
    uf.find(i)

for i in range(n):
    num = uf.size(i)
    personal_block_list = blocks[i]
    personal_block_num = 0
    for j in personal_block_list:
        if uf.same(i, j):
            personal_block_num += 1

    print(num-friend_num[i]-personal_block_num-1, end=' ')

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

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(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:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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

ans=[0]*N
uf1=UnionFind(N)
for i in range(M):  
    a,b=map(int, input().split()) 
    uf1.union(a-1,b-1)
    ans[a-1]-=1
    ans[b-1]-=1

for i in range(N):
    uf1.find(i)  

from collections import defaultdict
ll=defaultdict(int)
for i in uf1.par:
    ll[i]+=1

for i in range(N):
    ans[i]+=ll[uf1.par[i]]-1

for i in range(K):
    a,b=map(int, input().split()) 
    if uf1.is_same(a-1,b-1):
        ans[a-1]-=1
        ans[b-1]-=1

print(*ans)

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

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(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:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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

ans=[0]*N
uf1=UnionFind(N)
for i in range(M):  
    a,b=map(int, input().split()) 
    uf1.union(a-1,b-1)
    ans[a-1]-=1
    ans[b-1]-=1

for i in range(N):
    uf1.find(i)  

from collections import defaultdict
ll=defaultdict(int)
for i in uf1.par:
    ll[i]+=1

for i in range(N):
    ans[i]+=ll[uf1.par[i]]-1

for i in range(K):
    a,b=map(int, input().split()) 
    if uf1.is_same(a-1,b-1):
        ans[a-1]-=1
        ans[b-1]-=1

print(*ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for _ in range(n)]

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

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

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

        if self.par[x]>self.par[y]:
            x,y = y,x

        self.par[x] += self.par[y]
        self.par[y] = x

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

n,m,k = map(int, input().split())
uf = UnionFind(n+1)
dd = {}
for i in range(n):
    dd[i] = set()

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

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

res = [0]*n
for i in range(n):
    res[i] = uf.size(i) - len(dd[i]) - 1

print(*res)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))'''
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield set(x for x, _ in group)

N,M,K = m()

po = [0 for i in range(N)]

uni = UnionFind(N-1)

pon = [set() for i in range(N)]

for i in range(M):
    x,y = m()
    po[x-1] -= 1
    po[y-1] -= 1
    uni.unite(x-1,y-1)

for i in range(K):
    x,y = m()
    pon[x-1].add(y-1)
    pon[y-1].add(x-1)

a = list(uni.grouper())


for i in range(len(a)):
    for popo in a[i]:
        po[popo] += len(a[i]) - len(a[i] & pon[popo]) - 1
print(jo(po))

Solution (Python):
class Unionfind:
    def __init__(self, n):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.find(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]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True
    
    def same(self, x, y):
        if self.find(x)==self.find(y):
            return True
        return False
    
    def size(self, x):
        return (-1) * self.d[self.find(x)]

N, M, K = map(int,input().split())
deg = [0]*N
uf = Unionfind(N)
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.unite(a, b)
    

for i in range(K):
    a, b = map(int, input().split())
    
    
    if uf.same(a-1, b-1)==True:
        deg[a-1] += 1
        deg[b-1] += 1

for i in range(N):
    
    
    print(uf.size(i)-1-deg[i])

Solution (Python):
def d_friend_suggestions():
    N, M, K = [int(i) for i in input().split()]
    Friends = [[int(i) - 1 for i in input().split()] for j in range(M)]
    Blocked = [[int(i) - 1 for i in input().split()] for j in range(K)]

    class UnionFind(object):
        def __init__(self, n):
            """要素番号は 0 スタートを前提とする"""
            self.num_element = n
            self.parents = [-1] * n  

        def find(self, x):
            """要素 x が属するグループの根を返す"""
            if self.parents[x] < 0:
                return x
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

        def union(self, x, y):
            """要素 x が属するグループと要素 y が属するグループとを併合する"""
            u, v = self.find(x), self.find(y)

            if u == v:
                return

            
            if self.parents[u] > self.parents[v]:
                u, v = v, u

            self.parents[u] += self.parents[v]  
            self.parents[v] = u  

        def get_size(self, x):
            """要素 x が属するグループの要素数を返す"""
            return -self.parents[self.find(x)]

        def is_same(self, x, y):
            """要素 x, y は同じグループに属するか？"""
            return self.find(x) == self.find(y)

    uf = UnionFind(N)
    degree = [0] * N
    for a, b in Friends:
        uf.union(a, b)
        degree[a] += 1
        degree[b] += 1
    for c, d in Blocked:
        if uf.is_same(c, d):
            degree[c] += 1
            degree[d] += 1

    ans = [uf.get_size(i) - 1 - degree[i] for i in range(N)]
    return ' '.join(map(str, ans))

print(d_friend_suggestions())

Solution (Python):
import sys
import math
import copy
import queue
input = sys.stdin.readline
n,m,k = map(int,input().split())
f = [[] for _ in range(n+1)]
b = [[] for _ in range(n+1)]
for _ in range(m):
    x,y = map(int,input().split())
    f[x].append(y)
    f[y].append(x)
for _ in range(k):
    x,y = map(int, input().split())
    b[x].append(y)
    b[y].append(x)
g = [0 for _ in range(n+1)]
g_cnt = [0]
g_no = 0
for i in range(1,n+1):
    if g[i] > 0:
        continue

    g_no += 1
    q = queue.Queue()
    q.put(i)
    cnt = 0
    while not q.empty():
        g[i] = g_no
        node = q.get()
        cnt += 1
        for n_node in f[node]:
            if g[n_node] == 0:
                q.put(n_node)
                g[n_node] = g_no
    g_cnt.append(cnt)

for i in range(1,n+1):
    block = 0
    for x in b[i]:
        block += (g[i] == g[x])
    print (g_cnt[g[i]] - len(f[i]) - block - 1,end=' ')
print ()

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)

    def Find_Root(self, x):
        if (self.root[x] == x):
          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.size[x] > self.size[y]):
            self.size[x] += self.size[y]
            self.root[y] = x
        else:
            self.size[y] += self.size[x]
            self.root[x] = y

    def isSameGroup(self, x, y):
      return self.Find_Root(x) == self.Find_Root(y)

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

A = UnionFind(N)

F = [0] * (N + 1)
for _ in range(M):
    a, b = map(int, input().split())
    F[a] += 1
    F[b] += 1
    A.Unite(a, b)
    
B = [0] * (N + 1)
for _ in range(K):
    c, d = map(int, input().split())
    if A.isSameGroup(c, d):
        B[c] += 1
        B[d] += 1
        
ans = []
for i in range(1, N + 1):
    size = A.size[A.Find_Root(i)]
    block = B[i]
    friends = F[i]
    res = size - block - friends - 1
    ans.append(str(res))

print(" ".join(ans))

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = list(range(n + 1))
        self.size = [1] * (n + 1)

    def root(self, x: int) -> int:
        if self.par[x] == x: return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self, x: int, y: int):
        root_x, root_y = self.root(x), self.root(y)
        if root_x != root_y:
            if self.size[root_x] < self.size[root_y]:
                root_x, root_y = root_y, root_x
            self.size[root_x] += self.size[root_y]
            self.par[root_y] = root_x

    def check(self, x: int, y: int) -> bool:
        root_x, root_y = self.root(x), self.root(y)
        return root_x == root_y

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

u = UnionFind(N)

ABm = [0] * (N + 1)
for _ in range(M):
    a, b = map(int, input().split())
    ABm[a] += 1
    ABm[b] += 1
    u.unite(a, b)
    
CDk = [0] * (N + 1)
for _ in range(K):
    c, d = map(int, input().split())
    if u.check(c, d):
        CDk[c] += 1
        CDk[d] += 1
        
ans = []
for i in range(1, N + 1):
    size = u.size[u.root(i)]
    block = CDk[i]
    friends = ABm[i]
    res = size - block - friends - 1
    ans.append(str(res))

print(" ".join(ans))

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))    
        self.siz = [1] * n

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.siz[x] > self.siz[y]:     
            x, y = y, x
        self.siz[y] += self.siz[x]
        self.par[x] = y

    def tree_size(self, x):
        return self.siz[self.root(x)]


N, M, K = map(int, input().split())
F = UnionFind(N)
n_friend = [0] * N

B = {}
for i in range(N):
    B[i] = set()
for _ in range(M):
    p, q = map(int, input().split())
    n_friend[p - 1] += 1
    n_friend[q - 1] += 1
    F.unite(p - 1, q - 1)
for _ in range(K):
    p, q = map(int, input().split())
    B[p - 1].add(q - 1)
    B[q - 1].add(p - 1)



i, blocked = 0, 0
for b in B[0]:
    if F.same(i, b):
        blocked += 1
print(F.tree_size(i) - 1 - n_friend[i] - blocked, end='')
for i in range(1, N):
    print(' ', end='')
    blocked = 0
    for b in B[i]:
        if F.same(i, b):
            blocked += 1
    print(F.tree_size(i) - 1 - n_friend[i] - blocked, end='')
print('')

Solution (Python):
N, M, K = map(int, input().split())
par = list(range(N))
siz = [1] * N
n_friend = [0] * N


def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]


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


def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    if siz[x] > siz[y]:
        x, y = y, x
    siz[y] += siz[x]
    par[x] = y


def tree_size(x):
    return siz[root(x)]


B = {}
for i in range(N):
    B[i] = set()
for _ in range(M):
    p, q = map(int, input().split())
    n_friend[p - 1] += 1
    n_friend[q - 1] += 1
    unite(p - 1, q - 1)
for _ in range(K):
    p, q = map(int, input().split())
    B[p - 1].add(q - 1)
    B[q - 1].add(p - 1)



i, blocked = 0, 0
for b in B[0]:
    if same(i, b):
        blocked += 1
print(tree_size(i) - 1 - n_friend[i] - blocked, end='')
for i in range(1, N):
    print(' ', end='')
    blocked = 0
    for b in B[i]:
        if same(i, b):
            blocked += 1
    print(tree_size(i) - 1 - n_friend[i] - blocked, end='')
print('')

Solution (Python):
N, M, K = map(int, input().split())
par = list(range(N))
siz = [1] * N
n_friend = [0] * N


def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]


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


def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    if siz[x] > siz[y]:
        x, y = y, x
    siz[y] += siz[x]
    par[x] = y


def tree_size(x):
    return siz[root(x)]


B = {}
for i in range(N):
    B[i] = set()
for _ in range(M):
    p, q = map(int, input().split())
    n_friend[p - 1] += 1
    n_friend[q - 1] += 1
    unite(p - 1, q - 1)
for _ in range(K):
    p, q = map(int, input().split())
    B[p - 1].add(q - 1)
    B[q - 1].add(p - 1)



i, blocked = 0, 0
for b in B[0]:
    if same(i, b):
        blocked += 1
print(tree_size(i) - 1 - n_friend[i] - blocked, end='')
for i in range(1, N):
    print(' ', end='')
    blocked = 0
    for b in B[i]:
        if same(i, b):
            blocked += 1
    print(tree_size(i) - 1 - n_friend[i] - blocked, end='')
print('')

Solution (Python):
N,M,K=map(int,input().split())
par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]

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

def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            siz[a]+=siz[b]
        else:
            par[a]=b
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
            

def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)

ans=[0 for i in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    union(A,B)
    ans[A]-=1
    ans[B]-=1
for i in range(N):
    ans[i]+=size(i)-1
for _ in range(K):
    C,D=map(int,input().split())
    C,D=C-1,D-1
    if(same(C,D)):
        ans[C]-=1
        ans[D]-=1
        
print(*ans)