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):
from sys import setrecursionlimit


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


setrecursionlimit(10 ** 5)


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

parent = [-1] * N
friends = [[] for _ in range(N)]
for A, B in AB:
    unite(parent, A - 1, B - 1)
    friends[A-1].append(B-1)
    friends[B-1].append(A-1)
blocks = [[] for _ in range(N)]
for C, D in CD:
    blocks[C-1].append(D-1)
    blocks[D-1].append(C-1)

result = []
for i in range(N):
    p = find(parent, i)
    t = -parent[p] - 1
    t -= len(friends[i])
    for b in blocks[i]:
        if p == find(parent, b):
            t -= 1
    result.append(t)
print(*result)

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group_count = 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

        self.group_count -= 1

        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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

def int_(num_str):
    return int(num_str) - 1


N, M, K = map(int, input().split())
uf = UnionFind(N)
some = [1] * N
for i in range(M):
    a, b = map(int_, input().split())
    uf.union(a, b)
    some[a] += 1
    some[b] += 1
for i in range(K):
    c, d = map(int_, input().split())
    if uf.same(c, d):
        some[c] += 1
        some[d] += 1


ans = [uf.size(i) - some[i] for i in range(N)]
print(*ans)

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group_count = 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

        self.group_count -= 1

        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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

def int_(num_str):
    return int(num_str) - 1


N, M, K = map(int, input().split())
uf = UnionFind(N)
some = [1] * N
for i in range(M):
    a, b = map(int_, input().split())
    uf.union(a, b)
    some[a] += 1
    some[b] += 1
for i in range(K):
    c, d = map(int_, input().split())
    if not uf.same(c, d):
        pass
    else:
        some[c] += 1
        some[d] += 1


ans = [uf.size(i) - some[i] for i in range(N)]
print(*ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    def size(self, x):
        return -self.parents[self.root(x)]
    
    def members(self, x):
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_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)

friend = [0] * N
block = [[]*N for i in range(N)]

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

for _ in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    block[a].append(b)
    block[b].append(a)

for i in range(N):
    ans = uf.size(i) - 1
    ans -= friend[i]
    for br in block[i]:
        if uf.same(i, br):
            ans -= 1
    print(ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    def size(self, x):
        return -self.parents[self.root(x)]
    
    def members(self, x):
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_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)

friend = [0] * N
block = [[]*N for i in range(N)]

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

for _ in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    block[a].append(b)
    block[b].append(a)

for i in range(N):
    ans = uf.size(i) - 1
    ans -= friend[i]
    for br in block[i]:
        if uf.same(i, br):
            ans -= 1
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000)


class UnionFind:

    def __init__(self, N):
        self._N = N
        self._parents = [-1 for n in range(N)]
        self._size = [1 for n in range(N)]

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

    def size(self, x):
        assert self.is_root(x)
        return self._size[x]

    def find(self, x):
        if self.is_root(x):
            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._size[x] > self._size[y]:
            x, y = y, x

        self._parents[y] = x
        self._size[x] += self._size[y]
        self._size[y] = None


def solve():

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

    A = [0 for m in range(M)]
    B = [0 for m in range(M)]
    tree = UnionFind(N)
    for m in range(M):
        A[m], B[m] = map(int, input().split())
        tree.union(A[m]-1, B[m]-1)

    n_friends = [0 for n in range(N)]
    for m in range(M):
        root_a, root_b = tree.find(A[m]-1), tree.find(B[m]-1)
        assert root_a == root_b
        n_friends[A[m]-1] += 1
        n_friends[B[m]-1] += 1

    C = [0 for k in range(K)]
    D = [0 for k in range(K)]
    n_blocks_in_group = [0 for n in range(N)]
    for k in range(K):
        C[k], D[k] = map(int, input().split())
        root_c, root_d = tree.find(C[k]-1), tree.find(D[k]-1)
        if root_c == root_d:
            n_blocks_in_group[C[k]-1] += 1
            n_blocks_in_group[D[k]-1] += 1

    res = []
    for n in range(N):
        n_cand = tree.size(tree.find(n)) - n_friends[n] - n_blocks_in_group[n] - 1
        res.append(str(n_cand))
    print(' '.join(res))


solve()

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

def unite(x,y):
  x,y=find(x),find(y)
  if x!=y:
    if x>y:
        x,y=y,x
    par[x]+=par[y]
    par[y]=x
    
def same(x,y):
  return find(x)==find(y)

def size(x):
  return-par[find(x)]
  
n,m,k=map(int,input().split())

par=[-1]*n

F=[]
B=[]

f=[set() for _ in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    F.append([a,b])
    
for i in range(k):
    c,d=map(int,input().split())
    B.append([c,d])

for a,b in F:
    a-=1
    b-=1
    unite(a,b)
    f[a].add(b)
    f[b].add(a)

a=[size(i)-len(f[i])-1 for i in range(n)]

for c,d in B:
    c-=1
    d-=1
    if same(c,d):
        a[c]-=1
        a[d]-=1
print(*a)

Solution (Python):
class UnionFind:
    """
    sizeによる実装
    """

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

    def find(self, x):
        """
        x: child
        ret-> node
        xのグループの代表を見つける
        """
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        """
        union (x ,y)
        x,y: node
        ret->None
        """
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

    def same(self, x, y):
        """
        return true if x and y are in same group
        """
        return self.find(x) == self.find(y)

    def connectedNum(self, x):
        """
        return size of the group x belong to
        """
        return self.size[self.find(x)]

    def is_connected(self):
        """
        return true is all node is in one group
        """
        return self.connectedNum(0) == len(self.parent)


N, M, K = map(int, input().split())
F = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
B = [list(map(lambda x:int(x)-1, input().split())) for _ in range(K)]

B_set = [set() for _ in range(N)]
F_set = [set() for _ in range(N)]
for a, b in B:
    B_set[a].add(b)
    B_set[b].add(a)
for a, b in F:
    F_set[a].add(b)
    F_set[b].add(a)

Un = UnionFind(N)
for a, b in F:
    Un.union(a, b)

ans = [0]*N
for i in range(N):
    in_group_B = 0
    for b in B_set[i]:
        if Un.same(b, i):
            in_group_B += 1
    ans[i] = Un.connectedNum(i) - len(F_set[i])-in_group_B-1
print(*ans)

Solution (Python):
import sys

def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    """ Union-Find木の実装（ランクあり） """
    def __init__(self, n):
        self.n = n
        self.parent = [-1]*(n+1)    
        self.rank   = [0]*(n+1)     

    def root(self, x):
        """ 木の根を求める """
        if self.parent[x] < 0:      
            return x
        else:
            self.parent[x] = self.root(self.parent[x])  
            return self.parent[x]
            
    def unite(self, x, y):
        """ xとyの属する集合を併合 """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return 0
        elif self.rank[x] > self.rank[y]:
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def isSame(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.root(x) == self.root(y) or x==y
    
    def size(self, x):
        """ xと同じ集合に属する数 """
        return -self.parent[self.root(x)]


N, M, K = map(int, input().split())
uf = UnionFind(N)
friends = [[] for _ in range(N)]
blocks = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1; B -= 1
    uf.unite(A, B)
    friends[A].append(B)
    friends[B].append(A)
for i in range(K):
    C, D = map(int, input().split())
    C -= 1; D -= 1
    blocks[C].append(D)
    blocks[D].append(C)

ans = [0] * N
for i in range(N):
    ans[i] = uf.size(i) - 1   
    ans[i] -= len(friends[i]) 
    block_num = 0
    for j in blocks[i]:
        if uf.isSame(i,j):
            block_num += 1
    ans[i] -= block_num

print(*ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

class UnionFind:
    def __init__(self, N):
        self.roots = list(range(N + 1))
        self.counter = [1] * (N + 1)

    def get_root(self, n):
        if self.roots[n] != n:
            self.roots[n] = self.get_root(self.roots[n])
        return self.roots[n]

    def union(self, a, b):
        a, b = sorted([self.get_root(a), self.get_root(b)])
        if a != b:
            self.roots[b] = a
            self.counter[a] += self.counter[b]
            self.counter[b] = 0

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

    def count(self, x):
        return (self.counter[self.get_root(x)])

def resolve():
    N, M, K = [int(x) for x in input().split()]
    list = [[] for _ in range(N)]
    block = [[] for _ in range(N)]

    uf = UnionFind(N)

    for _ in range(M):
        A, B = [int(x)-1 for x in input().split()]
        list[A].append(B)
        list[B].append(A)
        uf.union(A,B)

    for _ in range(K):
        C, D = [int(x)-1 for x in input().split()]
        block[C].append(D)
        block[D].append(C)

    for i in range(N):
        ans = uf.count(i) - len(list[i]) - 1
        for j in block[i]:
            if uf.find(i ,j):
                ans -= 1

        print(ans, end=" ")

resolve()

Solution (Python):
class UnionFind:
    def __init__(self, N, l):
        self.roots = list(range(N+1))
        self.counter = [1]*(N+1)
        for a, b in l:
            self.union(a, b)
 
    def get_root(self, n):
        if self.roots[n] != n:
            self.roots[n] = self.get_root(self.roots[n])
        return self.roots[n]
 
    def union(self, a, b):
        a, b = sorted([self.get_root(a), self.get_root(b)])
        if a != b:
            self.roots[b] = a
            self.counter[a] += self.counter[b]
            self.counter[b] = 0
 
    def find(self, a, b):
        return self.get_root(a) == self.get_root(b)
 
    def count(self, x):
        return(self.counter[self.get_root(x)])
 
 
N, M, K = [int(i) for i in input().split()]
ab = [[int(i) for i in input().split()] for _ in range(M)]
cd = [[int(i) for i in input().split()] for _ in range(K)]
friend = [[] for _ in range(N+1)]
uf = UnionFind(N, ab)
 
for a, b in ab:
    friend[a].append(b)
    friend[b].append(a)
 
ans = [uf.count(i)-1-len(friend[i]) for i in range(N+1)]
 
for c, d in cd:
    if uf.find(c, d):
        ans[c] -= 1
        ans[d] -= 1
 
print(*ans[1:])

Solution (Python):
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)]

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

ans = [-1] * (N+1)
for i in range(M):
    a,b = map(int,input().split())
    ans[a] -= 1
    ans[b] -= 1
    t.Unite(a,b)

for i in range(N):
    ans[i+1] += t.Count(i+1)

for i in range(K):
    c,d = map(int,input().split())
    if t.isSameGroup(c,d):
        ans[c] -= 1
        ans[d] -= 1

del ans[0]
print(' '.join(map(str,ans)))

Solution (Python):
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)]

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

friends = [0] * (N+1)
for i in range(M):
    a,b = map(int,input().split())
    friends[a] += 1
    friends[b] += 1
    t.Unite(a,b)

ans = [t.Count(i+1) - friends[i+1] - 1 for i in range(N)]

block = [0] * (N+1)
for i in range(K):
    c,d = map(int,input().split())
    if t.isSameGroup(c,d):
        ans[c-1] -= 1
        ans[d-1] -= 1

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

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.d[x]
        
    
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x!=y):
            
            if(self.d[x] > self.d[y]):
                
                self.d[y] += self.d[x]
                self.d[x] = y
            else:
                self.d[x] += self.d[y]
                self.d[y] = x
    
    
    def size(self, x):
        if(self.d[x] < 0):
            return -self.d[x]
        else:
            return -self.d[self.find(x)]
    
    
    def same(self,x,y):
        return (self.find(x) == self.find(y))


N, M, K = map(int, input().split())
ut_f = UnionFind(N)
ut_b = UnionFind(N)
ab = []
cd = [] 
for i in range(M):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ut_f.unite(a,b)
    ab.append((a,b))
for j in range(K):
    c,d = map(int, input().split())
    c -= 1
    d -= 1
    ut_b.unite(c,d)
    cd.append((c,d))

ans = [0] * N
for i in range(N):
    ans[i] = ut_f.size(i) - 1


for a,b in ab:
    if(ut_f.same(a,b)):
        ans[a] -= 1
        ans[b] -= 1


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

Solution (Python):
class Union_Find():
    def __init__(self,n):
        self.n=n
        self.par=[-1]*n
    def root(self,x):
        if self.par[x]<0:
            return x
        else:
            self.par[x]=self.root(self.par[x])
            return self.par[x]
    def union(self,x,y):
        rx=self.root(x)
        ry=self.root(y)
        if rx==ry:
            return
        if self.par[rx]>self.par[ry]:
            rx,ry=ry,rx
        self.par[rx]+=self.par[ry]
        self.par[ry]=rx

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

    def same(self,x,y):
        return self.root(x)==self.root(y)
N,M,K=map(int,input().split())
deg=[0]*N
bro=[[]*N for _ in range(N)]
uf=Union_Find(N)
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    deg[a]+=1
    deg[b]+=1
    uf.union(a,b)
for j in range(K):
    a,b=map(int,input().split())
    a-=1
    b-=1
    bro[a].append(b)
    bro[b].append(a)

for q in range(N):
    ans=uf.size(q)-deg[q]-1
    for w in bro[q]:
        if uf.same(q,w):
            ans-=1
    print(ans,end=" ")

Solution (Python):
from collections import defaultdict
import sys
import time

sys.setrecursionlimit(2000)
N, M, K = [int(i) for i in input().split(" ")]

t = time.time()
class UnionNode():
    def __init__(self, number):
        self.number = number
        self.volume = 1
        self.master = None

    @property
    def root(self):
        if self.master:
            self.master = self.master.root
            return self.master
        else:
            return self

    def unite(self, target):
        seroot = self.root
        taroot = target.root
        if seroot.number == taroot.number:
            pass
        else:
            
            if seroot.volume > taroot.volume:
                seroot.volume += taroot.volume
                taroot.master = seroot
            else:
                taroot.volume += seroot.volume
                seroot.master = taroot

nodes = [UnionNode(i) for i in range(N)]

outlist = defaultdict(lambda :[])

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    nodes[a].unite(nodes[b])
    outlist[a].append(b)
    outlist[b].append(a)

for i in range(K):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    outlist[a].append(b)
    outlist[b].append(a)

result = []
for i in range(N):
    rootnode = nodes[i].root
    ret = rootnode.volume - 1
    for out in outlist[i]:
        if nodes[out].root.number == rootnode.number:
            ret -=1
    result.append(ret)




print(" ".join([str(i) for i in result]))

Solution (Python):
from collections import defaultdict
import sys
import time

sys.setrecursionlimit(2000)
N, M, K = [int(i) for i in input().split(" ")]

t = time.time()
class UnionNode():
    def __init__(self, number):
        self.number = number
        self.volume = 1
        self.master = None

    @property
    def root(self):
        if self.master:
            self.master = self.master.root
            return self.master
        else:
            return self

    def unite(self, target):
        seroot = self.root
        taroot = target.root
        if seroot.number == taroot.number:
            pass
        else:
            
            if seroot.number < taroot.number:
                seroot.volume += taroot.volume
                taroot.master = seroot
            else:
                taroot.volume += seroot.volume
                seroot.master = taroot

nodes = [UnionNode(i) for i in range(N)]

outlist = defaultdict(lambda :[])

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    nodes[a].unite(nodes[b])
    outlist[a].append(b)
    outlist[b].append(a)

for i in range(K):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    outlist[a].append(b)
    outlist[b].append(a)

result = []
for i in range(N):
    rootnode = nodes[i].root
    ret = rootnode.volume - 1
    for out in outlist[i]:
        if nodes[out].root.number == rootnode.number:
            ret -=1
    result.append(ret)




print(" ".join([str(i) for i in result]))

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

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

    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 __str__(self):
        return '\n'.join('{}: {}'.format(root, self.members(root)) for root in self.roots())

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

uf_friend = UnionFind(n+1)
uf_block = UnionFind(n+1)
count = [0]*(n+1)
for i in range(m):
    a,b = map(int, input().split(" "))
    uf_friend.union(a, b)
    count[a] += 1
    count[b] += 1

for i in range(k):
    a,b = map(int, input().split(" "))
    if(uf_friend.issame(a,b)):
        count[a] += 1
        count[b] += 1

result = [0]*n
for i in range(1,n+1):
    result[i-1] = uf_friend.count(i) - count[i] - 1

print(*result)

Solution (Python):




from collections import defaultdict


def main():
    n, m, k = map(int, input().split())
    fr_ed_c = defaultdict(int)  

    parents = {}  
    root_2_nc = {}  

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

        p_a = get_root(parents, a)
        p_b = get_root(parents, b)

        if p_a == p_b:
            
            pass
        else:
            
            p_a_c = root_2_nc.get(p_a, 1)
            p_b_c = root_2_nc.get(p_b, 1)
            p_a, p_b = (p_a, p_b) if p_a_c < p_b_c else (p_b, p_a)
            parents[p_a] = p_b
            if p_b not in root_2_nc:
                root_2_nc[p_b] = 1
            root_2_nc[p_b] += root_2_nc.pop(p_a, 1)

    br_ed = defaultdict(set)  
    for i in range(k):
        c, d = map(int, input().split())
        br_ed[c].add(d)
        br_ed[d].add(c)

    ans_list = []
    for i_m in range(n):
        i = i_m + 1
        root = get_root(parents, i)
        block_count = 0
        for b in br_ed[i]:
            b_root = get_root(parents, b)
            block_count += 1 if root == b_root else 0
        ans = root_2_nc.get(root, 1) - 1 - fr_ed_c.get(i, 0) - block_count
        ans_list.append(str(ans))
    print(" ".join(ans_list))


def get_root(parents, i):
    if i not in parents:
        return i
    return get_root(parents, parents[i])


if __name__ == '__main__':
    main()