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.parent = [-1] * n

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

    def size(self, a):
        return -self.parent[self.root(a)]

    def connect(self, a, b) -> bool:
        a = self.root(a)
        b = self.root(b)

        if a == b:
            return False

        if self.size(a) < self.size(b):
            a, b = b, a

        self.parent[a] += self.parent[b]

        self.parent[b] = a

        return True


N, M, K = map(int, input().split())
fri_g = dict([str(i), []] for i in range(N))
blk_g = dict([str(i), []] for i in range(N))
unif = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    unif.connect(a-1, b-1)
    fri_g[str(a-1)].append(b-1)
    fri_g[str(b-1)].append(a-1)

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

for i in range(N):
    i_str = str(i)
    n_link = unif.size(i) - 1  
    n_friends = len(fri_g[i_str])
    n_blk_and_link = sum([unif.root(d) == unif.root(i) for d in blk_g[i_str]])
    
    
    

    print(n_link - n_friends - n_blk_and_link)

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

























def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007




def main():
	N,M,K = inputMap()
	UF = UnionFind(N)
	AB = {}
	for i in range(N):
		AB[i] = []
	for i in range(M):
		a,b = inputMap()
		a -= 1
		b -= 1
		UF.union(a, b)
		if a in AB:
			AB[a].append(b)

		if b in AB:
			AB[b].append(a)

	CD = {}
	for i in range(N):
		CD[i] = []
	for i in range(K):
		c,d = inputMap()
		c -= 1
		d -= 1
		if c in CD:
			CD[c].append(d)

		if d in CD:
			CD[d].append(c)

	ans = []
	for i in range(N):
		tmp = UF.getSize(i) - len(AB[i]) -1
		for j in CD[i]:
			if UF.is_same(i, j):
				tmp -= 1
		ans.append(tmp)

	print(*ans)








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:
			
			sum = self.size[x] + self.size[y]
			self.size[x] = sum
			self.size[y] = sum
			
			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

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

	
	def getSize(self, x):
		par_x = self.find(x)
		return self.size[par_x]




def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.readline
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):
        """
        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 と 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[y] += 1
            self.par[x] = y
            self.size[y] += self.size[x]

    def same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]


n,m,k=map(int,input().split())
tomo=[[] for _ in range(n)]
blo=[[] for _ in range(n)]
tomouf=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    tomo[a].append(b)
    tomo[b].append(a)
    tomouf.union(a,b)
for i in range(k):
    a,b=map(int,input().split())
    a-=1
    b-=1
    blo[a].append(b)
    blo[b].append(a)
aans=[]
for i in range(n):
    ans=tomouf.get_size(i)
    for j in tomo[i]:
        if tomouf.same(i,j):
            ans-=1
    for j in blo[i]:
        if tomouf.same(i,j):
            ans-=1
    aans.append(ans-1)
print(*aans)

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 same(self, 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)
friend = [0] * (n+1)
block = [0] * (n+1)

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

for _ in range(k):
    c, d = map(int, input().split())
    if uf.same(c-1, d-1):
        block[c] += 1
        block[d] += 1

w = [0] * (n+1)

for i in range(1, n+1):
    w[i] = uf.size(i-1) - friend[i] - block[i] - 1

print(*w[1:])

Solution (Python):
class UnionFind:
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rnk = [0]*(n+1)
		self.Maxroot = -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]
			if self.root[x] < self.Maxroot:
				self.Maxroot = self.root[x]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			if self.root[y] < self.Maxroot:
				self.Maxroot = self.root[y]
			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)] * (-1)

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

solve = UnionFind(N)
cntF = [0] * (N)

for _ in range(M):
	ta,tb = map(int, input().split())
	ta -= 1
	tb -= 1
	cntF[ta] += 1
	cntF[tb] += 1
	solve.Unite(ta,tb)

for _ in range(K):
	tc,td = map(int, input().split())
	tc -= 1
	td -= 1
	if solve.isSameGroup(tc,td):
		cntF[tc] += 1
		cntF[td] += 1

ans = []
for i in range(N):
	ans.append(solve.Count(i) - cntF[i] - 1)
print(*ans)

Solution (Python):
from collections import Counter


def same_group():
    class UnionFind(object):
        def __init__(self, n):
            self.par = [i for i in range(n)]
            self.rank = [0 for _ in range(n)]

        def find(self, x):
            if self.par[x] != x:
                self.par[x] = self.find(self.par[x])
            return self.par[x]

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

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

    uf = UnionFind(N)
    friends = {i: 0 for i in range(N)}
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if uf.find(a) != uf.find(b):
            uf.unite(a, b)

        friends[a] += 1
        friends[b] += 1

    for i in range(N):
        uf.find(i)

    num_per_group = Counter(uf.par)

    blocks = {i: 0 for i in range(N)}
    for _ in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        if uf.par[c] == uf.par[d]:
            blocks[c] += 1
            blocks[d] += 1

    print(*[max(num_per_group[uf.par[i]] - friends[i] - blocks[i] - 1, 0) for i in range(N)])


same_group()

Solution (Python):
n,m,k = map(int,input().split())
num = [1 for _ in range(n)]
pre = [i for i in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  A = [a]
  B = [b]
  la = 1
  lb = 1
  while a != pre[a]:
    a = pre[a]
    A.append(a)
    la += 1
  while b != pre[b]:
    b = pre[b]
    B.append(b)
    lb += 1
  
  if a != b:
    if la > lb:
      pre[b] = a
      for aa in A:
        pre[aa] = a
      for bb in B:
        pre[bb] = a
    else:
      pre[a] = b
      for aa in B:
        pre[aa] = b
      for bb in B:
        pre[bb] = b
root = [10**6 for _ in range(n)]
cnt = [0 for _ in range(n)]
for i in range(n):
  if root[i] < 10**6:
    cnt[root[i]] += 1
    continue
  I = int(i)
  J = [I]
  while I != pre[I]:
    I = pre[I]
    J.append(I)
  for x in J:
    root[x] = I
  cnt[I] += 1



ans = []
for i in range(n):
  ans.append(cnt[root[i]]-num[i])

for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    ans[a] -= 1
    ans[b] -= 1
print(' '.join(map(str,ans)))

Solution (Python):
n,m,k=map(int, input().split( ))
F = [tuple(map(int, input().split( ))) for _ in range(m)]
B = [tuple(map(int, input().split( ))) for _ in range(k)]
Fx = [[] for i in range(n+1)]
Bx = [[] for i in range(n+1)]
for a,b in F:
    Fx[a].append(b)
    Fx[b].append(a)
for a,b in B:
    Bx[a].append(b)
    Bx[b].append(a)




*p, = range(n+1)
rank = [1]*(n+1)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    rx = rank[px]; ry = rank[py]
    if ry < rx:
        p[py] = px
    elif rx < ry:
        p[px] = py
    else:
        p[py] = px
        rank[px] += 1
    return 1
for a,b in F:
    unite(a,b)
dic = {}
for i in range(1,n+1):
    if root(i) in dic:
        dic[root(i)] +=1
    else:
        dic[root(i)] = 1
for i in range(1,n+1):
    ans = dic[root(i)]-1
    for b in Fx[i]:
        if root(b)==root(i):
            ans-=1
    for b in Bx[i]:
        if root(b)==root(i):
            ans-=1
    print(ans,end=" ")

Solution (Python):

import numpy as np


from functools import *
import sys
sys.setrecursionlimit(100000)


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


def II():
    return int(input())


mod = 10**9+7


class UnionFind:
    def __init__(self, size):
        
        
        self.table = [-1 for i in range(size)]

    def _find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] >= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def get_ntree(self):
        res = 0
        for c in self.table:
            if c < 0:
                res += 1
        return res

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

    def get_nclass(self):
        done = []
        for x in range(len(self.table)):
            if x in done:
                continue
            while self.table[x] >= 0:
                done.append(x)
                x = self.table[x]

    def get_nodenum(self):
        res = []
        for t in self.table:
            if t < 0:
                res.append(-t)

        return res


def ij_to_n(i, j, W):
    return i*W+j


def n_to_ij(n, W):
    return (n//W, n % W)


if __name__ == '__main__':

    N, M, K = acinput()

    uf = UnionFind(N)
    A=[[]for i in range(N)]
    for i in range(M):
        tmp = acinput()
        uf.union(tmp[0]-1, tmp[1]-1)
        A[tmp[0]-1].append(tmp[1]-1)
        A[tmp[1]-1].append(tmp[0]-1)


    block=[[]for i in range(N)]
    for i in range(K):
        tmp = acinput()
        block[tmp[0]-1].append(tmp[1]-1)
        block[tmp[1]-1].append(tmp[0]-1)

    nt = uf.get_ntree()
    res=[]
    for i in range(N):
        nblock = 0
        for sb in block[i]:
            if uf.is_same(sb,i):
                nblock += 1

        nn =(-uf.table[uf.find(i)])

        nn-=1
        
        
        tmp = nn-(len(A[i]))-nblock
        res.append(tmp)

    print(" ".join(map(str,res)))

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


N, M, K = map(int, input().split())
uf1 = UnionFind(N)
frs = [0] * N
for _ in range(M):
    a, b = map(int, input().split())
    uf1.union(a-1, b-1)
    frs[a-1] += 1
    frs[b-1] += 1
ans = []
for i in range(N):
    ans.append(uf1.size(i) - frs[i] - 1)
for _ in range(K):
    c, d = map(int, input().split())
    if uf1.same(c-1, d-1):
        ans[c-1] -= 1
        ans[d-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())
    
from collections import defaultdict
n,m,k=map(int,input().split())
tree = UnionFind(n)
friend=defaultdict(int)
block =defaultdict(int)

ab=[]
for _ in range(m):
    a,b=map(int,input().split())
    ab.append((a,b))
    
for a,b in ab:
    tree.union(a-1,b-1)
    
for a,b in ab:
    if tree.same(a-1,b-1):
        friend[a-1] +=1
        friend[b-1] +=1
    
for _ in range(k):
    c,d=map(int,input().split())
    if tree.same(c-1,d-1):
        block[c-1] +=1
        block[d-1] +=1
    
ans=[]
for i in range(n):
    l = tree.size(i) - block[i]  - friend[i]
    ans.append(l-1)
print(*ans)

Solution (Python):
n,m,k = map(int,input().split())
num = [1 for _ in range(n)]
pre = [i for i in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  A = [a]
  B = [b]
  la = 1
  lb = 1
  while a != pre[a]:
    a = pre[a]
    A.append(a)
    la += 1
  while b != pre[b]:
    b = pre[b]
    B.append(b)
    lb += 1
  
  if a != b:
    if la > lb:
      pre[b] = a
      for aa in A:
        pre[aa] = a
      for bb in B:
        pre[bb] = a
    else:
      pre[a] = b
      for aa in B:
        pre[aa] = b
      for bb in B:
        pre[bb] = b
root = [10**6 for _ in range(n)]
cnt = [0 for _ in range(n)]
for i in range(n):
  if root[i] < 10**6:
    cnt[root[i]] += 1
    continue
  I = int(i)
  J = [I]
  while I != pre[I]:
    I = pre[I]
    J.append(I)
  for x in J:
    root[x] = I
  cnt[I] += 1



ans = []
for i in range(n):
  ans.append(cnt[root[i]]-num[i])

for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    ans[a] -= 1
    ans[b] -= 1
print(' '.join(map(str,ans)))

Solution (Python):
n,m,k = (int(num) for num in input().split())
f_l = [0] * n
b_l = [[] for _ in range(n)]
par = [i for i in range(n)]
rank = [0] * n
size = [1] * n

def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])
        
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    elif rank[x] < rank[y]:
        par[x] = y
        size[y] += size[x]
    else:
        par[y] = x
        size[x] += size[y]
        if rank[x] == rank[y]:
            rank[x] += 1
    return
            
def isSame(x,y):
    return find(x) == find(y)

for _ in range(m):
    a,b = (int(num) for num in input().split())
    a -= 1
    b -= 1
    f_l[a] += 1
    f_l[b] += 1
    unite(a,b)
    
    
    
for _ in range(k):
    a,b = (int(num) for num in input().split())
    a -= 1
    b -= 1
    b_l[a].append(b)
    b_l[b].append(a)
    
ans = ""

for i in range(n):
    ans_num = size[find(i)] - f_l[i] -1
    for num in b_l[i]:
        if isSame(i,num):
            ans_num -= 1
    ans_num = max(ans_num,0)
    ans += str(ans_num) + " "
    
print(ans)

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):
        """
        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 と 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):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

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)]
ans = [0] * n
u = UnionFind(n)
for a,b in ab:
  a-=1
  b-=1
  u.union(a,b)
for i in range(n):
  ans[i] = u.get_size(i)-1
for a,b in ab:
  a-=1
  b-=1
  if u.is_same(a,b):
    ans[a] -= 1
    ans[b] -= 1
for c,d in cd:
  c-=1
  d-=1
  if u.is_same(c,d):
    ans[c] -= 1
    ans[d] -= 1	
print(*ans)

Solution (Python):
def rt(x):
    while x!=T[x][0]:
        x = T[x][0]
    return x
N,M,K = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
D = {i:[] for i in range(1,N+1)}
for _ in range(K):
    c,d = map(int,input().split())
    D[c].append(d)
    D[d].append(c)
T = {i:[i,0] for i in range(1,N+1)}
for a in G:
    for b in G[a]:
        r1 = rt(a)
        r2 = rt(b)
        if r1!=r2:
            if T[r1][1]>=T[r2][1]:
                T[r2][0] = r1
                if T[r1][1]==T[r2][1]:
                    T[r1][1] += 1
            else:
                T[r1][0] = r2
C = {}
for i in range(1,N+1):
    rt1 = rt(i)
    if rt1 not in C:
        C[rt1] = 0
    C[rt1] += 1
B = [0 for _ in range(N+1)]
for i in range(1,N+1):
    rt1 = rt(i)
    numc = C[rt1]
    numd = len(G[i])
    B[i] = numc-1-numd
    for j in D[i]:
        if rt(j)==rt1:
            B[i] -= 1
print(*B[1:])

Solution (Python):
class DisjointSet:
    def __init__(self, size):
        self.rank = [0 for i in range(size)]
        self.p = [0 for i in range(size)]
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    
    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]
        

from collections import defaultdict, Counter
count_friend = Counter()

friends_cluster = Counter()

count_block = Counter()
N, M, K = map(int, input().split())
ds = DisjointSet(N+1)

for i in range(M):
    A, B = map(int, input().split())
    ds.unite(A, B)
    count_friend[A] += 1
    count_friend[B] += 1
for i in range(K):
    C, D = map(int, input().split())
    if ds.same(C, D):
        count_block[C] += 1
        count_block[D] += 1
c_ids = [ds.findSet(i) for i in range(N+1)]
for i in range(1, N+1):
    friends_cluster[c_ids[i]] += 1
ans = []
for i in range(1, N+1):
    c_id = c_ids[i]
    ans += [friends_cluster[c_id]-count_block[i]-count_friend[i]-1]
print(' '.join(list(map(str, ans))))

Solution (Python):
import sys
input = sys.stdin.readline
n,m,k=map(int,input().split())
friend=[[]for _ in range(n+1)]
block=[[] for _ in range(n+1)]

par=[-1]*(n+1)
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):
    if find(x)==find(y):
        return False
    if size(x)<size(y):
        x,y=y,x
    X=find(x)
    Y=find(y)
    par[X]+=par[Y]
    par[Y]=X
    return True
def is_same(x,y):
    return find(x)==find(y)

for _ in range(m):
    a,b=map(int,input().split())
    friend[a].append(b)
    friend[b].append(a)
    unite(a,b)
for _ in range(k):
    c,d=map(int,input().split())
    if is_same(c,d):
        block[c].append(d)
        block[d].append(c)
ans=[0]*(n+1)

for i in range(1,n+1):
    f=size(i)-1-len(friend[i])
    b=len(block[i])
    ans[i]=f-b
print(*ans[1:], sep=' ')

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

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)
      
uf=UnionFind(N)
for i in range(N):
  for j in AB[i]:
    uf.union(i,j-1)

ans=[0]*N
for i in range(N):
  ans[i]=uf.size(i)-1-len(AB[i])
for i in range(K):
  c,d=map(int,input().split())
  if uf.same(c-1,d-1):
    ans[c-1]-=1
    ans[d-1]-=1
print(*ans)

Solution (Python):
n, m, k = map(int, input().split())
connect = [[] for _ in range(n)]
cCnt = [0 for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    connect[a - 1].append(b - 1)
    cCnt[a - 1] += 1
    connect[b - 1].append(a - 1)
    cCnt[b - 1] += 1

group = [0 for _ in range(n)]
gNum = 0
import queue
for i in range(n):
    if group[i]:
        continue
    gNum += 1
    next = queue.Queue()
    for j in connect[i]:
        group[j] = gNum
        next.put(j)
    group[i] = gNum

    while not next.empty():
        j = next.get()
        group[j] = gNum
        for l in connect[j]:
            if not group[l]:
                group[l] = gNum
                next.put(l)

hunaka = [0 for i in range(n)]
for i in range(k):
    c, d = map(int, input().split())
    if group[c - 1] != group[d - 1]:
        continue
    hunaka[c - 1] += 1
    hunaka[d - 1] += 1

groupCnt = [0 for _ in range(gNum + 1)]
for i in group:
    groupCnt[i] += 1

for i in range(n):
    tmp = groupCnt[group[i]]
    tmp -= cCnt[i]
    tmp -= hunaka[i]
    tmp -= 1
    print(tmp, end = " ")

Solution (Python):
from operator import itemgetter

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

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

def get_root(A):
    if par[A] == A:
        return A
    par[A] = get_root(par[A])
    return par[A]

def connect(A, B):
    A = get_root(A)
    B = get_root(B)
    if A == B:
        return
    if rank[A] < rank[B]:
        A, B = B, A
    par[B] = A
    rank[A] += rank[B]
    rank[B] = 0


def verify_connect(A, B):
    if get_root(A) == get_root(B):
        return True
    else:
        return False



like_path = [[] for i in range(N)]
like_query = [input() for i in range(M)]
dislike_query = [input() for i in range(K)]
for line in like_query:
    A, B = map(int, line.split())
    connect(A-1, B-1)
    like_path[A-1].append(B-1)
    like_path[B-1].append(A-1)

tmp_ans = []
for i in range(N):
    tmp_ans.append(rank[get_root(i)]-len(like_path[i])-1)

for line in dislike_query:
    A, B = map(int, line.split())
    if verify_connect(A-1, B-1):
        tmp_ans[A-1] -= 1
        tmp_ans[B-1] -= 1

print(" ".join(map(str, tmp_ans)))