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

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1


class UnionFind:
    __slots__ = ['id','sz']

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

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

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

    def union(self, x, y):
        s1, s2 = self.root(x), self.root(y)
        if s1 != s2:
            if self.id[s1] <= self.id[s2]:
                self.id[s1] += self.id[s2]
                self.id[s2] = s1
            else:
                self.id[s2] += self.id[s1]
                self.id[s1] = s2
            self.sz-=1
            return True
        return False


n,m,k = map(int,input().split())
uf=UnionFind(n)
S = [[] for i in range(n)]
for i in range(m):
  a,b = map(int,input().split())
  a-=1;b-=1
  uf.union(a,b)
  S[a].append(b)
  S[b].append(a)
for i in range(k):
  a,b = map(int,input().split())
  a-=1;b-=1
  S[a].append(b)
  S[b].append(a)
ans = [0] * n
for i in range(n):
  tmp = (-uf.id[uf.root(i)])-1
  for vi in S[i]:
    if uf.find(i,vi):
      tmp -= 1
  ans[i] = tmp
print(*ans)

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


class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

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

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


N, M, K = map(int, input().split())
uf = UnionFind(N)
friend = [0] * N
for _ in range(M):
    A, B = map(lambda x: int(x)-1, input().split())
    friend[A] += 1
    friend[B] += 1
    uf.unite(A, B)
block = [0] * N
for _ in range(K):
    C, D = map(lambda x: int(x)-1, input().split())
    if uf.same(C, D):
        block[C] += 1
        block[D] += 1
counter = defaultdict(int)
for i in range(N):
    counter[uf.find(i)] += 1
ans = [0] * N
for i in range(N):
    ans[i] = counter[uf.find(i)] - friend[i] - block[i] - 1
print(' '.join(map(str, ans)))

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

root = [i for i in range(N + 1)]
comp_size = [1] * (N+1)
 
def root_find(x):
  y = root[x]
  if x == y:
    return x
  else:
    z = root_find(y)
    root[x] = z
    return z

def merge(x, y):
  
  rx = root_find(x)
  ry = root_find(y)
  sx = comp_size[rx]
  sy = comp_size[ry]
  if rx == ry:
    return 0
  else:
    if sx >= sy:
      root[ry] = rx
      comp_size[rx] = sx + sy
    else:
      root[rx] = ry
      comp_size[ry] = sx + sy
    return sx * sy
    
for a, b in AB:
    merge(a, b)



answer = []
for i in range(N + 1):
    answer.append(comp_size[root_find(i)] - 1)


for a, b in AB:
    if root_find(a) == root_find(b):
        answer[a] -= 1
        answer[b] -= 1
for c, d in CD:
    if root_find(c) == root_find(d):
        answer[c] -= 1
        answer[d] -= 1
print(*answer[1:])

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')


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

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

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        
        
        
        if root_x != root_y:
            
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root

def main():
    N,M,K=MI()
    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    
    friend_cnt = [0]*N
    ans = [0]*N
    for _ in range(M):
        a,b = MI_()
        unite(a,b)
        friend_cnt[a]+=1
        friend_cnt[b]+=1
    for i in range(N):
        ans[i] = -nodes[get_root(i)]-1-friend_cnt[i]
    for _ in range(K):
        a,b = MI_()    
        if get_root(a)==get_root(b):
            ans[a]-=1
            ans[b]-=1
    print(*ans)
    
if __name__ == '__main__':
    main()

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

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




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

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


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


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


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


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


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


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



par = [-1]*n
lst2 = [0]*n
lst3 = [0]*n
for i in range(m):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    lst2[a] += 1
    lst2[b] += 1
    unite(a,b)

block = 0

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

ans = [0]*n

for i in range(n):
    res = size(i) -1
    res -= lst2[i]+lst3[i]
    ans[i] = res


print(*ans)

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


N, M, K = map(int, input().split())
U = UnionFind(N)
res = [0 for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    res[a - 1] -= 1
    res[b - 1] -= 1
    U.union(a - 1, b - 1)


for _ in range(K):
    c, d = map(int, input().split())
    if U.same(c - 1, d - 1):
        res[c - 1] -= 1
        res[d - 1] -= 1
for i in range(N):
    res[i] += U.size(i) - 1
print(" ".join(map(str, res)))

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

import sys
sys.setrecursionlimit(10**7)

class UnionFind:
    def __init__(self,N):
        self.Parent = list(range(N))
    def get_Parent(self,n):
        if self.Parent[n] == n:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y: self.Parent[y] = x
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

U = UnionFind(N)
E_f = [[] for _ in [0]*N]
for a,b in AB:
    a -= 1
    b -= 1
    U.merge(a,b)
    E_f[a].append(b)
    E_f[b].append(a)
group = [set() for _ in [0]*N]
for i in range(N):
    p = U.get_Parent(i)
    group[p].add(i)

E_b = [[] for _ in [0]*N]
for c,d in CD:
    c -= 1
    d -= 1
    E_b[c].append(d)
    E_b[d].append(c)

ans = [0]*N
for i in range(N):
    p = U.get_Parent(i)
    cnt = 0
    for b in E_b[i]:
        if b in group[p]: cnt += 1
    ans[i] = len(group[p]) -cnt - len(E_f[i]) - 1

print(*ans)

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


class UnionFind():
    """
    parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
    find(x):要素xの属するグループの根を返す
    size(x):要素xの属するグループの要素数を返す
    same(x,y):x,yが同じグループに属しているか返す
    members(x):要素xが属するグループに属する要素をリストで返す
    roots:全ての根の要素を返す
    group_count():グループの数を返す
    all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
    """
    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():
    mod=10**9+7
    N,M,K=MI()
    uf = UnionFind(N)
    cnt=[0]*N
    for i in range(M):
        a,b=MI()
        a-=1
        b-=1
        cnt[a]+=1
        cnt[b]+=1
        uf.union(a,b)
        
    blo=[0]*N
    for i in range(K):
        c,d=MI()
        c-=1
        d-=1
        if uf.same(c,d):
            blo[c]+=1
            blo[d]+=1
    ans=[0]*N    
    for i in range(N):
        ans[i]=uf.size(i) - cnt[i]-blo[i]-1
        
    print(' '.join(map(str, ans)))
        
    

main()

Solution (Python):
class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in range(n)]
        self.rank = [0] * 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 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.parent[y] = x
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)


N, M, K = map(int, input().split())
uf = UnionFind(N)
count_friends = [1] * N
for i in range(M):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
  count_friends[a-1] += 1
  count_friends[b-1] += 1


parents = [uf.find(i) for i in range(N)]
par_dict = {}
for p in parents:
  if p in par_dict:
    par_dict[p] += 1
  else:
    par_dict[p] = 1

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

ans = [-1]*N
for i in range(N):
  p = parents[i]
  ans[i] = par_dict[p] - count_friends[i] - count_block[i]

print(*ans)

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]


N, M, K, *ABCD = map(int, open(0).read().split())
AB, CD = ABCD[:2 * M], ABCD[2 * M:]

E = [[] for _ in range(N + 1)]
uf = UnionFind(N + 1)
for a, b in zip(*[iter(AB)] * 2):
    uf.union(a, b)
    E[a].append(b)
    E[b].append(a)

B = [[] for _ in range(N + 1)]
for c, d in zip(*[iter(CD)] * 2):
    B[c].append(d)
    B[d].append(c)

A = []
for i in range(1, N + 1):
    A.append(uf.size(i) - 1 - len(E[i]) - sum(1 for b in B[i] if uf.same(b, i)))

print(*A)

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

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))




class UF(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*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 = LI()
A,B = LIR(M,2)
C,D = LIR(K,2)

b = defaultdict(set)
t = defaultdict(set)

uf = UF(N)

for i in range(M):
    uf.union(A[i]-1,B[i]-1)
    t[A[i]-1].add(B[i]-1)
    t[B[i]-1].add(A[i]-1)

num = [0]*N
for i in range(K):
    if uf.is_same(C[i]-1, D[i]-1):
        num[C[i]-1] -= 1
        num[D[i]-1] -= 1

ans = []
for i in range(N):
    ans.append(uf.get_size(i)-1-len(t[i])+num[i])
print(*ans)

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

e_list = [[] for i in range(N)]

b_list = [[] for i in range(N)]

edge1 = []
edge2 = []
for i in range(M):
    a,b = list(map(int,input().split()))
    a,b = a-1,b-1
    edge1.append((a,b))
    e_list[a].append(b)
    e_list[b].append(a)

for i in range(K):
    a,b = list(map(int,input().split()))
    a,b = a-1,b-1
    edge2.append((a,b))
    b_list[a].append(b)
    b_list[b].append(a)

color = [-1]*N

from collections import deque

def BFS(vi,c):
    Q = deque([vi])
    color[vi]=c
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if color[v1]==-1:
                color[v1]=c
                Q.appendleft(v1)

c=0

for i in range(N):
    if color[i]==-1:
        BFS(i,c)
        c+=1

member = [0]*(max(color)+1)

for i in range(N):
    member[color[i]]+=1

ans = []
for i in range(N):
    a = member[color[i]] -1 - len(e_list[i]) 
    for j in range(len(b_list[i])):
        if color[i]==color[b_list[i][j]]:
            a-=1

    ans.append(a)

print(*ans)

"""
good = [0]*(max(color)+1)
bad = [0]*(max(color)+1)
for i in range(M):
    good[color[edge1[i][0]]]+=1

for i in range(K):
    bad[color[edge2[i][0]]]+=1

ans = 0
for i in range(len(member)):
    ans += (member[i]*(member[i]-1))//2 - good[i] - bad[i]

print(ans)
"""

Solution (Python):
import math
import heapq
import bisect
from collections import defaultdict, Counter, deque
import sys

def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (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:
            return
        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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    def update_all(self):
        n = len(self.par)
        for i in range(n):
            self.par[i] = self.find(i)

def main():
    n, m, k = getList()
    friends = [[] for i in range(n)]
    blocks = [[] for i in range(n)]

    uf = UnionFind(n)

    for i in range(m):
        a, b = getList()
        uf.union(a-1, b-1)
        friends[a-1].append(b-1)
        friends[b-1].append(a-1)

    for i in range(k):
        a, b = getList()
        blocks[a-1].append(b-1)
        blocks[b-1].append(a-1)
    uf.update_all()
    
    ans = []
    for i in range(n):
        tmp = uf.size[uf.par[i]]
        for fr in friends[i]:
            if uf.same_check(i, fr):
                tmp -= 1
        for bl in blocks[i]:
            if uf.same_check(i, bl):
                tmp -= 1

        ans.append(tmp-1)

    print(*ans)


if __name__ == "__main__":
    main()

"""
10
203941992 742164984
670850202 743524472
687298546 744891559
676493045 744182895
385467254 742631752
740505911 744926772
425723256 743348462
225362543 742332848
399450535 742706299
563528474 743419738
"""

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

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

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

friend=[0 for i in range(n+1)]
blocked={i:[] for i in range(1,n+1)}
for i in range(m):
    a,b=map(int,input().split())
    friend[a]+=1
    friend[b]+=1
    A.union(a,b)
    
    
for j in range(k):
    x,y=map(int,input().split())
    
    blocked[x].append(y)
    blocked[y].append(x)
    
for i in range(1,n+1):
    A.find(i)
    
parent=A.par

howmany={i:0 for i in range(n+1)}

for i in range(1,n+1):
    x=parent[i]
    howmany[parent[i]]+=1
    


lists=[]
for i in range(1,n+1):
    sums=howmany[parent[i]]-1-friend[i]
    for some in blocked[i]:
        if parent[i]==parent[some]:
            sums-=1
    lists.append(sums)
print(*lists)

Solution (Python):
from collections import defaultdict
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.size = [1]*n
    self.rank = [0]*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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      self.size[y] += self.size[x]
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
      self.size[x] += self.size[y]
    else:
      self.par[y] = x
      self.size[x] += self.size[y]
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
  def count(self, x):
    return self.size[x]
N, M, K = map(int, input().split())
frend = defaultdict(list)
F = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  frend[a] += [b]
  frend[b] += [a]
  F.unit(a-1,b-1)
ans = [0]*N
for i in range(N):
  p = F.find(i)
  X = F.count(p)
  ans[i] = X-len(frend[i+1])-1
for i in range(K):
  a, b = map(int, input().split())
  if F.same(a-1,b-1):
    ans[a-1] -= 1
    ans[b-1] -= 1

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

Solution (Python):
class UnionFind:
    def __init__(self, n):
        
        self.par = [i for i in range(n+1)]
        
        self.rank = [0] * (n+1)
        
        self.count = [1] * (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):
        if UnionFind.same_check(self,x,y):
            return
        x = self.find(x)
        y = self.find(y)
        t = (x == y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return t


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

    
    def size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]

n,m,k = map(int,input().split())
u = UnionFind(n)
friend = [1 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    friend[a] += 1
    friend[b] += 1
    u.union(a,b)

ans = [u.size(i)-friend[i] for i in range(n)]

for i in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if u.same_check(c,d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Solution (Python):

class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
N,M,K = list(map(int,input().split()))
uf = UnionFind(N)
fr = [0]*(N+1)
for i in range(M):
    [x_tmp,y_tmp] = list(map(int,input().split()))
    uf.Unite(x_tmp,y_tmp)
    fr[x_tmp] += 1
    fr[y_tmp] += 1
ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = uf.Count(i) - fr[i] - 1
for j in range(K):
    [x_tmp,y_tmp] = list(map(int,input().split()))
    if uf.isSameGroup(x_tmp,y_tmp):
        ans[x_tmp] -= 1
        ans[y_tmp] -= 1
print(' '.join(list(map(str,ans[1::]))))

Solution (Python):
n, m, k = [int(i) for i in input().split()]
ro = [-1] * n
r = [0] * n
co = [1] * n
ab = []
for _ in range(m):
    a, b = [int(i) - 1 for i in input().split()]
    ab.append([a, b])
    while ro[a] != -1:
        a = ro[a]
    while ro[b] != -1:
        b = ro[b]
    if a != b:
        if r[a] > r[b]:
            ro[b] = a
            r[a] = max(r[a], r[b] + 1)
            co[a] += co[b]
        else:
            ro[a] = b
            r[b] = max(r[b], r[a] + 1)
            co[b] += co[a]
ans = []
for i in range(n):
    while ro[i] != -1:
        i = ro[i]
    ans.append(co[i]-1)
for a, b in ab:
    ans[a] -= 1
    ans[b] -= 1

for _ in range(k):
    c, d = [int(i) - 1 for i in input().split()]
    e, f = c, d
    while ro[c] != -1:
        c = ro[c]
    while ro[d] != -1:
        d = ro[d]
    if c == d:
        ans[e] -= 1
        ans[f] -= 1


print(" ".join(list(map(str, ans))))

Solution (Python):
class UnionFind:
    def __init__(self, N):
        
        
        
        self.p = [-1 for i in range(N)]

    def find(self, i):
        
        if self.p[i] >= 0:
            self.p[i] = self.find(self.p[i])
            return self.p[i]
        else:
            return i

    def union(self, i, j):
        
        root1 = self.find(j)
        root2 = self.find(i)
        if root1 == root2:
            return
        size1 = -self.p[root1]
        size2 = -self.p[root2]
        if size1 < size2:
            self.p[root1] = root2
            self.p[root2] = -(size1 + size2)
        else:
            self.p[root2] = root1
            self.p[root1] = -(size1 + size2)

    def getComponentSize(self, i):
        return -self.p[self.find(i)]


from collections import defaultdict

N, M, K = list(map(int, input().split()))
friend = defaultdict(set)
for i in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    friend[a].add(b)
    friend[b].add(a)
block = defaultdict(set)
for i in range(K):
    c, d = list(map(int, input().split()))
    c -= 1
    d -= 1
    block[c].add(d)
    block[d].add(c)

uf = UnionFind(N)
for a, friends in friend.items():
    for b in friends:
        uf.union(a, b)

out = []
for a in range(N):
    count = uf.getComponentSize(a) - 1 - len(friend[a])
    for b in block[a]:
        if uf.find(a) == uf.find(b):
            count -= 1
    out.append(str(count))
print(" ".join(out))

Solution (Python):
n,m,k=map(int,input().split())
edge=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
blist=[[] for i in range(n+1)]
for i in range(k):
    a,b=map(int,input().split())
    blist[a].append(b)
    blist[b].append(a)
ans=[-1]*(n+1)
for i in range(1,n+1):
    if ans[i]==-1:
        s=set([i])
        q=[i]
        while q:
            for j in edge[q.pop()]:
                if j not in s:
                    s.add(j)
                    q.append(j)
        for j in s:
            tmp=len(s)-len(edge[j])-1
            for k in blist[j]:
                if k in s:
                    tmp-=1
            ans[j]=tmp
print(" ".join(map(str,ans[1:])))