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
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

class UnionFind:
    def __init__(self, n):
        
        
        self.root_table = [-1] * n
        
        self.count_table =  [1] * n
 
    def get_root(self, x):
        if self.root_table[x] < 0:
            return x
        else:
            
            self.root_table[x] = self.get_root(self.root_table[x])
            return self.root_table[x]
 
    def find(self, x, y):
        return self.get_root(x) == self.get_root(y)
 
    def union(self, x, y):
        r1 = self.get_root(x)
        r2 = self.get_root(y)
        if r1 == r2:
            return

        
        d1 = self.root_table[r1]
        d2 = self.root_table[r2]
        
        if d1 <= d2:
            self.root_table[r2] = r1
            self.count_table[r1] += self.count_table[r2]
            
            if d1 == d2:
                self.root_table[r1] -= 1
        else:
            self.root_table[r1] = r2
            self.count_table[r2] += self.count_table[r1]
        
    def count(self, x):
        return self.count_table[self.get_root(x)]


N, M, K = MI()
AB = LRI(M)
CD = LRI(K)

uf = UnionFind(N + 1)
friend = [0] * (N + 1)

for ab in AB:
    a, b = ab

    friend[a] -= 1
    friend[b] -= 1

    uf.union(a, b)

for cd in CD:
    c, d = cd

    if uf.find(c, d):
        friend[c] -= 1
        friend[d] -= 1

for i in range(1, N + 1):
    friend[i] += (uf.count(i) - 1)

print(*friend[1:])

Solution (Python):

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

Friends = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Friends[a].add(b)
    Friends[b].add(a)

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



checked = set()
ans = [0]*N

for i in range (N):
    if i in checked:
        continue
    
    fg = set()

    stack = list(Friends[i])
    while stack:
        f = stack.pop()
        if f in checked:
            continue

        checked.add(f)
        fg.add(f)
        stack.extend(Friends[f])

    for f in fg:
        ans[f] += len(fg)-1-len(fg&(Friends[f]|Blocked[f]))


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

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

N,M,K = map(int,input().split())
 
par = [i for i in range(N+1)]
 

def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]
 

def bool_same(x,y):
    return root(x) == root(y)
 

def unite(x,y):
    x = root(x)
    y = root(y)
    if x != y:
        par[x] = y
 
AB = [list(map(int,input().split())) for i in range(M)]
CD = [list(map(int,input().split())) for i in range(K)]
 
for a,b in AB:
    unite(a,b)
 
for i in range(N+1):
    root(i)
 
member = [0 for i in range(N+1)]
 
for p in par:
    member[p] += 1
 
ans = [member[par[i]]-1 for i in range(N+1)]
 
for a,b in AB:
    if bool_same(a,b):
        ans[a] -= 1
        ans[b] -= 1
for c,d in CD:
    if bool_same(c,d):
        ans[c] -= 1
        ans[d] -= 1
print(' '.join(map(str,ans[1:])))

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

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

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


def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]


def bool_same(x,y):
    return root(x) == root(y)


def unite(x,y):
    x = root(x)
    y = root(y)
    if x != y:
        par[x] = y

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

for i in range(M):
    a,b = AB[i]
    unite(a,b)

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

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

ans = [member[par[i]]-1 for i in range(N+1)]

for i in range(M):
    a,b = AB[i]
    if bool_same(a,b):
        ans[a] -= 1
        ans[b] -= 1

for i in range(K):
    c,d = CD[i]
    if bool_same(c,d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans[1:])

Solution (Python):
from collections import deque
n,m,k = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]

f1 = [set() for _ in range(0, n+1)]
b1 = [set() for _ in range(0, n+1)]
fb1 = [set() for _ in range(0, n+1)]
ans = [0]*(n+1)

for x,y in ab:
    f1[x].add(y)
    f1[y].add(x)
    fb1[x].add(y)
    fb1[y].add(x)

for x,y in cd:
    b1[x].add(y)
    b1[y].add(x)
    fb1[x].add(y)
    fb1[y].add(x)

stack = deque()
visited = [0]*(n+1)
links = []

for i in range(1, n+1):
    if visited[i]: continue
    link = {i}
    visited[i] = 1
    stack.append(i)
    while stack:
        n1 = stack.pop()
        for j in f1[n1]:
            if visited[j] == 0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    links.append(link)

for i in links:
    leni = len(i)
    for j in i:
        ans[j] = leni - len(i & fb1[j]) - 1

print(*ans[1:])

Solution (Python):
from collections import deque
from collections import Counter
N, M, K = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
C = [0]*K
D = [0]*K
for i in range(K):
    C[i], D[i] = map(int,input().split())

friend = {i: set([]) for i in range(1, N+1)}
brock = {i: set([]) for i in range(1, N+1)}
for i in range(M):
    friend[A[i]].add(B[i])
    friend[B[i]].add(A[i])
for i in range(K):
    brock[C[i]].add(D[i])
    brock[D[i]].add(C[i])

labels = [0] * (N+1)


def mark(n, label):
    if labels[n] != 0:
        return -1
    else:
        q = deque()
        q.append(n)
        labels[n] = label
        while q != deque():
            node = q.pop()
            labels[node] = label
            for i in friend[node]:
                if labels[i] == 0:
                    q.append(i)
        return label


label = 1
for n in range(1, N + 1):
    if mark(n, label) != -1:
        label += 1

group_size = Counter(labels)

res = [0] * N
for n in range(1, N + 1):
    tmp = 0
    for b in brock[n]:
        if labels[n] == labels[b]:
            tmp += 1
    res[n - 1] = group_size[labels[n]] - 1 - len(friend[n]) - tmp

print(*res)

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

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

    def union(self, x, y):
        x = self.root(x)
        y = self.root(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.root(x)]

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

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

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

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

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

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
ab = [tuple(map(int,input().split())) for i in range(m)]
cd = [tuple(map(int,input().split())) for i in range(k)]
es1 = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es1[a].append(b)
    es1[b].append(a)
    uf.union(a,b)

es_block_in_union = [[] for i in range(n)]
for i, (c,d) in enumerate(cd):
    c,d = c-1,d-1
    if uf.is_same(c,d):
        es_block_in_union[c].append(d)
        es_block_in_union[d].append(c)


ans = [0]*n
for i in range(n):
    ans[i] =  uf.size(i) - len(es_block_in_union[i])  - len(es1[i]) -1

print(*ans, sep=' ')

Solution (Python):
class UnionFind():
    
    def __init__(self,n):
        self.n = n
        self.parents = [-1]*n
        
    def find(self, a):
        if self.parents[a] < 0:
            return a
        else:
            self.parents[a]=self.find(self.parents[a])
            return self.parents[a]
        
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        else:
            if self.parents[x]<self.parents[y]:
                x,y = y,x
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            
    def size(self,x):
        return -self.parents[self.find(x)]
    
    def same(self,x,y):
        if self.find(x)==self.find(y):
            return True
        else:
            return False
    
N,M,K = map(int,input().split())
uf = UnionFind(N)
friend = [list(map(int,input().split())) for i in range(M)]
block = [list(map(int,input().split())) for i in range(K)]
ff = [[] for i in range(N)]
bb = [[] for i in range(N)]
ans = []
for i in range(M):
    uf.union(friend[i][0]-1,friend[i][1]-1)
    ff[friend[i][0]-1].append(friend[i][1]-1)
    ff[friend[i][1]-1].append(friend[i][0]-1)
for i in range(K):
    bb[block[i][0]-1].append(block[i][1]-1)
    bb[block[i][1]-1].append(block[i][0]-1)
for i in range(N):
    ans.append(uf.size(i)-1-len(ff[i]))
    for j in bb[i]:
        if uf.same(j,i)==True:
            ans[i] -= 1
answer=[str(ans[i]) for i in range(len(ans))]
print(" ".join(answer))

Solution (Python):
from collections import deque

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

f = [set() for _ in range(N+1)]
b = [set() for _ in range(N+1)]

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

stack=deque()
ans = [0]*(N+1)
visited = [0]*(N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in f[n]:
            if visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    for i in link:
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1
print(*ans[1:])

Solution (Python):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

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

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

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

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

def resolve():
    N, M, K = lr()
    uf = UnionFind(N)
    fr = [0]*N
    for i in range(M):
        a, b = lr()
        uf.union(a-1, b-1)
        fr[a-1] += 1
        fr[b-1] += 1
    ans = [uf.size(x) - fr[x] - 1 for x in range(N)]
    for i in range(K):
        c, d = lr()
        if uf.same(c-1, d-1):
            ans[c-1] -= 1
            ans[d-1] -= 1
    print(*ans, sep=' ')
resolve()

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

N,M,K = map(int, input().split())
par = [-1]*(N+1)
fri = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    fri[a].append(b)
    fri[b].append(a)
    unite(a,b)

bro = [[] for i in range(N+1)]
for i in range(K):
    c,d = map(int,input().split())
    bro[c].append(d)
    bro[d].append(c)

ans = [0]*N
for i in range(1,N+1):
    ans[i-1] = size(i)-1
    for f in fri[i]:
        if same(f,i): ans[i-1] -= 1
    for b in bro[i]:
        if same(b,i): ans[i-1] -= 1


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

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

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 members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

uf = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
  block_list[a-1].append(b-1)
  block_list[b-1].append(a-1)
for i in range(K):
  a, b = map(int, input().split())
  if uf.same(a-1, b-1):
    block_list[a-1].append(b-1)
    block_list[b-1].append(a-1)
ans = []
for i in range(N):
  ans.append(uf.size(i) - len(block_list[i]))
print(*ans)

Solution (Python):
import sys
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,input().split())

U=UnionFind(n)
M=[[] for i in range(n)]
K=[[] for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    U.union(a,b)
    M[a].append(b)
    M[b].append(a)
    
for i in range(k):
    a,b=map(int,input().split())
    a-=1
    b-=1
    if U.same(a,b):
        K[a].append(b)
        K[b].append(a)

ans=[]
for i in range(n):
    m=M[i]
    k=K[i]
    ans.append(U.size(i)-len(m)-len(k)-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())


if __name__ == "__main__":
    n, m, k = map(int, input().split())
    uf = UnionFind(n)

    friendlist = dict()
    for i in range(m):
        tmp = list(map(int, input().split()))
        uf.union(tmp[0]-1, tmp[1]-1)
        if tmp[0] - 1 not in friendlist:
            friendlist[tmp[0]-1] = [tmp[1]-1]
        else:
            friendlist[tmp[0]-1].append(tmp[1]-1)
        if tmp[1] - 1 not in friendlist:
            friendlist[tmp[1]-1] = [tmp[0]-1]
        else:
            friendlist[tmp[1]-1].append(tmp[0]-1)

    blocklist = dict()
    for i in range(k):
        tmp = list(map(int, input().split()))
        if tmp[0] - 1 not in blocklist:
            blocklist[tmp[0]-1] = [tmp[1]-1]
        else:
            blocklist[tmp[0]-1].append(tmp[1]-1)
        if tmp[1] - 1 not in blocklist:
            blocklist[tmp[1]-1] = [tmp[0]-1]
        else:
            blocklist[tmp[1]-1].append(tmp[0]-1)

    ans = list()
    for i in range(n):
        blocknum = 0
        if i in blocklist:
            for ii in blocklist[i]:
                if uf.find(ii) == uf.find(i):
                    blocknum += 1
        friendnum = 0
        if i in friendlist:
            friendnum = len(friendlist[i])

        print(str(uf.size(i) - friendnum - blocknum - 1))

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter
N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]

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

label = [-1] * N

cnt_label_num = 0

for i in range(N):
	if label[i] != -1: continue 
	
	
	Q = [i]
	while Q:
		cur = Q.pop()
		if label[cur] != -1: continue
		label[cur] = cnt_label_num
		for adj in friend[cur]:
			if label[adj] != -1: continue
			Q.append(adj)
	
	cnt_label_num += 1
	

cnt = Counter(label)
for i in range(N):
	friend_candidate = cnt[label[i]] - 1 
	friend_candidate -= len(friend[i]) 
	
	for block_man in block[i]:
		if label[i] == label[block_man]:
			friend_candidate -= 1
	print(friend_candidate, end = " ")

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

    def find(self, x):  
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  
            return self.parent[x]

    def union(self, x, y):  
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

    def group_size(self, x):  
        return self.size[self.find(x)]
    
N, M, K = map(int, input().split())
A, B, C, D = [0]*M, [0]*M, [0]*K, [0]*K
for i in range(0, M):
    A[i], B[i] = map(int, input().split())
for i in range(0, K):
    C[i], D[i] = map(int, input().split())

friend, block = [0]*N, [0]*N
uf = UnionFind(N)
for i in range(0, M):
    friend[A[i]-1] = friend[A[i]-1]+1
    friend[B[i]-1] = friend[B[i]-1]+1
    uf.union(A[i]-1, B[i]-1)
for i in range(0, K):
    if uf.is_same(C[i]-1, D[i]-1):
        block[C[i]-1] = block[C[i]-1]+1
        block[D[i]-1] = block[D[i]-1]+1

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

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 is_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, inp().split())
uf = UnionFind(N)
ans = [0]*N
not_friend = [1]*N 

for _ in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  uf.union(a, b)
  not_friend[a] += 1
  not_friend[b] += 1
  
for _ in range(K):
  c, d = map(int, input().split())
  c -= 1
  d -= 1
  if uf.is_same(c, d):
    not_friend[c] += 1
    not_friend[d] += 1  
    
ans = [uf.size(i) - not_friend[i] for i in range(N)]    
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
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def unite(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)]

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


N, M, K = map(int, input().split())
uf = UnionFind(N)
friends = [[] for _ in range(N)]
blocks = [[] for _ in range(N)]
root = {}

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

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

ans = []
for i in range(N):
    ans.append(uf.size(i) - 1 - len(blocks[i]) - len(friends[i]))
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
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def unite(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)]

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


N, M, K = map(int, input().split())
uf = UnionFind(N)
friends = [[] for _ in range(N)]
blocks = [[] for _ in range(N)]
root = {}

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

roots = uf.roots()
for r in roots:
    size = uf.size(r)
    root[r] = size - 1

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

ans = []
for i in range(N):
    ans.append(root[uf.find(i)] - len(blocks[i]) - len(friends[i]))
print(*ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**9)

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

a = []
b = []
c = []
d = []
for _ in range(m):
	tmp = list(map(int,input().split()))
	a.append(tmp[0]-1)
	b.append(tmp[1]-1)
for _ in range(k):
	tmp = list(map(int,input().split()))
	c.append(tmp[0]-1)
	d.append(tmp[1]-1)

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

uf = UnionFind(n)
ans = []

for i in range(m):
	uf.union(a[i],b[i])

for i in range(n):
	ans.append(uf.size(i)-1) 

for i in range(m):
	if uf.find(a[i]) == uf.find(b[i]):
		ans[a[i]] -= 1
		ans[b[i]] -= 1

for i in range(k):
	if uf.find(c[i]) == uf.find(d[i]):
		ans[c[i]] -= 1
		ans[d[i]] -= 1

for i in range(n):
	print(ans[i],end=" ")

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

N, M, K = map(int, inp().split())
friends = [set() for _ in range(N+1)]
blocked = [set() for _ in range(N+1)]

for _ in range(M):
  a, b = map(int, inp().split())
  friends[a].add(b)
  friends[b].add(a)
for _ in range(K):
  c, d = map(int, inp().split())
  blocked[c].add(d)
  blocked[d].add(c)  

checked = set()
ans = [0]*(N+1)
for i in range(1, N+1):
  if i in checked:
    continue
  chain = set()
  
  stack = list(friends[i])
  while stack:
    friend = stack.pop()
    if friend in checked:
      continue
      
    checked.add(friend)
    chain.add(friend)
    stack.extend(friends[friend])
  cnt = len(chain) - 1 
  for c in chain:
    ans[c] += cnt - len(chain & (friends[c] | blocked[c]))
    
print(*ans[1:])

Solution (Python):
class Unionfind():

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

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


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

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

    def same(self,x,y):
        if self.find(x)==self.find(y):
            return True
        else:
            return False
          
N,M,K=map(int,input().split())
uf=Unionfind(N)
friend=[list(map(int,input().split())) for i in range(M)]
block=[list(map(int,input().split())) for i in range(K)]
ff=[[] for i in range(N)]
bb=[[] for i in range(N)]
ans=[]
for i in range(M):
    uf.union(friend[i][0]-1,friend[i][1]-1)
    ff[friend[i][0]-1].append(friend[i][1]-1)
    ff[friend[i][1]-1].append(friend[i][0]-1)
for i in range(K):
    bb[block[i][0]-1].append(block[i][1]-1)
    bb[block[i][1]-1].append(block[i][0]-1)
for i in range(N):
    ans.append(uf.size(i)-1-(len(ff[i])))
    for j in bb[i]:
        if uf.same(j,i)==True:
            ans[i]-=1
answer=[str(ans[i]) for i in range(len(ans))]
print(" ".join(answer))