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 = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find(self, n):
        if self.parent[n] != n:
            self.parent[n] = self.find(self.parent[n])
        return self.parent[n]

    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.parent[y] = x
            self.size[x] += self.size[y]
        else:
            self.parent[x] = y
            self.size[y] += self.size[x]
            if self.rank[x] == self.rank[y]:
                self.rank[y] = self.rank[y] + 1

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

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

UF = UnionFind(N)
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

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

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

for i in range(N):
    for f in F[i]:
        UF.union(i, f)

ans = [UF.size[UF.find(i)]-1 for i in range(N)]

for i in range(N):
    ans[i] -= len(F[i])

for i in range(N):
    for b in B[i]:
        if UF.same(i, b):
            ans[i] -= 1

print(*ans, sep=' ')

Solution (Python):


        



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

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

from collections import deque
clusters=[]
visited=[0]*n
list_cluster=[0]*n
i_c=0

for i in range(n):
    if visited[i]==0:
        start=i
    else:
        continue

    cluster =[start]
    q=deque([(start,togo) for togo in friend[start]]) 
    visited[start]=1
    list_cluster[start]=i_c
    for togo in friend[start]:
        visited[togo]=1
        cluster.append(togo)
        list_cluster[togo]=i_c
    while q:
        parent,x = q.popleft()
        for y in friend[x]:


            if visited[y]==0:
                q.append((x,y))
                visited[y]=1
                cluster.append(y)
                list_cluster[y]=i_c

    clusters.append(cluster)
    i_c+=1

ans = [len(clusters[list_cluster[i]])-1 for i in range(n)  ]
for f0,f1 in friends_pair:
    if list_cluster[f0] ==  list_cluster[f1]:
        ans[f0]-=1
        ans[f1]-=1
for b0,b1 in block:
    if list_cluster[b0] ==  list_cluster[b1]:
        ans[b0]-=1
        ans[b1]-=1
print(*ans)

Solution (Python):


        



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

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

from collections import deque
clusters=[]
visited=[0]*n
list_cluster=[0]*n
i_c=0





for i in range(n):
    if visited[i]==0:
        start=i
    else:
        continue

    cluster =[start]
    q=deque([(start,togo) for togo in friend[start]]) 
    visited[start]=1
    list_cluster[start]=i_c
    for togo in friend[start]:
        visited[togo]=1
        cluster.append(togo)
        list_cluster[togo]=i_c
    while q:
        parent,x = q.popleft()
        for y in friend[x]:
            if y == parent:
                continue
            if visited[y]==0:
                q.append((x,y))
                visited[y]=1
                cluster.append(y)
                list_cluster[y]=i_c

    clusters.append(cluster)
    i_c+=1

ans = [len(clusters[list_cluster[i]])-1 for i in range(n)  ]
for f0,f1 in friends_pair:
    if list_cluster[f0] ==  list_cluster[f1]:
        ans[f0]-=1
        ans[f1]-=1
for b0,b1 in block:
    if list_cluster[b0] ==  list_cluster[b1]:
        ans[b0]-=1
        ans[b1]-=1
print(*ans)

Solution (Python):
import sys
import math
import fractions
import bisect
from collections import deque
from collections import defaultdict
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())
uf = UnionFind(N)
dame = [set() for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.union(A, B)
    dame[A].add(B)
    dame[B].add(A)
for _ in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if uf.same(C, D):
        dame[C].add(D)
        dame[D].add(C)


ans = []
for n in range(N):
    ans.append(uf.size(n) - len(dame[n]) - 1)

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

Solution (Python):
maxn = 100000

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

par = [0] * (n+1)
rank = [0] * (n+1)


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


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

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

a = [0]*m
b = [0]*m
        
for i in range(m):
    a[i] ,b[i]  = map(int, input().split())
    unite(a[i] ,b[i] )
    
from collections import Counter
par2 = [find(i) for i in range(n+1)]
s = Counter(par2)
ans = [s[i] for i in par2]

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

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

ans = [ans[j]-1 for j in range(1,n+1)]
print(*ans)

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

    def find_root(self, x):
        p = self.parent
        while (0 <= p[x]):
            x, p[x] = p[x], p[p[x]]
        return x

    def unite(self, x, y):
        x_root = self.find_root(x)
        y_root = self.find_root(y)
        p = self.parent
        if (x_root == y_root):
            return
        if p[x_root] > p[y_root]:
            x_root, y_root = y_root, x_root
        
        p[x_root], p[y_root] = (p[x_root] + p[y_root]), x_root

    def size(self, x):
        return -self.parent[self.find_root(x)]

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


n, m, k = map(int, input().split())
ab = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
cd = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(k)]
friend_trees = UnionFindTrees(n)
friend_or_block_cnts = [0] * n

for a, b in ab:
    friend_trees.unite(a, b)
    friend_or_block_cnts[a] += 1
    friend_or_block_cnts[b] += 1
for c, d in cd:
    if friend_trees.is_same_set(c, d):
        friend_or_block_cnts[c] += 1
        friend_or_block_cnts[d] += 1

print(*[(friend_trees.size(i) - friend_or_block_cnts[i] - 1) for i in range(n)])

Solution (Python):
from sys import exit
from collections import Counter
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

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

if M == 0:
    print(*np.zeros(N, dtype="int8"))
    exit()

exc = [set() for _ in range(N)]
edge = []

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

edge = np.array(edge).T
matr = csr_matrix((np.ones(M, dtype="int64"), edge), (N, N))
_, labels = connected_components(matr)
ct = Counter(labels)

for _ in range(K):
    c, d = map(int, input().split())
    if labels[c - 1] == labels[d - 1]:
        exc[c - 1].add(d - 1)
        exc[d - 1].add(c - 1)

ans = [ct[labels[i]] - len(exc[i]) - 1 for i in range(N)]
print(*ans)

Solution (Python):
n,m,k = map(int,input().split())
al = [0 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, a, b,l):
        x = self.find(a)
        y = self.find(b)
        l[a] -= 1
        l[b] -= 1

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf = UnionFind(n)
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1,al)

for i in range(k):
    c,d = map(int,input().split())
    if uf.find(c-1) == uf.find(d-1):
        al[c-1] -= 1
        al[d-1] -= 1
for i in range(n):
    print(uf.size(i)+al[i]-1,end=" ")

Solution (Python):
from sys import exit
from collections import Counter
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N, M, K = map(int, input().split())
exc = [set() for _ in range(N)]
edge = []

if M == 0:
    print(*[0 for _ in range(N)])
    exit()

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

edge = np.array(edge).T
matr = csr_matrix(([1 for _ in range(M)], edge), (N, N))
_, labels = connected_components(matr)
ct = Counter(labels)

for _ in range(K):
    c, d = map(int, input().split())
    if labels[c - 1] == labels[d - 1]:
        exc[c - 1].add(d - 1)
        exc[d - 1].add(c - 1)

ans = [ct[labels[i]] - len(exc[i]) - 1 for i in range(N)]
print(*ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf=UnionFind(n)
friends=[[] for _ in range(n)]
blocks=[[] for _ in range(n)]
root=dict()
for i in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
  friends[a-1].append(b-1)
  friends[b-1].append(a-1)
lis=uf.roots()
for i in lis:
  size=uf.size(i)
  root[i]=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):
n, m, k = map(int, input().split())
a_m, b_m = [], []
c_k, d_k = [], []
def minus(x):
    return int(x)-1

friends_list = [[] for i in range(n)]
block_list = [[] for i in range(n)]
for i in range(m):
    a_m.append(0)
    b_m.append(0)
    a_m[i], b_m[i] = map(minus, input().split())
    friends_list[a_m[i]].append(b_m[i])
    friends_list[b_m[i]].append(a_m[i])
for i in range(k):
    c_k.append(0)
    d_k.append(0)
    c_k[i], d_k[i] = map(minus, input().split())
    block_list[c_k[i]].append(d_k[i])
    block_list[d_k[i]].append(c_k[i])


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

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

def union_size(x):
    return -parents[find(x)]

def blocks_in_union(x):
    count = 0
    for block in block_list[x]:
        if find(x) == find(block):
            count += 1
    return count

parents =[ -1 for i in range(n)]
for i in range(m):
    unite(a_m[i], b_m[i])
for i in range(n):
    print(union_size(i)-1-len(friends_list[i])-blocks_in_union(i), end=' ')

Solution (Python):
def root(parents, i):
    depth = 0
    while parents[i] != i:
        i = parents[i]
        depth += 1

    return i, depth

def isSame(parents, a, b):
    return root(parents,a)[0] == root(parents, b)[0]

def union(parents, size, a, b):
    pa, deptha = root(parents, a)
    pb, depthb = root(parents, b)
    if pa == pb: 
        return
    if deptha < depthb:
        parents[pa] = pb
        size[pb] += size[pa]
    else:
        parents[pb] = pa
        size[pa] += size[pb]

def resolve():
    N, M, K = list(map(int, input().split()))
    parents = [i for i in range(N)]
    size = [1] * N
    ans = [0] * N

    for i in range(M):
        A, B = list(map(int, input().split()))
        ans[A-1] += 1
        ans[B-1] += 1
        union(parents, size, A-1, B-1)

    for i in range(N):
        pi = root(parents, i)[0]
        ans[i] = size[pi] - ans[i] -1 

    for i in range(K):
        A, B = list(map(int, input().split()))
        if isSame(parents, A-1, B-1):
            ans[A-1] -= 1
            ans[B-1] -= 1

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

resolve()

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

    def FindRoot(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.FindRoot(self.parents[x])
            return self.parents[x]
    
    def Union(self,x,y):
        x = self.FindRoot(x)
        y = self.FindRoot(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 isSame(self,x,y):
        return self.FindRoot(x) == self.FindRoot(y)

    def Size(self,x):
        return -self.parents[self.FindRoot(x)]

n,m,k = [int(x) for x in input().split()]
obj = UnionFind(n)
cnt = [0]*(n+1)
for _ in range(m):
    a,b = [int(x) for x in input().split()]
    obj.Union(a,b)
    cnt[a] += 1
    cnt[b] += 1
for _ in range(k):
    c,d = [int(x) for x in input().split()]
    if obj.isSame(c,d):
        cnt[c] += 1
        cnt[d] += 1
ans = 0
for i in range(1,n+1):
    ans = obj.Size(i)-1-cnt[i]
    print(ans,end=" ")

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


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

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

    def unite(self, x, y):
        xd = self.find(x)
        yd = self.find(y)
        if(xd == yd):
            return False
        if self.d[xd] > self.d[yd]:
            self.d[yd] += self.d[xd]
            self.d[xd] = yd
        else:
            self.d[xd] += self.d[yd]
            self.d[yd] = xd
        return True

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

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


def main():
    n, m, k = map(int, input().split())
    uf = UnionFind(n)
    fr = [0] * n
    bl = [[] for _ in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        fr[a] += 1
        fr[b] += 1
        uf.unite(a, b)
    for i in range(k):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        bl[c].append(d)
        bl[d].append(c)

    ans = [0]*n
    for i in range(n):
        t = uf.size(i)-1-fr[i]
        for j in range(len(bl[i])):
            if(uf.same(i, bl[i][j])):
                t -= 1
        ans[i] = t
    print(*ans)


main()

Solution (Python):
from collections import defaultdict
import time
n,m,k = map(int,input().split())
fr = defaultdict(set)
bl = []
start = time.time()
group = [0] * n
 
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  fr[a].add(b)
  fr[b].add(a)
 
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  bl.append((a,b))
 
 
g_num = 0
for i in range(n):
    if group[i] != 0:
        continue
    g_num += 1
    unvisited = set({i})
    while len(unvisited) > 0:
        v = unvisited.pop()
        group[v] = g_num
        for w in fr[v]:
            if group[w] > 0 or w in unvisited:
                continue
            unvisited.add(w)
 
group_size = defaultdict(int)
for x in group:
    group_size[x] += 1
 
bl_in_group = [0] * n
for a,b in bl:
    if group[a] == group[b]:
        bl_in_group[a] += 1
        bl_in_group[b] += 1
 
for i in range(n):
    print(group_size[group[i]] - len(fr[i]) - bl_in_group[i] - 1, end=' ')
 
print()

Solution (Python):
from collections import defaultdict
import time
n,m,k = map(int,input().split())
fr = defaultdict(set)
bl = []
start = time.time()
group = [0] * n

for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  fr[a].add(b)
  fr[b].add(a)

for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  bl.append((a,b))


g_num = 0
for i in range(n):
    if group[i] != 0:
        continue
    g_num += 1
    unvisited = set({i})
    while len(unvisited) > 0:
        v = unvisited.pop()
        group[v] = g_num
        for w in fr[v]:
            if group[w] > 0 or w in unvisited:
                continue
            unvisited.add(w)

group_size = defaultdict(int)
for x in group:
    group_size[x] += 1

bl_in_group = [0] * n
for a,b in bl:
    if group[a] == group[b]:
        bl_in_group[a] += 1
        bl_in_group[b] += 1

for i in range(n):
    print(group_size[group[i]] - len(fr[i]) - bl_in_group[i] - 1, end=' ')

print()

Solution (Python):
from collections import deque,Counter
import sys
input = sys.stdin.readline

n,m,k = map(int,input().split())
ans = [0]*n
frd = [[] for _ in range(n)]

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

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

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

for i in range(n): 
    ans[i] += cnt[uni[i]] - 1
    print(ans[i],end=" ")

Solution (Python):
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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y: return False
        if self.parents[x] > self.parents[y]: x,y = y,x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True
    
    
    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())
ab = [list(map(int,input().split())) for _ in range(m)]
cd = [list(map(int,input().split())) for _ in range(k)]


uf = UnionFind(n)

for a,b in ab: uf.unite(a-1,b-1)


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

for a,b in ab:
    if uf.same(a-1,b-1):
        ans[a-1] -= 1
        ans[b-1] -= 1
for c,d in cd:
    if uf.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 = [i for i in range(N)]
        self.sizes = [1] * N

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx < ry:
            self.parents[ry] = rx
            self.sizes[rx] += self.sizes[ry]
            self.sizes[ry] = 0
        elif rx > ry:
            self.parents[rx] = ry
            self.sizes[ry] += self.sizes[rx]
            self.sizes[rx] = 0

    def same(self, x, y):
        return self.root(x) == self.root(y)
    
    def size(self, x):
        return self.sizes[self.root(x)]

N, M, K = list(map(int, input().split()))
AB_list = []
for _ in range(M):
    A, B = list(map(int, input().split()))
    AB_list.append([A - 1, B - 1])
CD_list = []
for _ in range(K):
    C, D = list(map(int, input().split()))
    CD_list.append([C - 1, D - 1])

uf = UnionFind(N)
for A, B in AB_list:
    uf.unite(A, B)

friends = [0] * N
for A, B in AB_list:
    friends[A] += 1
    friends[B] += 1
blocks = [0] * N
for C, D in CD_list:
    if uf.root(C) != uf.root(D):
        continue
    blocks[C] += 1
    blocks[D] += 1
answers = [0] * N
for i in range(N):
    answers[i] = uf.size(i) - 1 - friends[i] - blocks[i]

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

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



graph = [[] for _ in range(N)]
bgraph = [[] for _ in range(N)]
cnt = [0]*N
for i in range(M):
    ii, jj = friend[i]
    graph[ii-1].append(jj-1)
    graph[jj-1].append(ii-1)

for i in range(K):
    ii, jj = block[i]
    bgraph[ii-1].append(jj-1)
    bgraph[jj-1].append(ii-1)




seen = [False for _ in range(N)]
seenb = [False for _ in range(N)]
def dfs():
    labelb = 1
    
    for i in range(N):
        if seen[i] != False: continue
        label = 1
        
        seen[i] = label
        seenb[i] = labelb
        que = deque([i])
        seg = deque([i])
        while que:
            
            neci = que.pop()
            for nec in graph[neci]:
                if seen[nec]== False:
                    seen[nec]=label
                    seenb[nec]=labelb
                    que.append(nec)
                    seg.append(nec)
                    label += 1
        for iii in seg:
            seen[iii] = label

        labelb += 1

dfs()
for i in range(N):
    count = seen[i] - 1 -len(graph[i])
    if bgraph[i] and seen[i]>=2:
          for j in bgraph[i]:
                if seenb[i] == seenb[j]:
                    count -= 1
    cnt[i]=count
print(*cnt)

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

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

    uf = UnionFind(N)
    for a, b in zip(A, B):
        uf.union(a-1, b-1)

    direct_friends_num = [0]*N
    for a, b in zip(A, B):
        direct_friends_num[a-1] += 1
        direct_friends_num[b-1] += 1
    blocked_num = [0]*N
    for c, d in zip(C, D):
        if uf.find(c-1) == uf.find(d-1):
            blocked_num[c-1] += 1
            blocked_num[d-1] += 1

    ans = [0]*N
    for i in range(N):
        ans[i] = uf.size(i) - direct_friends_num[i] - blocked_num[i] - 1
    print(*ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
class UnionFindTree():
  def __init__(self,n):
    self.parent = []
    self.rank = []
    self.candidate = []
    for i in range(n):
      self.parent.append(i)
      self.rank.append(int(1))
      self.candidate.append(int(1))

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

  def unite(self,n,m):
    n = self.find(n)
    m = self.find(m)

    if n == m:
      return
    else:
      if self.rank[n] < self.rank[m]:
        self.parent[n] = m
        self.candidate[m] += self.candidate[n]
      elif self.rank[n] > self.rank[m]:
        self.parent[m] = n
        self.candidate[n] += self.candidate[m]
      elif self.rank[n] == self.rank[m]:
        self.parent[m] = n
        self.candidate[n] += self.candidate[m]
        self.rank[n] += 1




N,M,K = (int(i) for i in input().split())

uft = UnionFindTree(N)

friend = [0] * N
for i in range(M):
  A,B = (int(i) for i in input().split())
  uft.unite(A-1,B-1)
  friend[A-1] += 1
  friend[B-1] += 1




candidate = []
for i in range(N):
  candidate.append(uft.candidate[uft.find(i)])

blocked = [0] * N
for i in range(K):
  C,D = (int(i) for i in input().split())
  if uft.parent[C-1] == uft.parent[D-1]:
    blocked[C-1] += 1
    blocked[D-1] += 1

for i in range(N):
  candidate[i] -= (friend[i]+blocked[i]+1)


print(*candidate)

Solution (Python):
import numpy as np

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

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

        if self.rank[x]>=self.rank[y]:
            self.par[y]=x
        else:
            self.par[x]=y
        if self.rank[x]==self.rank[y]:
            self.rank[x]+=1
        self.size[x]=self.size[y]=self.size[x]+self.size[y]
    
    def rev_size(self,n):
        for i in range(n+1):
            self.size[i]=self.size[self.find(i)]

    def dame_cnt(self,a,b):
        if a!=b:
            self.dame[a]+=1
            self.dame[b]+=1

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

UF=UnionFind(N)

for _ in range(M):
    A,B=map(int,input().split())
    UF.dame_cnt(A,B)
    if UF.same_check(A,B)==0:
        UF.union(A,B)

for _ in range(K):
    C,D=map(int,input().split())
    if UF.same_check(C,D):
        UF.dame_cnt(C,D)

UF.rev_size(N)

print(*list(np.array(UF.size[1:])-np.array(UF.dame[1:])-np.array([1]*(N))))