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 heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
import math
import bisect
import numpy as np
from collections import defaultdict, deque
from operator import itemgetter
from bisect import bisect_left, bisect_right
import sys
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 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())
    fg = [[] for _ in range(n)]
    uf = UnionFind(n)
    bg = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        fg[a].append(b)
        fg[b].append(a)
        uf.union(a, b)
    for _ in range(k):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        bg[c].append(d)
        bg[d].append(c)
    ans = [0] * n
    for i in range(n):
        ans[i] = uf.size(i)-1
        for f in fg[i]:
            if uf.same(f, i):
                ans[i] -= 1
        for b in bg[i]:
            if uf.same(b, i):
                ans[i] -= 1
    print(*ans)


if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind:
    """素集合を木構造として管理する"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """要素xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """要素xを含む集合と要素yを含む集合を統合する"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1

    def is_same(self, x, y):
        """要素x, yが同じ集合に属するかどうかを求める"""
        return self.root(x) == self.root(y)

    def get_size(self, x):
        """要素xを含む集合の要素数を求める"""
        return -self.parent[self.root(x)]


n, m, k = map(int, input().split())
b = [list(map(int, input().split())) for i in range(m)]
c = [list(map(int, input().split())) for i in range(k)]

uf = UnionFind(n)
b_graph = [[] for i in range(n)]
for u, v in b:
    u -= 1
    v -= 1
    uf.merge(u, v)
    b_graph[u].append(v)
    b_graph[v].append(u)
    
c_graph = [[] for i in range(n)]
for u, v in c:
    u -= 1
    v -= 1
    c_graph[u].append(v)
    c_graph[v].append(u)

ans = []
for i in range(n):
    res = uf.get_size(i) - 1
    res -= len(b_graph[i])
    for v in c_graph[i]:
        if uf.is_same(i, v):
            res -= 1
    ans.append(res)
print(*ans)

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

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

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.parent[root_x] > self.parent[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_x] += self.parent[root_y]
        self.parent[root_y] = root_x

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


def main():
    n, m, k = map(int, input().split())
    uf = UnionFind(n)
    friend = [[] for _ in range(n)]
    answer = [-1 for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        uf.union(a, b)
        friend[a].append(b)
        friend[b].append(a)
    for _ in range(k):
        c, d = map(lambda x: int(x) - 1, input().split())
        if uf.is_same(c, d):
            answer[c] -= 1
            answer[d] -= 1
    for i in range(n):
        answer[i] += uf.get_size(i) - len(friend[i])
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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, readline().split())
ab = [list(map(int, readline().split())) for _ in range(m)]
cd = [list(map(int, readline().split())) for _ in range(k)]
uf = UnionFind(n + 1)
cnt = [-1] * n
for a, b in ab:
    uf.union(a, b)
for i in range(n):
    cnt[i] += uf.size(i + 1)

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

Solution (Python):
from collections import defaultdict

N, M, K = map(int, input().split())
friends = defaultdict(list)
blocked = defaultdict(list)

for i in range(M):
    a, b = map(int, input().split())
    friends[a - 1].append(b - 1)
    friends[b - 1].append(a - 1)
for j in range(K):
    c, d = map(int, input().split())
    blocked[c - 1].append(d - 1)
    blocked[d - 1].append(c - 1)


class UnionFind:
    def __init__(self, n):
        
        self.n = n
        
        self._root_table = list(range(n))
        
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

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


uf = UnionFind(N)
for i in range(N):
    for j in friends[i]:
        uf.union(i, j)

ans = []
for i in range(N):
    res = uf.size(i) - len(friends[i]) - 1
    for b in blocked[i]:
        if uf.same(i, b):
            res -= 1
    ans.append(res)
print(*ans)

Solution (Python):
from itertools import chain
 
n,m,k = map(int,input().split())
 
bff = [list(map(int,input().split())) for i in range(m)]
 
blk = [list(map(int,input().split())) for i in range(k)]
 
 
rank = [0] * (n+1)
par = [i for i in range(n+1)]
demi = [1] * (n+1)
 
 
for i,j in bff:
    x = par[i]
    y = par[j]
    while x != par[x]:
        x = par[x]
    while y != par[y]:
        y = par[y]
    if(x == y):
        continue
    
    if rank[x] < rank[y]:
        par[x] = y
        demi[y] += demi[x]
        
    else:
        par[y] = x
        demi[x] += demi[y]
        
        if rank[x] == rank[y]:
             rank[x] += 1
 
 
for i in range(n):
    x = par[i+1]
    while x!=par[x]:
        x = par[x]
    par[i+1] = x
 
 
for i in range(n):
    x = par[i+1]
    while x!=par[x]:
        x = par[x]
    demi[i+1] = demi[x]
 
 
 
a = list(chain.from_iterable(bff))
b = list(chain.from_iterable(blk))
 
fqua = [0] * n
bqua = [0] * n
 
for i,j in bff:
    if(par[i] == par[j]):
        fqua[i-1] += 1
        fqua[j-1] += 1
 
for i,j in blk:
    if(par[i] == par[j]):
        bqua[i-1] += 1
        bqua[j-1] += 1
 
for i in range(n):
    print(demi[i+1] - fqua[i] - bqua[i] - 1 ,end=" ")

Solution (Python):
from collections import defaultdict

N, M, K = map(int, input().split())
friends = defaultdict(list)
blocked = defaultdict(list)

for i in range(M):
    a, b = map(int, input().split())
    friends[a - 1].append(b - 1)
    friends[b - 1].append(a - 1)
for j in range(K):
    c, d = map(int, input().split())
    blocked[c - 1].append(d - 1)
    blocked[d - 1].append(c - 1)

groups = {}
for i in range(N):
    if i in groups:
        continue
    group = {i}
    stack = [(i, None)]
    while stack:
        j, parent_id = stack.pop()
        group.add(j)
        groups[j] = group
        for k in friends[j]:
            if k != parent_id and k not in groups:
                stack.append((k, j))

ans = []
for i in range(N):
    g = groups[i]
    res = len(g) - len(friends[i]) - 1
    for b in blocked[i]:
        if groups[b] is g:
            res -= 1
    ans.append(res)
print(*ans)

Solution (Python):
from collections import defaultdict

N, M, K = map(int, input().split())
friends = defaultdict(list)
blocked = defaultdict(list)

for i in range(M):
    a, b = map(int, input().split())
    friends[a - 1].append(b - 1)
    friends[b - 1].append(a - 1)
for j in range(K):
    c, d = map(int, input().split())
    blocked[c - 1].append(d - 1)
    blocked[d - 1].append(c - 1)


class UF:
    def __init__(self, node_id):
        self.node_id = node_id
        self._root = self
        self._size = 1

    @property
    def root(self):
        p = self._root
        while p is not p._root:
            p = p._root
        q = self
        while q._root is not p:
            r = q._root
            q._root = p
            q = r
        return p

    @property
    def size(self):
        return self.root._size

    def merge(self, other):
        if self.root.node_id == other.root.node_id:
            return self.root
        elif self.root.node_id < other.root.node_id:
            self.root._size += other.root._size
            other._root = self.root
            return self.root
        else:
            other.root._size += self.root._size
            self._root = other.root
            return other.root


sets = [UF(i) for i in range(N)]
visited = set()
for i in range(N):
    if i in visited:
        continue
    r = sets[i]
    stack = [(i, None)]
    while stack:
        j, parent_id = stack.pop()
        if j in visited:
            continue
        visited.add(j)
        for k in friends[j]:
            if k != parent_id:
                r = r.merge(sets[k])
                if k not in visited:
                    stack.append((k, j))

ans = []
for i in range(N):
    res = sets[i].size - len(friends[i]) - 1
    root_id = sets[i].root.node_id
    for b in blocked[i]:
        if sets[b].root.node_id == root_id:
            res -= 1
    ans.append(res)
print(*ans)

Solution (Python):
from collections import deque
import sys
import time
def input(): return sys.stdin.readline().strip()

DEBUG = False

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

friend_relations = [[] for _ in range(N+1)]
block_relations = [[] for _ in range(N+1)]

num_connected_friends = [0] * (N+1)
num_connected_blocks = [0] * (N+1)

for _ in range(M):
    A, B = map(int, input().split())
    friend_relations[A].append(B)
    friend_relations[B].append(A)

for _ in range(K):
    C, D = map(int, input().split())
    block_relations[C].append(D)
    block_relations[D].append(C)

if DEBUG:
    print("friend_relations:")
    for i, row in enumerate(friend_relations):
        print("node: {}, relation: {}".format(i, row))
    print("block_matrix:")
    for i, row in enumerate(block_relations):
        print("node: {}, relation: {}".format(i, row))

count = 0
labels = [-1] * (N+1)
graph_sizes = []
total_iteration = 0
for n in range(1, N+1):
    if DEBUG:
        print("root_node: {}, count: {}".format(n, count))
    if labels[n] == -1:
        queue = deque([n])
        labels[n] = count
        size = 0
        while queue:
            if DEBUG:
                print("queue:{}".format(queue))
            node = queue.popleft()
            size += 1
            if DEBUG:
                print("node:{}".format(node))
            for next_node in friend_relations[node]:
                total_iteration += 1
                if labels[next_node] == -1:
                    labels[next_node] = count
                    queue.append(next_node)
            if DEBUG:
                print("labels: {}".format(labels))
            
        count += 1
        graph_sizes.append(size)
if DEBUG:
    print("total_iteration: {}".format(total_iteration))
    print("labels: {}".format(labels))
    print("graph_sizes: {}".format(graph_sizes))

friend_candidate = [0] * (N+1)
for n in range(1, N+1):
    num_block = sum([1 for i in block_relations[n] if labels[n] == labels[i]])
    num_frined = len(friend_relations[n])
    if DEBUG:
        print("node: {}, num_frined: {}, num_block: {}".format(n+1, num_frined, num_block))
    friend_candidate[n] = graph_sizes[labels[n]] - num_frined - num_block - 1

print(*friend_candidate[1:])

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


class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * self.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 False
    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 get_node_members(self):
    return [[j for j in range(self.n) if self.issame(i, j)] for i in range(self.n)]
  
  def size(self, x):
    return -self.parents[self.find(x)]
  
N = list(map(int, input().split()))
uf = UnionFind(N[0])
results = [0 for i in range(N[0])]
for i in range(N[1]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x] += 1
  results[y] += 1
  uf.union(x, y)


for i in range(N[2]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  if uf.issame(x, y):
  	results[x] += 1
  	results[y] += 1
  



print(" ".join([str(uf.size(i) - results[i] - 1) for i in range(N[0])]))

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


class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * self.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 False
    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 get_node_members(self):
    return [[j for j in range(self.n) if self.issame(i, j)] for i in range(self.n)]
  
  def size(self, x):
    return -self.parents[self.find(x)]

N = list(map(int, input().split()))
parents = [-1] * N[0]
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 False
  if parents[x] > parents[y]:
    x, y = y, x
  parents[x] += parents[y]
  parents[y] = x
        
def issame(x, y):
  return find(x) == find(y)
  
def size(x):
  return -parents[find(x)]
  

results = [0 for i in range(N[0])]
for i in range(N[1]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x] += 1
  results[y] += 1
  union(x, y)


for i in range(N[2]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  if issame(x, y):
  	results[x] += 1
  	results[y] += 1
  


print(" ".join([str(size(i) - results[i] - 1) for i in range(N[0])]))

Solution (Python):
from collections import deque
N,M,K = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]
friends = [set() for _ in range(N)]
blocks = [set() for _ in range(N)]
searched = [0] * N
ans = [0] * N
d = deque()
for x, y in AB:
    friends[x-1].add(y-1)
    friends[y-1].add(x-1)
for x, y in CD:
    blocks[x-1].add(y-1)
    blocks[y-1].add(x-1)
for i in range(N):
    if searched[i]:
        continue
    trace = set()
    d.append(i)
    trace.add(i)
    searched[i] = 1
    while d:
        temp = d.popleft()
        for x in friends[temp]:
            if searched[x] == 0:
                d.append(x)
                trace.add(x)
                searched[x] = 1
    chain = len(trace)
    for j in trace:
        ans[j] = chain - 1 - len(trace&friends[j]) - len(trace&blocks[j])
print(*ans)

Solution (Python):
import sys
sys.setrecursionlimit(2 ** 30)
N, M, K = map(int, input().split())

groups = [None] * N
visited = set()


def dfs(group, i):
  if i in visited:
    return
  
  visited.add(i)
  group.add(i)
  groups[i] = group
  
  for c in graph[i]:
    if not c in visited:
      dfs(group, c)
  

graph = [set() for _ in range(N)]

friends_count = [0] * N
block_count = [0] * N

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  friends_count[a] += 1
  friends_count[b] += 1
  graph[a].add(b)
  graph[b].add(a)
  
for i in range(N):
  dfs(set(), i)
      
for _ in range(K):
  c, d = map(int, input().split())
  c, d = c - 1, d - 1
  
  
  if d in groups[c]:
    block_count[c] += 1
    block_count[d] += 1

candidates = []

for i in range(N): 
  candidates.append(
    len(groups[i]) - friends_count[i] - block_count[i] - 1
  )
    
print(' '.join(str(x) for x in candidates))

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

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

uf = UnionFind(N)
for i in range(M):
    uf.union(AB[i][0]-1,AB[i][1]-1)
pot = [uf.size(i)-1 for i in range(N)]
for i in range(M):
    A,B = AB[i][0],AB[i][1]
    if uf.find(A-1) == uf.find(B-1):
        pot[A-1] -= 1
        pot[B-1] -= 1
for i in range(K):
    C,D = CD[i][0],CD[i][1]
    if uf.find(C-1) == uf.find(D-1):
        pot[C-1] -= 1
        pot[D-1] -= 1
print(*pot)

Solution (Python):
class UnionFind(object):
    def __init__(self, n=1):
        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]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            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())

friend = [[] for _ in range(n)]
block = [[] for _ in range(n)]

uf = UnionFind(n)

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

    uf.union(a-1, b-1)

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

candidate = [0] * n

for i in range(n):
    candidate[i] = uf.get_size(i) - len(friend[i]) - 1
    for j in block[i]:
        if uf.is_same(i, j):
            candidate[i] -= 1

print(' '.join(list(map(str, candidate))))

Solution (Python):
from itertools import chain

n,m,k = map(int,input().split())
 
bff = [list(map(int,input().split())) for i in range(m)]
 
blk = [list(map(int,input().split())) for i in range(k)]


rank = [0] * (n+1)
par = [i for i in range(n+1)]
demi = [1] * (n+1)


for i,j in bff:
    x = par[i]
    y = par[j]
    while x != par[x]:
        x = par[x]
    while y != par[y]:
        y = par[y]
    if(x == y):
        continue
    
    if rank[x] < rank[y]:
        par[x] = y
        demi[y] += demi[x]
        
    else:
        par[y] = x
        demi[x] += demi[y]
        
        if rank[x] == rank[y]:
             rank[x] += 1


for i in range(n):
    x = par[i+1]
    while x!=par[x]:
        x = par[x]
    par[i+1] = x


for i in range(n):
    x = par[i+1]
    while x!=par[x]:
        x = par[x]
    demi[i+1] = demi[x]



a = list(chain.from_iterable(bff))
b = list(chain.from_iterable(blk))

fqua = [0] * n
bqua = [0] * n
 
for i,j in bff:
    if(par[i] == par[j]):
        fqua[i-1] += 1
        fqua[j-1] += 1

for i,j in blk:
    if(par[i] == par[j]):
        bqua[i-1] += 1
        bqua[j-1] += 1

for i in range(n):
    print(demi[i+1] - fqua[i] - bqua[i] - 1 ,end=" ")

Solution (Python):
class union_find:
    def __init__(self, N):
        
        self.par = [-1 for i in range(N)]
        self.excluded = [0 for i in range(N)]
    
    def root(self, a):
        if self.par[a] < 0:
            return a
        else:
            
            self.par[a] = self.root(self.par[a])
            return self.par[a]
    
    def unite(self, a, b):
        ar = self.root(a)
        br = self.root(b)
        if ar == br:
            return
        if self.par[ar] > self.par[br]:
            ar, br = br, ar
        self.par[ar] += self.par[br]
        self.par[br] = ar
    
    def friend(self, a, b):
        self.unite(a, b)
        self.excluded[a] += 1
        self.excluded[b] += 1
    
    def block(self, a, b):
        ar = self.root(a)
        br = self.root(b)
        if ar != br:
            return
        self.excluded[a] += 1
        self.excluded[b] += 1
    
    def get_friend_sugestion_size(self, a):
        return -self.par[self.root(a)] - 1 - self.excluded[a]

N, M, K = map(int, input().split())
UF = union_find(N)
for i in range(M):
    A, B = map(int, input().split())
    UF.friend(A-1, B-1)
for i in range(K):
    A, B = map(int, input().split())
    UF.block(A-1, B-1)
print(*[UF.get_friend_sugestion_size(x) for x in range(N)])

Solution (Python):
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def main():
    N, M, K = map(int, input().split())
    gf = [[] for _ in range(N)]
    gb = []
    for _ in range(M):
        a, b = [int(i) - 1 for i in input().split()]
        gf[a].append(b)
        gf[b].append(a)
    for _ in range(K):
        c, d = [int(i) - 1 for i in input().split()]
        gb.append((c, d))
    friend = defaultdict(int)
    ans = [0] * N
    par = [None] * N
    
    def dfs(v):
        if par[v] is None:  
            par[v] = v
            friend[par[v]] += 1
        for u in gf[v]:  
            if par[u] is None:  
                par[u] = par[v]
                friend[par[v]] += 1
                dfs(u)  
    
    for i in range(N):
        if par[i] is None:
            dfs(i)
    for i in range(N):  
        ans[i] += friend[par[i]] - len(gf[i]) - 1
    for c, d in gb:
        if par[c] == par[d]:  
            ans[c] -= 1
            ans[d] -= 1
    print(*ans)


if __name__ == '__main__':
    main()

Solution (Python):
class UnionFindTree:
    """
    Union Find Tree

    Attributes
    ----------
    _parents : list
        Parents of each nodes.
        A parent of a root node is -1.
    _size : int
        The number of nodes of the tree
    _rank : int
        The size of a tree to which each root belongs to.
        If the node is not root, this rank might be incollect.
    """

    def __init__(self, size):
        """
        Parameters
        ----------
        size : int
            The number of nodes of the tree
        """
        self._size = size
        self._parents = [-1 for i in range(size)]
        self._rank = [1 for i in range(size)]

    def find(self, node):
        """
        Return the root of the node.
        If the node is root and have no parent, then return the node itself.

        Parameters
        ----------
        node : int
            A node whose parent will be returned.

        Returns
        -------
        root : int
            A parent of the node.
        """
        if self._parents[node] == -1:
            return node
        else:
            root = self.find(self._parents[node])
            self._parents[node] = root
            return root

    def union(self, node1, node2):
        """
        Unite two trees

        Parameters
        ----------
        node1 : int
            The first tree that will be united includes this node.
        node2 : int
            The first tree that will be united includes this node.
        """
        root1 = self.find(node1)
        root2 = self.find(node2)
        if root1 == root2:
            
            return
        rank1 = self._rank[root1]
        rank2 = self._rank[root2]
        if rank1 < rank2:
            self._parents[root1] = root2
            self._rank[root2] += rank1
        else:
            self._parents[root2] = root1
            self._rank[root1] += rank2

    def are_same(self, node1, node2):
        """
        Judges if two nodes belong to the same tree or not.

        Parameters
        ----------
        node1 : int
            The first node.
        node2 : int
            The second node.

        Returns
        : boolean
            If two nodes belong to the same tree or not.
        -------

        """
        if self.find(node1) == self.find(node2):
            return True
        else:
            return False

    def members_size(self, node):
        """
        Return the number of nodes that belong to the same tree include itself.

        Parameters
        ----------
        node

        Returns
        -------
        : int

        """
        return self._rank[self.find(node)]


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

friends = []
for m in range(M):
    A, B = map(int, input().split())
    t.union(A - 1, B - 1)
    friends.append([A, B])

potential_friends = [t.members_size(n) - 1 for n in range(N)]
for m in range(M):
    A, B = friends[m]
    if t.find(A - 1) == t.find(B - 1):
        potential_friends[A - 1] -= 1
        potential_friends[B - 1] -= 1

for k in range(K):
    C, D = map(int, input().split())
    if t.find(C - 1) == t.find(D - 1):
        potential_friends[C - 1] -= 1
        potential_friends[D - 1] -= 1

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