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.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)

n, m, k = map(int, input().split())
L = UnionFind(n)
F = [0] * n
B = [0] * n

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

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

for i in range(n):
    print(L.size(i) - F[i] - B[i] - 1)

Solution (Python):
class UnionFind():
    def __init__(self,n):
      self.n=n
      self.root=[-1]*(n+1)
      self.rank=[0]*(n+1)
      
    def find(self,x):
      if self.root[x]<0:
        return x
      else:
        self.root[x]=self.find(self.root[x])
        return self.root[x]
    
    def unite(self,x,y):
      x=self.find(x)
      y=self.find(y)
      if x==y:
        return 0
      elif self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      else:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
          
    def Same(self,x,y):
      return self.find(x)==self.find(y)
    
    def size(self,x):
      return -self.root[self.find(x)]
import sys
input=sys.stdin.buffer.readline
n,m,k=map(int,input().split())
link=UnionFind(n)
f=[0]*n
block=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    link.unite(a,b)
    f[a]+=1
    f[b]+=1
for _ in range(k):
    a,b=map(int,input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
ans=[]
for i in range(n):
  ret=link.size(i)-f[i]-1
  for j in block[i]:
    if link.Same(i,j):
      ret-=1
  ans.append(ret)
print(*ans)

Solution (Python):
from collections import deque


def make_list(length, repeat):
    result = [[] for _ in range(length)]
    for _ in range(repeat):
        a, b = map(lambda x: int(x) - 1, input().split())
        result[a].append(b)
        result[b].append(a)
    return result


def main():
    n, m, k = map(int, input().split())
    friend = make_list(n, m)
    block = make_list(n, k)
    group_id = 1
    group = [0 for _ in range(n)]

    def dfs(start, group_id):
        q = deque([start])
        connection = 0
        if group[start] == 0:
            connection += 1
            while q:
                now = q.pop()
                group[now] = group_id
                for nn in friend[now]:
                    if group[nn] == 0:
                        group[nn] = group_id
                        q.append(nn)
                        connection += 1
        return connection

    count = {}
    for i in range(n):
        if group[i] == 0:
            count[group_id] = dfs(i, group_id)
            group_id += 1

    answer = [0 for _ in range(n)]
    for i in range(n):
        answer[i] = count[group[i]] - len(friend[i]) - 1
        for b in block[i]:
            if group[i] == group[b]:
                answer[i] -= 1
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

if __name__ == "__main__":
    main()

Solution (Python):
"""
D-Friend Suggestions
BFS
"""

import sys
input = sys.stdin.readline
from collections import deque, Counter


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

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

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

    label_list = [-1] * N
    label = 0
    for start_vertex in range(N):
        q = deque()

        def push(vertex, label):
            if label_list[vertex] != -1:
                return
            q.append(vertex)
            label_list[vertex] = label

        push(start_vertex, label)

        while len(q) != 0:
            vertex = q.popleft()
            friend_vertexes = friend[vertex]
            for f_vertex in friend_vertexes:
                push(f_vertex, label)
        label += 1

    connected_component_id = Counter(label_list)

    ans = []
    for i in range(N):
        vertex_label = label_list[i]
        connected_qty = connected_component_id[vertex_label]

        for j in block[i]:
            if label_list[i] == label_list[j]:
                connected_qty -= 1

        ans.append(connected_qty - len(friend[i]) - 1)

    print(*ans)


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())


class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))

        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}

    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]

    def union(self, x, y):
        super().union(self.d[x], self.d[y])

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

    def same(self, x, y):
        return super().same(self.d[x], self.d[y])

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

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

def MAP(): return map(int, input().split())
def ZIP(n): return zip(*(MAP() for _ in range(n)))

N, M, K = list(map(int, input().split()))
ans = [-1] * N
uf = UnionFindLabel(range(1, N + 1))
for i in range(M):
    node1, node2 = list(map(int, input().split()))
    ans[node1 - 1] -= 1
    ans[node2 - 1] -= 1
    if not uf.same(node1, node2):
        uf.union(node1, node2)
for i in range(N):
    ans[i] += uf.size(i + 1)
for i in range(K):
    node1, node2 = list(map(int, input().split()))
    if uf.same(node1, node2):
        ans[node1 - 1] -= 1
        ans[node2 - 1] -= 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())


class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))

        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}

    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]

    def union(self, x, y):
        super().union(self.d[x], self.d[y])

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

    def same(self, x, y):
        return super().same(self.d[x], self.d[y])

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

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

def MAP(): return map(int, input().split())
def ZIP(n): return zip(*(MAP() for _ in range(n)))

N, M, K = list(map(int, input().split()))
ans = [-1] * N
uf = UnionFindLabel(range(1, N + 1))
for i in range(M):
    node1, node2 = list(map(int, input().split()))
    ans[node1 - 1] -= 1
    ans[node2 - 1] -= 1
    if not uf.same(node1, node2):
        uf.union(node1, node2)
for i in range(N):
    ans[i] += uf.size(i + 1)
for i in range(K):
    node1, node2 = list(map(int, input().split()))
    if uf.same(node1, node2):
        ans[node1 - 1] -= 1
        ans[node2 - 1] -= 1
print(*ans)

Solution (Python):
class UnionFind:
    def __init__(self, num):
        self.rank = [0] * num
        self.par = [i for i in range(num)]

    def find_root(self, node):
        if self.par[node] == node:
            return node
        else:
            self.par[node] = self.find_root(self.par[node])
            return self.par[node]

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

    def union(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1



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


direct_friend = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    union_find.union(a - 1, b - 1)
    direct_friend[a - 1] += 1
    direct_friend[b - 1] += 1


group = [[] for _ in range(n)]
for i in range(n):
    group[union_find.find_root(i)].append(i)


res = [0] * n
for i in range(n):
    for people in group[i]:
        res[people] = len(group[i]) - 1


for i in range(n):
    res[i] -= direct_friend[i]


for i in range(k):
    c, d = map(int, input().split())
    if union_find.same_root(c - 1, d - 1):
        res[c - 1] -= 1
        res[d - 1] -= 1


print(*res)

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)]

IN=[ 0 for _ in range(N+1) ]

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

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

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

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


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 unite(self, x, y):
        """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):
        """xとyが同じ集合に属するか否か"""
        return self.find(x) == self.find(y)

    def size(self, x):
        """グループのサイズを返す"""
        return -self.parents[self.find(x)]

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

uf = UnionFind(N)
ans = [0] * N
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.unite(A, B)
    ans[A] -= 1
    ans[B] -= 1

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

for _ in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if uf.same(C, D):
        ans[C] -= 1
        ans[D] -= 1

print(*ans)

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

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 unite(self, x, y):
        """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):
        """xとyが同じ集合に属するか否か"""
        return self.find(x) == self.find(y)

    def size(self, x):
        """グループのサイズを返す"""
        return -self.parents[self.find(x)]

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

uf = UnionFind(N)
ans = [0] * N
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.unite(A, B)
    ans[A] -= 1
    ans[B] -= 1

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

for _ in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if uf.same(C, D):
        ans[C] -= 1
        ans[D] -= 1

print(*ans)

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

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

ab = [[] for j in range(n)]
cd = [[] for j in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
    
for i in range(k):
    c,d = map(int,input().split())
    cd[c-1].append(d-1)
    cd[d-1].append(c-1)
    
check = [-1]*n

def dfs(x,check):
    
    
    for i in range(len(ab[x])):
        cho = ab[x][i]
        
        if check[cho] != -1:
            continue
        check[cho] = num
        dfs(cho,check)
    
    return

num = 0
for i in range(n):
    
    if check[i] != -1:
        continue
    dfs(i,check)
    num += 1

grp_num = max(check)
grp_size = [0]*(grp_num+1)

for i in range(n):
    if check[i] == -1:
        continue
    grp_size[check[i]] += 1

for i in range(n):
    hiku = 0
    for j in range(len(cd[i])):
        
        if check[cd[i][j]] == check[i]:
            hiku += 1
            
    if check[i] == -1:
        print(0)
    else:
        print(grp_size[check[i]]-len(ab[i])-hiku-1,end=' ')

Solution (Python):
class UnionFind:
	def __init__ (self, n):
		self.n = n
		self.parent = [i for i in range(n)]
		self.rank = [1] * n
		self.size = [1] * n

	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 x != y:
			if self.rank[x] < self.rank[y]:
				self.parent[x] = y
				self.size[y] += self.size[x]
			else:
				self.parent[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 group_size(self, x):
		return self.size[self.find(x)]

N, M, K = map(int, input().split())
A, B = [0] * M, [0] * M
C, D = [0] * K, [0] * K

direct = [[] for _ in range(N)]
uf = UnionFind(N)

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

for i in range(K):
	C[i], D[i] = map(int, input().split())
	C[i] -= 1
	D[i] -= 1
	if uf.is_same(C[i], D[i]):
		direct[C[i]].append(D[i])
		direct[D[i]].append(C[i])

ans = [0] * N
for i in range(N):
	ans[i] = uf.group_size(i) - len(direct[i]) -1
print(*ans)

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

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

def root_of(x):
	if parent_of[x] < 0:
		return x
	else:
		parent_of[x] = root_of(parent_of[x])
		return parent_of[x]

def unite(x,y):
	top_root_x = root_of(x)
	top_root_y = root_of(y)
	if top_root_x == top_root_y:
		return False
	if parent_of[top_root_x] > parent_of[top_root_y]:
		top_root_x,top_root_y = top_root_y,top_root_x
	
	parent_of[top_root_x] += parent_of[top_root_y]
	parent_of[top_root_y] = top_root_x
	return True

def size_of(x):
		return -parent_of[root_of(x)]

def is_same(x,y):
	return root_of(x) == root_of(y)

friend_list = [-1] * n
for _ in range(m):
	a,b = map(int,input().split())
	a -= 1
	b -= 1
	friend_list[a] -=1
	friend_list[b] -=1
	unite(a,b)

for _ in range(k):
	c,d = map(int,input().split())
	c -= 1
	d -= 1
	if root_of(c) == root_of(d):
		friend_list[c] -= 1
		friend_list[d] -= 1
for i in range(n):
	friend_list[i] += size_of(i)
	
print(*friend_list)

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


def find(x):
    if par[x]<0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
 
def size(x):
    return -par[find(x)]
 
def unite(x,y):
    x,y=find(x),find(y)
    if x==y:
        return
    if x>y:
        x,y=y,x
    par[x]+=par[y]
    par[y]=x
 
def same(x,y):
    return find(x)==find(y)

ans=[-1 for i in range(n)]

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

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

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

print(*ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000)
N,m,k = [int(x) for x in input().split()]
p = []
q = []
roots = [0]*(N+1)
rootmatome = [0]*(N+1)
tonari = [0]*(N+1)
dame = [0]*(N+1)
for i in range(m):
    p.append(list(map(int, input().split())))
for i in range(k):
    q.append(list(map(int, input().split())))
par = []
for i in range(N+1):
    par.append(i)
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return root(par[x])
def unite(x,y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    par[rx] = ry
for i in range(m):
    unite(p[i][0],p[i][1])
for i in range(1,N+1):
  roots[i] = root(i)
for i in range(1,N+1):
    rootmatome[roots[i]] += 1
for i in range(m):
    tonari[p[i][0]] += 1
    tonari[p[i][1]] += 1
for i in range(k):
    if roots[q[i][0]] == roots[q[i][1]]:
        dame[q[i][0]] += 1
        dame[q[i][1]] += 1
for i in range(1,N+1):
    print(rootmatome[roots[i]] - tonari[i] - dame[i] - 1,end=" ")

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

class Union_Find:
    def __init__(self, n = 0):
        self.d = [-1] * n
    
    def find(self, x: int) -> int:
        if self.d[x] < 0:
            return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]
    
    def unite(self, x: int, y: int) -> bool:
        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: int, y: int) -> bool:
        return self.find(x) == self.find(y)

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


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

friends = [0] * n
blocks = [[] for _ in range(n)]

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

for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    blocks[c].append(d)
    blocks[d].append(c)

ans = []
for i in range(n):
    candidates = uf.size(i) - 1 - friends[i]
    for u in blocks[i]:
        if uf.same(i, u):
            candidates -= 1
    ans.append(candidates)

print(*ans)

Solution (Python):
def init(n):
    par = list(range(n))
    size = [1] * n
    return par, size

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 size[x] < size[y]:
        par[x] = y
        size[y] += size[x]
    else:
        par[y] = x
        size[x] += size[y]


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

par, size = init(N+1)
non_candidates = [1] * (N+1)
for i in range(M):
    a, b = map(int, input().split())
    unite(a, b)
    non_candidates[a] += 1
    non_candidates[b] += 1
    

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

for i in range(1, N+1):
    print(size[root(i)] - non_candidates[i], end=" ")

Solution (Python):

def inputlist(): return [int(j) for j in input().split()]
from collections import Counter


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]

N,M,K = inputlist()
uf = UnionFind(N+1)
graph = [[] for _ in range(N+1)]
for i in range(M):
    a,b = inputlist()
    uf.union(a,b)
    graph[a].append(b)
    graph[b].append(a)
brogra = [[] for _ in range(N+1)]
li = [0]*N
for i in range(K):
    c,d = inputlist()
    if uf.same(c,d):
        brogra[c].append(d)
        brogra[d].append(c)
for i in range(1,N+1):
    li[i-1] = uf.size(i) - len(graph[i]) - len(brogra[i]) -1
print(*li)

Solution (Python):
class UnionFind:

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

    def flatten(self):
        for i, _ in enumerate(self.t):
            self.find_root(i)

    def union(self, a, b):
        ra = self.find_root(a)
        rb = self.find_root(b)
        if ra != rb:
            self.t[max(ra, rb)] = min(ra, rb)

    def find_root(self, x):
        t = []
        while self.t[x] > 0:
            t.append(x)
            x = self.t[x]
        for _t in t:
            self.t[_t] = x
        return x


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    r = [1] * (n + 1)
    uf = UnionFind(n)
    for a, b in zip(*[iter(abcd[:2 * m])] * 2):
        r[a] += 1
        r[b] += 1
        uf.union(a, b)
    uf.flatten()
    for i, v in enumerate(uf.t):
        uf.t[i] = i if v < 0 else v
    mp = {k: set([]) for k in set(uf.t[1:])}
    for i, v in enumerate(uf.t[1:], start=1):
        mp[v].add(i)
    for c, d in zip(*[iter(abcd[2 * m:])] * 2):
        r[c] += 1 if d in mp[uf.t[c]] else 0
        r[d] += 1 if c in mp[uf.t[d]] else 0
    mp = {k: len(v) for k, v in mp.items()}
    return " ".join([str(mp[uf.t[i]] - r[i]) for i in range(1, n + 1)])


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Solution (Python):
class UnionFind:

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

    def flatten(self):
        for i, _ in enumerate(self.t):
            self.find_root(i)

    def union(self, a, b):
        ra = self.find_root(a)
        rb = self.find_root(b)
        if ra != rb:
            self.t[max(ra, rb)] = min(ra, rb)

    def find_root(self, x):
        t = []
        while self.t[x] > 0:
            t.append(x)
            x = self.t[x]
        for _t in t:
            self.t[_t] = x
        return x


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    r = [0] * (n + 1)
    uf = UnionFind(n)
    for a, b in zip(*[iter(abcd[:2 * m])] * 2):
        r[a] += 1
        r[b] += 1
        uf.union(a, b)
    uf.flatten()
    for i, v in enumerate(uf.t):
        uf.t[i] = i if v < 0 else v
    mp = {k: set([]) for k in set(uf.t[1:])}
    for i, v in enumerate(uf.t[1:], start=1):
        mp[v].add(i)
    for c, d in zip(*[iter(abcd[2 * m:])] * 2):
        r[c] += 1 if d in mp[uf.t[c]] else 0
        r[d] += 1 if c in mp[uf.t[d]] else 0
    mp = {k: len(v) for k, v in mp.items()}
    return " ".join([str(mp[uf.t[i]] - 1 - r[i]) for i in range(1, n + 1)])


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Solution (Python):
class UnionFind:

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

    def flatten(self):
        for i, _ in enumerate(self.t):
            self.find_root(i)

    def union(self, a, b):
        ra = self.find_root(a)
        rb = self.find_root(b)
        if ra != rb:
            self.t[max(ra, rb)] = min(ra, rb)

    def find_root(self, x):
        t = []
        while self.t[x] > 0:
            t.append(x)
            x = self.t[x]
        for _t in t:
            self.t[_t] = x
        return x


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    ab, cd = abcd[:2 * m], abcd[2 * m:]
    r = [0] * (n + 1)
    uf = UnionFind(n)
    for a, b in zip(*[iter(ab)] * 2):
        r[a] += 1
        r[b] += 1
        uf.union(a, b)
    uf.flatten()
    for i, v in enumerate(uf.t):
        if v < 0:
            uf.t[i] = i
    mp = {k: [] for k in set(uf.t[1:])}
    for i, v in enumerate(uf.t[1:], start=1):
        mp[v].append(i)
    mp = {k: set(v) for k, v in mp.items()}
    for c, d in zip(*[iter(cd)] * 2):
        r[c] += 1 if d in mp[uf.t[c]] else 0
        r[d] += 1 if c in mp[uf.t[d]] else 0
    mp = {k: len(v) for k, v in mp.items()}
    return " ".join([str(mp[uf.t[i]] - 1 - r[i]) for i in range(1, n + 1)])


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))