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):
N, M, K = map(int, input().split())

parents = [-1] * N
friend = [set() for _ in range(N)]

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

def union(x, y):
	x = find(x)
	y = find(y)

	if x == y:
		return

	if parents[x] > parents[y]:
		x, y = y, x

	parents[x] += parents[y]
	parents[y] = x

for _ in range(M):
	A, B = map(int, input().split())
	union(A-1, B-1)
	friend[A-1].add(B-1)
	friend[B-1].add(A-1)

a = [-parents[find(i)]-len(friend[i])-1 for i in range(N)]

for _ in range(K):
	C, D = map(int, input().split())
	if find(C-1) == find(D-1):
		a[C-1] -= 1
		a[D-1] -= 1
print(*a)

Solution (Python):
class UnionFind:
    def __init__(self, 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 is_same_root(self, x, y):
        return self.find(x) == self.find(y)

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

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


friends = [0]*N
for _ in range(M):
    u, v = map(lambda x: int(x)-1, input().split())
    
    
    friends[u] += 1
    friends[v] += 1
    uf.union(u, v)
blocks = [0]*N
for _ in range(K):
    u, v = map(lambda x: int(x)-1, input().split())
    if uf.is_same_root(u, v):
        blocks[u] += 1
        blocks[v] += 1

res = [uf.get_group_size(i)-friends[i]-blocks[i]-1 for i in range(N)]
print(' '.join(map(str, res)))

Solution (Python):
from collections import defaultdict

class UnionFind:
    def __init__(self, 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 is_same_root(self, x, y):
        return self.find(x) == self.find(y)

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

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

friends = defaultdict(set)
for _ in range(M):
    u, v = map(lambda x: int(x)-1, input().split())
    friends[u].add(v)
    friends[v].add(u)
    uf.union(u, v)
blocks = [0]*N
for _ in range(K):
    u, v = map(lambda x: int(x)-1, input().split())
    if uf.is_same_root(u, v):
        blocks[u] += 1
        blocks[v] += 1

res = [uf.get_group_size(i)-len(friends[i])-blocks[i]-1 for i in range(N)]
print(' '.join(map(str, res)))

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

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

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

uf = UnionFind(n)

edge = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    uf.union(a-1, b-1)
for i in range(k):
    c, d = map(int, input().split())
    edge[c-1].append(d-1)
    edge[d-1].append(c-1)


cnt = [None] * n
for i in range(n):
    cnt[i] = uf.get_size(i)


cnt_2 = [0] * n
for i in range(n):
    for j in edge[i]:
        if uf.is_same(i, j):
            cnt_2[i] += 1

ans = [None] * n
for i in range(n):
    ans[i] = cnt[i] - cnt_2[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 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 solve(N,A,C):
    uf = UnionFind(N)
    ans = [0]*N
    for a in A:
        u,v = a
        uf.union(u-1,v-1)
        ans[u-1] -= 1
        ans[v-1] -= 1
    for i in range(N):
        ans[i] += uf.size(i) - 1
    for c in C:
        s,t = c
        if uf.same(s-1,t-1):
            ans[s-1] -= 1
            ans[t-1] -= 1
    return ans
def main():
    N,M,K = map(int,input().split(" "))
    A = [list(map(int,input().split(" "))) for _ in range(M)]
    C = [list(map(int,input().split(" "))) for _ in range(K)]
    ans = solve(N,A,C)
    print(*ans)
    
if __name__ == "__main__":
    main()

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

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

n,m,k=map(int,input().split())
fre=[list(map(int,input().split()))for _ in range(m)]
bro=[list(map(int,input().split()))for _ in range(k)]
f_cnt=[0]*(n+1)
b_cnt=[0]*(n+1)
u=UnionFind(n)

for i in range(m):
    u.unite(fre[i][0],fre[i][1])
    f_cnt[fre[i][0]]+=1
    f_cnt[fre[i][1]]+=1
for i in range(k):
    if u.isSame(bro[i][0],bro[i][1])==True:
        b_cnt[bro[i][0]]+=1
        b_cnt[bro[i][1]]+=1

for i in range(1,n+1):
    print(u.size(i)-f_cnt[i]-b_cnt[i]-1 ,end=" ")

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

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

block = [[] for _ in range(n + 1)]

for _ in range(k):
    c, d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)

def dfs(graph, start):
    visited = set([start])
    stack = []
    can_reach = set([start])
    for f in graph[start]:
        stack.append(f)
        can_reach.add(f)
    while stack:
        friend = stack.pop()
        visited.add(friend)
        candidates = graph[friend]
        for c in candidates:
            if c not in visited:
                can_reach.add(c)
                stack.append(c)
    return can_reach

labels = [None] * (n + 1)
for i in range(1, n + 1):
    if labels[i] is None:
        c = dfs(graph, i)
        for j in c:
            labels[j] = [i, len(c)]

ans = []
for i in range(1, n + 1):
    num = labels[i][1] - 1
    for j in graph[i]:
        if labels[i][0] == labels[j][0]:
            num -= 1
    for k in block[i]:
        if labels[i][0] == labels[k][0]:
            num -= 1
    ans.append(num)
print(*ans)

Solution (Python):
class UnionFind():
    '''
    UnionFindでグラフの状態を管理する
    '''
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n)
        self.rnk = [0]*(n)

    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 is_same_group(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())
union_find = UnionFind(N)
AB = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int,input().split())
    a, b = a-1,b-1
    AB[a].append(b)
    AB[b].append(a)
    union_find.unite(a, b)

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

ret = [-1] * N
for i in range(N):
    ret[i] += union_find.count(i)

for i in range(N):
    for a in AB[i]:
        if union_find.is_same_group(i, a):
            ret[i] -= 1
    for c in CD[i]:
        if union_find.is_same_group(i, c):
            ret[i] -= 1

print(*ret, sep=" ")

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        
        
        self.par = [i for i in range(n+1)]
        
        self.rank = [0] * (n+1)
        
        self.size = [1] * (n+1)
        
        self.tree = [True] * (n+1)

    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:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            res = set()
            for i in range(self.n+1):
                res.add(self.find(i))
            
            return len(res) - 1
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N, M, K = MAP()
uf = UnionFind(N)
ans = [0] * N

for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    uf.union(a, b)
    ans[a] -= 1
    ans[b] -= 1

for a in range(N):
    ans[a] += uf.get_size(a) - 1

for i in range(K):
    a, b = MAP()
    a -= 1; b -= 1
    if uf.is_same(a, b):
        ans[a] -= 1
        ans[b] -= 1
print(*ans)

Solution (Python):
class UnionFind():
    '''
    UnionFindでグラフの状態を管理する
    '''
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n)
        self.rnk = [0]*(n)

    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 is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]

    def get_root(self):
        return self.root

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


N, M, K = map(int, input().split())
union_find = UnionFind(N)
AB = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int,input().split())
    a, b = a-1,b-1
    AB[a].append(b)
    AB[b].append(a)
    union_find.unite(a, b)

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

ret = [-1] * N
for i in range(N):
    union_find.find_root(i)
    ret[i] += union_find.get_member(i)

for i in range(N):
    for a in AB[i]:
        if union_find.is_same_group(i, a):
            ret[i] -= 1
    for c in CD[i]:
        if union_find.is_same_group(i, c):
            ret[i] -= 1

print(*ret, sep=" ")

Solution (Python):
def main():
    class unionfind():
        
        def __init__(self, size):  
            self.size = size
            self.tree_root = list(range(self.size))
            self.tree_depth = [1]*self.size
            self.tree_size = [1]*self.size

        
        def root(self, index):
            temp_list = []
            temp = self.tree_root[index]
            while index != temp:
                temp_list.append(index)
                index = temp
                temp = self.tree_root[index]
            for i in temp_list:
                self.tree_root[i] = index
            return index

        
        def unite(self, index1, index2):
            r1 = self.root(index1)
            r2 = self.root(index2)
            if r1 != r2:
                d1, d2 = self.tree_depth[r1], self.tree_depth[r2]
                if d1 <= d2:
                    self.tree_root[r1] = r2
                    self.tree_depth[r2] = max(d1+1, d2)
                    self.tree_size[r2] += self.tree_size[r1]
                else:
                    self.tree_root[r2] = r1
                    self.tree_depth[r1] = max(d2+1, d1)
                    self.tree_size[r1] += self.tree_size[r2]

        
        def same(self, index1, index2):
            r1 = self.root(index1)
            r2 = self.root(index2)
            return r1 == r2

    n, m, k = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*m]
    cd = [list(map(int, input().split())) for _ in [0]*k]
    u = unionfind(n)

    for a, b in ab:
        u.unite(a-1, b-1)

    friend = [u.tree_size[u.root(i)]-1 for i in range(n)]

    for a, b in ab:
        friend[a-1] -= 1
        friend[b-1] -= 1
    for c, d in cd:
        if u.same(c-1, d-1):
            friend[c-1] -= 1
            friend[d-1] -= 1
    print(*friend)


main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
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())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

uni = UnionFind(N)
friends = []

for _ in range(M):
    a,b = l_in()
    uni.union(a-1, b-1)
    friends.append((a-1, b-1))

blocks = []

for _ in range(K):
    c,d = l_in()
    blocks.append((c-1, d-1))

res = [uni.size(i)-1 for i in range(N)]

for a,b in friends:
    res[a] -= 1
    res[b] -= 1

for c,d in blocks:
    if uni.same(c, d):
        res[c] -= 1
        res[d] -= 1

print_l(res)

Solution (Python):
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    siz=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
        self.siz=[1 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
            self.siz[vertex2]+=self.siz[vertex1]
        else:
            self.par[vertex2]=vertex1
            self.siz[vertex1]+=self.siz[vertex2]
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)
    def size(self,vertex1):
        return self.siz[self.find(vertex1)]

N,M,K=map(int,input().split())
friends=[0 for i in range(N)]
F=UnionFind(N)
for i in range(M):
    a,b=map(int,input().split())
    friends[a-1]+=1
    friends[b-1]+=1
    F.unite(a-1,b-1)
blocks=[0 for i in range(N)]
for i in range(K):
    c,d=map(int,input().split())
    if F.same(c-1,d-1):
        blocks[c-1]+=1
        blocks[d-1]+=1


ans=[0 for i in range(N)]
for i in range(N):
    ans[i]=F.size(i)-friends[i]-blocks[i]-1
print(*ans)

Solution (Python):

import sys
N,M,K=map(int, sys.stdin.readline().split())

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

def root(x):
    while par[x]!=x:
        x=par[x]
    return 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 size[y]<size[x]: x,y=y,x  
    size[y]+=size[x]
    par[x]=y 

def getsize(x):
	return size[root(x)]

al_ok=[ 0 for i in range(N+1) ]	

for _ in range(M):
    a,b=map(int, sys.stdin.readline().split())
    unite(a,b)
    al_ok[a]+=1
    al_ok[b]+=1

al_ng=[ 0 for i in range(N+1) ]	
for _ in range(K):
    c,d=map(int, sys.stdin.readline().split())
    if same(c,d):
        al_ng[c]+=1
        al_ng[d]+=1

for i in range(1,N+1):
    print getsize(i)-1-al_ok[i]-al_ng[i],

Solution (Python):

import sys
N,M,K=map(int, sys.stdin.readline().split())

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

def root(x):
    while par[x]!=x:
        x=par[x]
    return 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 size[y]<size[x]: x,y=y,x  
    size[y]+=size[x]
    par[x]=y

def getsize(x):
	return size[root(x)]

al_ok=[ 0 for i in range(N+1) ]	

for _ in range(M):
    a,b=map(int, sys.stdin.readline().split())
    unite(a,b)
    al_ok[a]+=1
    al_ok[b]+=1

al_ng=[ 0 for i in range(N+1) ]	
for _ in range(K):
    c,d=map(int, sys.stdin.readline().split())
    if same(c,d):
        al_ng[c]+=1
        al_ng[d]+=1

for i in range(1,N+1):
    print getsize(i)-1-al_ok[i]-al_ng[i],

Solution (Python):

import sys
N,M,K=map(int, sys.stdin.readline().split())

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

def root(x):
    while par[x]!=x:
        x=par[x]
    return 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 size[y]<size[x]: x,y=y,x  
    size[y]+=size[x]
    par[x]=y

def getsize(x):
	return size[root(x)]

al_ok=[ 0 for i in range(N+1) ]	

for _ in range(M):
    a,b=map(int, sys.stdin.readline().split())
    unite(a,b)
    al_ok[a]+=1
    al_ok[b]+=1

al_ng=[ 0 for i in range(N+1) ]	
for _ in range(K):
    c,d=map(int, sys.stdin.readline().split())
    if same(c,d):
        al_ng[c]+=1
        al_ng[d]+=1

for i in range(1,N+1):
    print getsize(i)-1-al_ok[i]-al_ng[i],

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)
a = [0] * M
b = [0] * M
for i in range(M):
    a[i], b[i] = map(int, input().split())
    uf.union(a[i]-1, b[i]-1)

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

for i in range(M):
    if uf.same(a[i]-1, b[i]-1):
        ans[a[i]-1] -= 1
        ans[b[i]-1] -= 1

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

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

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M, K = (int(i) for i in input().split())
    par = [i for i in range(N)]
    rank = [0 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]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    edge = [set() for _ in range(N)]
    for i in [0]*M:
        a, b = (int(i) for i in input().split())
        edge[a-1].add(b-1)
        edge[b-1].add(a-1)
        unite(a-1, b-1)
    from collections import Counter
    for i, x in enumerate(par):
        unite(i, x)
    c = Counter(par)  
    for i in [0]*K:
        a, b = (int(i) for i in input().split())
        if is_same_group(a-1, b-1):
            edge[a-1].add(b-1)
            edge[b-1].add(a-1)
    for i in range(N):
        cur = c[par[i]] - len(edge[i]) - 1
        print(cur, end=" ")
    print()


if __name__ == '__main__':
    main()

Solution (Python):

from collections import deque
import sys
sys.setrecursionlimit(700000)

NIL = -1
N, M, K = map(int, input().split())
relation = [deque() for i in range(N)]
prefriends = [deque() for i in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    relation[A].append(B)
    relation[B].append(A)

def dfs(x, y):
    for i in relation[y]:
        if check[i] == None:
            
            prefriends[x].append(i)
            
            check[i] = x
            dfs(x, i)


j = 0
check = [None]*N
while j < N:
    if check[j] == None:
        
        prefriends[j].append(j)
        check[j] = j
        dfs(j, j)
        
    j += 1
    
    
    
    

for i in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if check[C] == check[D]:
        relation[C].append(D)
        relation[D].append(C)
ans = [0]*N
for j in range(N):
    ans[j] = len(prefriends[check[j]]) - len(relation[j]) - 1
    
    
print(*ans)

Solution (Python):

import sys
N,M,K=map(int, sys.stdin.readline().split())

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

def root(x):
    while par[x]!=x:
        x=par[x]
    return 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 size[x]<size[y]: x,y=y,x  
    size[x]+=size[y]
    par[y]=x


def getsize(x):
	return size[root(x)]

al_ok=[ 0 for i in range(N+1) ]	

for _ in range(M):
    a,b=map(int, sys.stdin.readline().split())
    unite(a,b)
    al_ok[a]+=1
    al_ok[b]+=1

al_ng=[ 0 for i in range(N+1) ]	
for _ in range(K):
    c,d=map(int, sys.stdin.readline().split())
    if same(c,d):
        al_ng[c]+=1
        al_ng[d]+=1

for i in range(1,N+1):
    print getsize(i)-1-al_ok[i]-al_ng[i],

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
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())
uni = UnionFind(N)
fn = [0 for i in range(N)]
bl = [[] for i in range(N)]
bn = [0 for i in range(N)]
for i in range(M):
    a,b= map(int,input().split())
    a -= 1
    b -= 1
    uni.union(a,b)
    fn[a] +=1
    fn[b] += 1
for i in range(K):
    a,b= map(int,input().split())
    a -= 1
    b -= 1
    if uni.find(a) == uni.find(b):
        bn[a] += 1
        bn[b] += 1
ans = [0 for i in range(N)]
for i in range(N):
    ans[i] = uni.size(i) - bn[i] - fn[i] -1
print(' '.join([str(i) for i in ans]))