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 UnionFindTree:
    __slots__ = ('__parents', )

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

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

    def union(self, x, y):
        p = self.__parents
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if p[x] > p[y]:
            x, y = y, x
        p[x] += p[y]
        p[y] = x
        return True

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

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


def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


def main():
    n, m, k = spline()
    similar = UnionFindTree(n)
    candidates = [-1] * n
    kw = {'func_': lambda x: int(x) - 1}
    for _ in range(m):
        a, b = spline(**kw)
        similar.union(a, b)
        candidates[a] -= 1
        candidates[b] -= 1
    for i in range(n):
        candidates[i] += similar.size(i)
    for _ in range(k):
        c, d = spline(**kw)
        if similar.same(c, d):
            candidates[c] -= 1
            candidates[d] -= 1
    print(*candidates, sep=' ')


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())
uf = UnionFind(n)
E = [[] for i in range(n)]
num_E = [0]*n
E_d = [[] for i in range(n)]

import sys
input = sys.stdin.readline

for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  uf.union(a, b)
  num_E[a] += 1
  num_E[b] += 1

for i in range(k):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  E_d[a] = E_d[a] + [b]
  E_d[b] = E_d[b] + [a]

num_men = [0]*n
for i in range(n):
  num_men[i] = uf.size(i) - 1
  for dn in E_d[i]:
    if uf.same(i, dn):
      num_men[i] -= 1
  num_men[i] -= num_E[i]
      
print(*num_men)

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 same(self, x, y):
        return self.find(x) == self.find(y)

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

import sys
def input():
    return sys.stdin.readline().strip()

n, m, k = map(int, input().split())
ans = [-1 for _ in range(n)]
uf = UnionFind(n)

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

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

for i in range(n):
    ans[i] += uf.size(i)

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

Solution (Python):
n,m,k = map(int,input().split())
frag=list(range(n+1))

def takefrag(p):
    stock=[]
    while frag[frag[p]]!=frag[p]:
        stock.append(p)
        p=frag[p]
    p=frag[p]
    for i in stock:
        frag[i]=p
    return p
    
ans=[-1]*(n+1)
for i in range(m):
    a,b = map(int,input().split())
    ans[a]-=1
    ans[b]-=1
    a,b = takefrag(a),takefrag(b)
    a,b = min(a,b),max(a,b)
    frag[a]=b

fragteam=[0]*(n+1)
for i in range(n+1):
    frag[i]=takefrag(i)
    fragteam[frag[i]]+=1
for i in range(k):
    a,b = map(int,input().split())
    if frag[a]==frag[b]:
        ans[a]-=1
        ans[b]-=1
for i in range(n+1):
    ans[i]+=fragteam[frag[i]]
for i in ans[1:-1]:
    print(i,end=" ")
print(ans[-1])

Solution (Python):
class UnionFind:
    def __init__(self, data):
        """
        サイズベースのunion_find
        与えられたdataまでの長さの配列を作成
        配列は1から開始する
        それがunionfindの親となり初めは自分自身
        またsizeも定義し初期値は1
        ・union findのグループのサイズの求め方
        1.あるxのグループの親を取得
        union_find = UnionFind(N)
        par_x = union_find.find(x)
        2.その親のsizeがそのグループのサイズになっている
        size = union_find.size[par_x]
        """
        self.parent = {}
        self.size = {}
        for i in range(1, data+1):
            self.parent[i] = i
            self.size[i] = 1


    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 same(self, x, y):
        """
        与えられた2つの値が同一グループ(親)かチェック
        """
        return self.find(x) == self.find(y)


    def unite(self, x, y):
        """
        与えられた2つの値を同一のグループ(親)にする
        """
        x = self.find(x)
        y = self.find(y)
        if x == y: 
            return
        if self.size[x] > self.size[y]: 
            self.parent[y] = x
            self.size[x] += self.size[y]
            return
        elif self.size[x] < self.size[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
            return
        else: 
            self.parent[x] = y
            if self.size[x] == self.size[y]: self.size[y] += self.size[x]
            return

if __name__ == '__main__':
    N,M,K = map(int, input().split())
    union_find = UnionFind(N)

    kankei = [[] for i in range(N+1)]
    for i in range(M):
        A,B = map(int, input().split())
        union_find.unite(A,B)
        kankei[A].append(B)
        kankei[B].append(A)

    for i in range(K):
        C,D = map(int, input().split())
        if union_find.same(C,D):
            kankei[C].append(D)
            kankei[D].append(C)

    ans = ""
    for i in range(1,N+1):
        ans += str(union_find.size[union_find.find(i)]-len(kankei[i])-1) + " "

    print(ans.rstrip())

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

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

    fs = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())
        fs[a].add(b)
        fs[b].add(a)

    bs = tuple(set() for _ in range(N))
    for _ in range(K):
        a, b = (int(x) - 1 for x in input().split())
        bs[a].add(b)
        bs[b].add(a)

    roots = [-1] * N
    for v in range(N):
        if ~roots[v]: continue
        roots[v] = v
        dq = deque()
        dq.append(v)
        while dq:
            v = dq.popleft()
            r = roots[v]
            for u in fs[v]:
                if ~roots[u]: continue
                roots[u] = r
                dq.append(u)

    sizes = [0] * N
    for r in roots:
        sizes[r] += 1

    ans = []
    for v in range(N):
        r = roots[v]
        res = sizes[r] - 1 - len(fs[v]) - sum(1 for u in bs[v] if roots[u] == r)
        ans.append(res)

    print(*ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10 ** 7)
    
    input = sys.stdin.readline

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

    fs = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())
        fs[a].add(b)
        fs[b].add(a)

    bs = tuple(set() for _ in range(N))
    for _ in range(K):
        a, b = (int(x) - 1 for x in input().split())
        bs[a].add(b)
        bs[b].add(a)

    roots = [-1] * N
    sizes = [-1] * N

    def dfs(v):
        """
        return: 連結成分のサイズを返す
        roots: 連結成分の各成分に根のindexを割り当てる
        """
        sz = 1
        for u in fs[v]:
            if ~roots[u]: continue
            roots[u] = roots[v]
            sz += dfs(u)
        return sz

    for v in range(N):
        if ~roots[v]: continue
        roots[v] = v
        sizes[v] = dfs(v)

    ans = []
    for v in range(N):
        r = roots[v]
        res = sizes[r] - 1 - len(fs[v]) - sum(1 for u in bs[v] if roots[u] == r)
        ans.append(res)

    print(*ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        
        self.par = list(range(n))
        self.siz = [1] * n
    
    def root(self, x):
        """データxが属する木の根を再帰で得る
        """
        if self.par[x] == x: return x  
        self.par[x] = self.root(self.par[x])  
        return self.par[x]

    def size(self, x):
        """データxが属する木のサイズを返す
        """
        return self.siz[self.root(x)]
    
    def unite(self, x, y):
        """xとyの木を併合する
        """
        rx, ry = self.root(x), self.root(y)
        if rx != ry:  
            if self.siz[rx] < self.siz[ry]: rx, ry = ry, rx  
            self.siz[rx] += self.siz[ry]
            self.par[ry] = rx  

    def same(self, x, y):
        """2つのデータx, yが属する木が同じならTrueを返す
        """
        rx, ry = self.root(x), self.root(y)
        return rx == ry

n, m, k = map(int, input().split())
uf = UnionFind(n)
n_friends = [0] * n
n_blocks = [0] * n

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

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

ans = []
for i in range(n):
    ans.append(uf.size(i) - n_friends[i] - n_blocks[i] - 1)
print(*ans)

Solution (Python):
from collections import deque
n, m, k = map(int, input().split())
friends = [[] for _ in range(n)]
blocks = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    friends[a-1].append(b-1)
    friends[b-1].append(a-1)
for _ in range(k):
    c, d = map(int, input().split())
    blocks[c-1].append(d-1)
    blocks[d-1].append(c-1)


grp_idx = [-1]*n
grp_szs = []
grp = 0
for i in range(n):
    if grp_idx[i]>=0:
        continue
    queue = deque([i])
    grp_idx[i] = grp
    tmp = 0
    while len(queue)>0:
        node = queue.popleft()
        for c_node in friends[node]:
            if grp_idx[c_node]>=0:
                continue
            grp_idx[c_node] = grp
            tmp += 1
            queue.append(c_node)
    grp_szs.append(tmp)
    grp += 1
ans = []
for i in range(n):
    tmp = grp_szs[grp_idx[i]]
    for j in friends[i]:
        if grp_idx[j]==grp_idx[i]:
            tmp -= 1
    for j in blocks[i]:
        if grp_idx[j]==grp_idx[i]:
            tmp -= 1
    ans.append(tmp)
print(*ans)

Solution (Python):
import collections
import sys
sys.setrecursionlimit(10**5)
N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]

CD = [tuple(map(int, input().split())) for i in range(K)]


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

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

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

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return



F = unionFind(N)
f = [set() for i in range(N)]
for a, b in AB:
    F.unite(a, b)
    a -= 1
    b -= 1
    f[a].add(b)
    f[b].add(a)

B = [set() for i in range(N)]
for c, d in CD:
    c -= 1
    d -= 1
    B[c].add(d)
    B[d].add(c)

ans = [0]*N
D = collections.defaultdict(set)
for i in range(N):
    D[F.root(i)].add(i)


for i in range(N):
    x = D[F.root(i)]
    ret = len(x)
    ret -= 1
    ret -= len(x & f[i])
    ret -= len(x & B[i])
    ans[i] = ret
print(*ans)

Solution (Python):
from collections import deque
N,M,K = map(int,input().split())
F = {i:set() for i in range(1,N+1)}
B = {i:set() for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    F[a].add(b)
    F[b].add(a)
for _ in range(K):
    c,d = map(int,input().split())
    B[c].add(d)
    B[d].add(c)
A = []
hist = [-1 for _ in range(N+1)]
cnt = -1
for i in range(1,N+1):
    if hist[i]<0:
        cnt += 1
        A1 = set()
        que = deque([i])
        hist[i] = cnt
        A1.add(i)
        while que:
            x = que.popleft()
            for y in F[x]:
                if hist[y]<0:
                    A1.add(y)
                    que.append(y)
                    hist[y]=cnt
        A.append(A1)
C = []
for i in range(1,N+1):
    cnt = hist[i]
    a = A[cnt]&B[i]
    C.append(len(A[cnt])-len(F[i])-len(a)-1)
print(*C)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        
        self.parent = [None]*n
        
        self.count = [0] * n

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

    def union(self, x, y):
        
        x0 = self.root(x)
        y0 = self.root(y)
        if x0 == y0:
            return
        if x0 > y0:
            x0, y0 = y0, x0
        self.parent[y0] = x0
        self.count[x0] += self.count[y0] + 1

    def size(self, x):
        
        return self.count[self.root(x)] + 1

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


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

F = [0]*n

B = [0]*n
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    F[a-1] += 1
    F[b-1] += 1
for j in range(k):
    a, b = map(int, input().split())
    if uf.same(a-1, b-1):
        B[a-1] += 1
        B[b-1] += 1
L = [uf.size(i)-1-F[i]-B[i] for i in range(n)]
print(*L)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

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

    def find_root(self, x: int) -> int:
        if self.d[x] < 0:
            return x
        self.d[x] = self.find_root(self.d[x])
        return self.d[x]

    def unite(self, x: int, y: int) -> bool:
        x = self.find_root(x)
        y = self.find_root(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 is_same(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

    def size(self, x: int) -> int:
        return (-1) * self.d[self.find_root(x)]

n, m, k = map(int, input().split())
uf = Union_Find(n)
ng = [set() for _ in range(n)]

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

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

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

print(*ans)

Solution (Python):
class UnionFind():
    def __init__(self, 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


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

friends = [[] for _ in range(n)]
blocks = [[] for _ in range(n)]
UF = UnionFind(n)

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

for j in range(k):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    blocks[a].append(b)
    blocks[b].append(a)

for i in range(n):
    num = UF.size(i) - 1
    for j in blocks[i]:
        if UF.same(i, j):
            num -= 1
    num -= len(friends[i])
    print(num, end=' ')

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        
        self.r = [1]*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 union(self, x, y):
        rx, ry = self.find(x), self.find(y)
 
        if rx != ry:
            if self.r[rx] > self.r[ry]:
                rx, ry = ry, rx
            if self.r[rx] == self.r[ry]:
                self.r[ry] += 1
            self.p[ry] += self.p[rx]
            self.p[rx] = ry
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def count_member(self, x):
        return -self.p[self.find(x)]

n,m,k=map(int,input().split())
uf=UnionFind(n)
ab,cd=[],[]
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  uf.union(a,b)
  ab.append((a,b))
for i in range(k):
  c,d=map(int,input().split())
  c-=1
  d-=1
  cd.append((c,d))
ans=[]
for i in range(n):
  t=uf.count_member(i)-1
  ans.append(t)
for a,b in ab:
  if uf.same(a,b):
    ans[a]-=1
    ans[b]-=1
for c,d in cd:
  if uf.same(c,d):
    ans[c]-=1
    ans[d]-=1
print(*ans)

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





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)]
  
uni=UnionFind(N)
fri=[[] for _ in range(N)]
blo=[[] for _ in range(N)]
for i in range(M):
  a,b=map(int, input().split())
  uni.Unite(a-1,b-1)
  fri[a-1].append(b-1)
  fri[b-1].append(a-1)
for i in range(K):
  c,d=map(int, input().split())
  blo[c-1].append(d-1)
  blo[d-1].append(c-1)
  
for i in range(N):
  ans=uni.Count(i)-len(fri[i])-1
  for a in blo[i]:
    if uni.isSameGroup(i,a):
      ans-=1
  print(ans, end=" ")

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


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

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

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

    def unite(self, A, B):
        
        
        A = self.root(A)
        B = self.root(B)

        
        if (A == B):
            return False

        
        if (self.size(A) < self.size(B)):
            A, B = B, A

        
        self.parent[A] += self.parent[B]  
        self.parent[B] = A  

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  





N, M, K = read_ints()



uf = UnionFind(N)
n_friends = [0] * N
n_blocked = [0] * N
for _ in range(M):
    a, b = read_ints()
    a -= 1
    b -= 1
    uf.unite(a, b)
    n_friends[a] += 1
    n_friends[b] += 1
for _ in range(K):
    c, d = read_ints()
    c -= 1
    d -= 1
    if uf.is_in_same(c, d):
        n_blocked[c] += 1
        n_blocked[d] += 1

ans = []
for i in range(N):
    ans.append(uf.size(i) - n_friends[i] - n_blocked[i] - 1)
print(*ans)

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 main():
    import sys
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    union_find = UnionFind(N)
    friends = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        friends[a].append(b)
        friends[b].append(a)
        union_find.union(a, b)
    blacks = [[] for _ in range(N)]
    for _ in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        blacks[c].append(d)
        blacks[d].append(c)
    ans = []
    for i in range(N):
        a = union_find.size(i) - len(friends[i])
        for black in blacks[i]:
            if union_find.same(i, black):
                a -= 1
        ans.append(a-1)
    print(" ".join(map(str, ans)))

if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2) :  
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  
            return

        self.component -= 1  

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

N, M, K = map(int, input().split())
AB = [tuple(map(lambda a: int(a) - 1, input().split())) for _ in range(M)]
CD = [tuple(map(lambda a: int(a) - 1, input().split())) for _ in range(K)]

friends = UnionFind(N)
for a, b in AB:
    friends.union(a, b)

ans = [0] * N
for i in range(N):
    ans[i] = friends.sizeOfSameRoot(i) - 1
for a, b in AB:
    ans[a] -= 1
    ans[b] -= 1
for c, d in CD:
    if friends.isSameRoot(c, d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline
import bisect
n,m,k = [int(i) for i in input().split()]
ans = [-1]*n

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

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

def size(x):
    return -par[find(x)]

par = [-1]*n
g = [[] * n for i in range(n)]
for i in range(m):
  a,b = [int(i) for i in input().split()]
  unite(a-1,b-1)
  ans[a-1] -= 1
  ans[b-1] -= 1
  
def same(x,y):
    return find(x) == find(y)
for i in range(k):
  u, v = map(int, input().split())
  if same(u-1,v-1):
    ans[u-1] -= 1
    ans[v-1] -= 1
  
for i in range(n):
  ans[i] += size(i)
  
print(*ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M, K = (int(i) for i in input().split())
    AB = [[int(i)-1 for i in input().split()] for j in range(M)]
    CD = [[int(i)-1 for i in input().split()] for j in range(K)]

    par = [i for i in range(N)]
    rank = [1 for i in range(N)]

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

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

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            x, y = y, x
        rank[x] += rank[y]
        par[y] = x

    def size(x):
        return rank[find_root(x)]

    friends = [[] for _ in range(N)]
    blocks = [[] for _ in range(N)]
    for a, b in AB:
        friends[a].append(b)
        friends[b].append(a)
        unite(a, b)
    for c, d in CD:
        if is_same_group(c, d):
            blocks[c].append(d)
            blocks[d].append(c)
    for i in range(N):
        ans = size(i) - len(friends[i]) - len(blocks[i]) - 1
        print(ans, end=" " if i != N-1 else "\n")


if __name__ == '__main__':
    main()