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



n,m,k=map(int,input().split())
friend={}
block={}


result=[]

friendGroup=[]


for i in range(1,n+1):
    friend[i]=set([])
    block[i]=set([])
    result.append(0)
    friendGroup.append(0)


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


checked=set([])
bfbf=[]
for i in range(1,n+1):
    
    if i not in checked:
        checked.add(i)
        group=set([i])
        bf=set([i])
        friendGroup[i-1]=i
        while len(group)!= 0:
            temp=group.pop()
            for item in friend[temp]:
                if item not in checked:
                    checked.add(item)
                    group.add(item)
                    bf.add(item)
                    
                    friendGroup[item-1]=i
        lenbf=len(bf)
        for item1 in bf:
            result[item1-1]=lenbf-1-len(list(friend[item1]))


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

    
    if friendGroup[a-1]!=0 and friendGroup[a-1]==friendGroup[b-1]:
        result[a-1]-=1
        result[b-1]-=1

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

Solution (Python):



n,m,k=map(int,input().split())
friend={}
block={}
result=[]
friendGroup=[]
for i in range(1,n+1):
    friend[i]=set([])
    block[i]=set([])
    result.append(0)
    friendGroup.append(0)

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

checked=set([])
bfbf=[]
for i in range(1,n+1):
    
    if i not in checked:
        checked.add(i)
        group=set([i])
        bf=set([i])
        friendGroup[i-1]=i
        while len(group)!= 0:
            temp=group.pop()
            for item in friend[temp]:
                if item not in checked:
                    checked.add(item)
                    group.add(item)
                    bf.add(item)
                    friendGroup[item-1]=i
        lenbf=len(bf)
        for item1 in bf:
            result[item1-1]=lenbf-1-len(list(friend[item1]))

for _ in range(k):
    a,b=map(int,input().split())
    if friendGroup[a-1]!=0 and friendGroup[a-1]==friendGroup[b-1]:
        result[a-1]-=1
        result[b-1]-=1

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

Solution (Python):

import sys


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)

n,m,k = map(int,input().split())
friend = [0 for _ in range(n)]
block = [[] for _ in range(n)]
uf = UnionFind(n)

for i in range(m):
    a,b = map(int,input().split())
    friend[a - 1]+=1
    friend[b - 1]+=1
    uf.union(a - 1,b - 1)
for i in range(k):
    c,d = map(int,input().split())
    block[c - 1].append(d - 1)
    block[d - 1].append(c - 1)

for i in range(n):
    ans = uf.size(i) - friend[i] - 1
    for b in block[i]:
        if uf.same(i,b):
            ans-=1
    sys.stdout.write(str(ans) + " ")
print("")

Solution (Python):
import sys

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())
friend =[0]*N
block = {}
for i in range(N):
  block[i] = []
uf = UnionFind(N)
for i in range(M):
  a,b = map(int,input().split())  
  a -= 1;b-=1
  friend[a]+=1
  friend[b]+=1
  uf.union(a,b)
  
for i in range(K):
  c,d = map(int,input().split())
  c -= 1
  d -= 1
  block[c].append(d)
  block[d].append(c)
res = [0]*N
for i in range(N):
  ans = uf.size(i)-1-friend[i]
  for u in block[i]:
    if uf.same(i,u):
      ans -= 1
      
  res[i] = ans
  
print(*res)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)

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

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

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

n,m,k=map(int,input().split())
friends_cand = UnionFind(n)
not_cand = [0 for i in range(n)]

for i in range(m):
    a,b = map(int, input().split())
    a, b = a-1, b-1
    friends_cand.union(a,b)
    not_cand[a] +=1
    not_cand[b] +=1
for i in range(k):
    c,d = map(int, input().split())
    c, d = c-1, d-1
    if friends_cand.find(c) == friends_cand.find(d):
        not_cand[c] +=1
        not_cand[d] +=1

size = [0 for i in range(n)]
for i in range(n):
    size[friends_cand.find(i)]+=1

ans = []
for i in range(n):
    ans.append(size[friends_cand.find(i)] - not_cand[i] - 1)
print(*ans)

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 unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        if self.parents[x] > self.parents[y]:
            rx, ry = ry, rx
        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx

    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

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


n, m, k = map(int, input().split())
friend_cand = UnionFind(n)
friend = {i: set() for i in range(n)}
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    friend[a].add(b)
    friend[b].add(a)
    friend_cand.unite(a, b)
block = {i: set() for i in range(n)}
for _ in range(k):
    c, d = map(lambda x: int(x)-1, input().split())
    block[c].add(d)
    block[d].add(c)

res = []
for i in range(n):
    friend_cnt = len(friend[i])
    block_cnt = 0
    for k in block[i]:
        if friend_cand.same(i, k):
            block_cnt += 1
    res.append(friend_cand.size(i) - friend_cnt - block_cnt - 1)

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

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

def root(x):
  if par[x] == x:
    return x
  else:
    par[x] = root(par[x])
    return par[x]
def unite(x, y):
  x, y = root(x), root(y)
  if x != y:
    if rank[x] < rank[y]:
      par[x] = y
    else:
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
F, B = [], []
for i in range(M):
  a, b = map(int, input().split())
  F.append([a-1, b-1])
  unite(a-1, b-1)
for i in range(N):
  par[i] = root(i)
for i in range(K):
  a, b = map(int, input().split())
  B.append([a-1, b-1])
D = {}
for i in par:
  if i in D:
    D[i] += 1
  else:
    D[i] = 1
p = [0 for _ in range(N)]
for i in range(N):
  p[i] = D[par[i]]
for i in range(M):
  p[F[i][0]] -= 1
  p[F[i][1]] -= 1
for i in range(K):
  l = B[i][:]
  if par[l[0]] == par[l[1]]:
    p[l[0]] -= 1
    p[l[1]] -= 1
for i in range(N):
  if i != N - 1:
    print(p[i] - 1, end = ' ')
  else:
    print(p[i] - 1)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in 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 unite(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)]

person_num, friend_relation_num, block_relation_num = [int(n) for n in input().rstrip().split()]

A, B = [0]*friend_relation_num, [0]*friend_relation_num

C, D = [0]*block_relation_num, [0]*block_relation_num

direct = [[] for _ in range(person_num)]
uf = UnionFind(person_num)

for i in range(friend_relation_num):
    A[i], B[i] = [int(n)-1 for n in input().rstrip().split()]
    direct[A[i]].append(B[i])
    direct[B[i]].append(A[i])
    uf.unite(A[i], B[i])

for i in range(block_relation_num):
    C[i], D[i] = [int(n)-1 for n in input().rstrip().split()]
    if uf.is_same(C[i], D[i]):
        direct[C[i]].append(D[i])
        direct[D[i]].append(C[i])
        

answer = [0]*person_num
for i in range(person_num):
    answer[i] = uf.group_size(i) - len(direct[i]) -1 
    
    
    

print(*answer)

Solution (Python):
class UnionFind():
    def __init__(self,n):
        
        self.d=[-1 for i in range(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):
        x=self.find(x)
        y=self.find(y)
        if(x==y):return False
        if(self.d[x]>self.d[y]):x,y=y,x
        self.d[x]+=self.d[y]
        self.d[y]=x
        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)]
n,m,k=map(int,input().split())
uf=UnionFind(n)
deg=[0 for i in range(n)]
to=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    deg[a]+=1
    deg[b]+=1
for i in range(k):
    a,b=map(int,input().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)
for i in range(n):
    ans=uf.size(i)-1-deg[i]
    for j in to[i]:
        if(uf.same(i,j)):ans-=1
    print(ans,end=" ")

Solution (Python):

class UnionFind():
    def __init__(self,n):
        
        self.d=[-1 for i in range(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):
        x=self.find(x)
        y=self.find(y)
        if(x==y):return False
        if(self.d[x]>self.d[y]):x,y=y,x
        self.d[x]+=self.d[y]
        self.d[y]=x
        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)]

n,m,k=map(int,input().split())
uf=UnionFind(n)
deg=[0 for i in range(n)]
to=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    deg[a]+=1
    deg[b]+=1

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

for i in range(n):
    ans=uf.size(i)-1-deg[i]
    for j in to[i]:
        if(uf.same(i,j)):ans-=1
    print(ans,end=" ")

Solution (Python):

class UnionFind():
    def __init__(self,n):
        
        self.d=[-1 for i in range(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):
        x=self.find(x)
        y=self.find(y)
        if(x==y):return False
        if(self.d[x]>self.d[y]):x,y=y,x
        self.d[x]+=self.d[y]
        self.d[y]=x
        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)]

n,m,k=map(int,input().split())
uf=UnionFind(n)
deg=[0 for i in range(100005)]
to=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    deg[a]+=1
    deg[b]+=1

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

for i in range(n):
    ans=uf.size(i)-1-deg[i]
    for j in to[i]:
        if(uf.same(i,j)):ans-=1
    print(ans,end=" ")

Solution (Python):
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from functools import reduce
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm(a, b):
  return a*b//gcd(a, b)

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n
    
  
  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]
  
  
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    
    if x == y:
      return
    
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    
    self.parents[x] += self.parents[y]
    self.parents[y] = x
  
  
  def size(self, x):
    return -self.parents[self.find(x)]
  
  
  def same(self, x, y):
    return self.find(x) == self.find(y)
  
  
  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]
  
  
  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]
  
  
  def group_count(self):
    return len(self.roots)
  
  
  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}
  
  
  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
  n, m, k = map(int, input().split())
  deg = [0]*n
  ans = [0]*n
  uf = UnionFind(n)
  for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.union(a, b)
  
  for _ in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c,d):
      deg[c] += 1
      deg[d] += 1
  
  for i in range(n):
    ans[i] = uf.size(i) - 1 -deg[i]
  
  print(' '.join(map(str, ans)))
  
if __name__ == '__main__':
  main()

Solution (Python):
from collections import Counter

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

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

class Union:
    def __init__(self, val):
        self.val = val
        self.parent = self
        self.rank = 0
        self.size = 1

    def get_root(self):
        n = self
        while n.parent != n:
            n = n.parent
        return n

    def find_set(self):
        return self.get_root().val


unions = []
for i in range(n):
    unions.append(Union(i))

for a, b in friends:
    x, y = unions[a], unions[b]
    if x.find_set() == y.find_set():
        continue
    x_root, y_root = x.get_root(), y.get_root()
    if x_root.rank == y_root.rank:
        y_root.parent = x_root
        x_root.rank += 1
    elif x_root.rank > y_root.rank:
        y_root.parent = x_root
    else:
        x_root.parent = y_root
    size = x_root.size + y_root.size
    x_root.size = size
    y_root.size = size

d = {}
relation = []
for i in range(n):
    u = unions[i]
    parent = u.find_set()
    relation.append(parent)

parents = Counter(relation)
for i in range(n):
    p = relation[i]
    relation[i] = [p, parents.get(p)]

ans = []
for i in range(n):
    t = relation[i][1] - 1
    parent = relation[i][0]
    for j in graph[i]:
        if relation[j][0] == parent:
            t -= 1
    for k in block[i]:
        if relation[k][0] == parent:
            t -= 1
    ans.append(t)

print(*ans)

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

    def Find(self, x):
        if self.par[x] < 0:
            return x
        self.par[x] = self.Find(self.par[x])
        return self.par[x]

    def Union(self, x, y):
        x = self.Find(x)
        y = self.Find(y)
        if (x==y): 
            return False
        if (self.par[x]>self.par[y]):
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return True
    
    def isSameGroup(self, x, y):
        return self.Find(x)==self.Find(y)
    
    def Size(self, x):
        return self.par[self.Find(x)]*-1
    
    def PrintTree(self):
        return self.par

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

uf = UnionFind(N)
deg = [0]*N
ans = [0]*N
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.Union(a, b)

for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.isSameGroup(c, d):
        deg[c] += 1
        deg[d] += 1

for i in range(N):
    ans[i] = uf.Size(i)-1-deg[i]

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

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


class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


def solve():
    N, M, K = map(int, input().split())
    uft = UnionFind(N)
    d = {i:set() for i in range(1, N+1)}
    e = {i:0 for i in range(1, N+1)}
    f = {i:0 for i in range(1, N+1)}

    for _ in range(M):
        A, B = map(int, input().split())
        d[A].add(B)
        d[B].add(A)
        f[A] += 1
        f[B] += 1
        uft.unite(A, B)

    for _ in range(K):
        C, D = map(int, input().split())
        if uft.isunited(C, D):
            if D not in d[C]:
                e[C] += 1
            if C not in d[D]:
                e[D] += 1
    
    g = lambda x:uft.getsize(x)-e[x]-f[x]-1
    print(*map(g, range(1, N+1)))


if __name__ == "__main__":
    solve()

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


class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


def solve():
    N, M, K = map(int, input().split())
    uft = UnionFind(N)
    d = {i:set() for i in range(1, N+1)}
    e = {i:0 for i in range(1, N+1)}
    f = {i:0 for i in range(1, N+1)}

    for _ in range(M):
        A, B = map(int, input().split())
        d[A].add(B)
        d[B].add(A)
        f[A] += 1
        f[B] += 1
        uft.unite(A, B)

    for _ in range(K):
        C, D = map(int, input().split())
        if uft.isunited(C, D):
            if not D in d[C]:
                e[C] += 1
            if not C in d[D]:
                e[D] += 1

    print(*(uft.getsize(i)-e[i]-f[i]-1 for i in range(1, N+1)))


if __name__ == "__main__":
    solve()

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


class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


def solve():
    N, M, K = map(int, input().split())
    uft = UnionFind(N)
    d = {i:set() for i in range(1, N+1)}
    e = {i:0 for i in range(1, N+1)}
    f = {i:0 for i in range(1, N+1)}

    for _ in range(M):
        A, B = map(int, input().split())
        d[A].add(B)
        d[B].add(A)
        f[A] += 1
        f[B] += 1
        uft.unite(A, B)

    for _ in range(K):
        C, D = map(int, input().split())
        if uft.isunited(C, D):
            if not D in d[C]:
                e[C] += 1
            if not C in d[D]:
                e[D] += 1

    print(*(uft.getsize(i)-e[i]-f[i]-1 for i in range(1, N+1)))


if __name__ == "__main__":
    solve()

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

"""
Union-Find木実装のキモ(計算量削減)
1. Unionの工夫
   マージテク：大きい方を動かさずに小さい方をくっつける
2. Findの工夫
   経路圧縮 : 集合の要素を根に直接つなぎ変える.木をフラットにする.
"""


class UnionFind:
    
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0

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

    
    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

blocks = [[] for _ in range(N)]
for c, d in CD:
    c, d = c-1, d-1
    blocks[c].append(d)
    blocks[d].append(c)


friends = [0] * N
uf = UnionFind(N)
for a,b in AB:
    a, b = a-1, b-1
    friends[a] += 1
    friends[b] += 1
    
    if uf.is_same(a, b): continue
    
    uf.unite(a, b)

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

from collections import Counter
ctr = Counter()
for i in range(N):
    r = uf.root(i)
    ctr[r] += 1

ans = []
for i in range(N):
    tmp = ctr[uf.root(i)] - friends[i] -1
    for b in blocks[i]:
        if uf.is_same(i, b):
            tmp -= 1
    ans.append(tmp)
print(*ans)

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

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

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

        if x == y:
            return

        
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x

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

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


n, m, k = map(int, input().split())
num_friends = [0 for _ in range(n + 1)]
blocks = [[] for _ in range(n + 1)]
uf = UnionFind(n + 1)

for i in range(m):
    a, b = map(int, input().split())
    num_friends[a] += 1
    num_friends[b] += 1
    uf.unite(a, b)

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

out = ''
for i in range(1, n + 1):
    ans = uf.size(i) - num_friends[i] - 1
    for block in blocks[i]:
        if uf.same(i, block):
            ans -= 1
    out += str(ans) + ' '
print(out.strip())

Solution (Python):
 



from sys import setrecursionlimit
setrecursionlimit(10**8)
n, m, k = map(int, input().split())
par = [i for i in range(n)]
ans = [0 for _ in range(n)]


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


def union(x, y):
    if x > y:
        x, y = y, x
    rx, ry = root(x), root(y)
    if rx != ry:
        par[ry] = rx


friends = [[] for _ in range(n)]
blocks = [[] for _ in range(n)]

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


group_count = [0 for _ in range(n)]
for i in range(n):
    group_count[root(i)] += 1

for i in range(n):
    
    ans[i] += group_count[root(i)]
    
    ans[i] -= len(friends[i])
    
    for b in blocks[i]:
        ra, rb = root(i), root(b)
        if ra == rb:
            ans[i] -= 1
    
    ans[i] -= 1
print(" ".join(list(map(str, ans))))

Solution (Python):
from collections import defaultdict

class UnionFind:
  def __init__(self, n):
    self.parents = list(range(n))
    self.ranks = [0] * n

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

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

  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if x == y:
      return
    if self.ranks[x] < self.ranks[y]:
      self.parents[x] = y
    else:
      self.parents[y] = x
      if self.ranks[x] == self.ranks[y]:
        self.ranks[x] += 1

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

for _ in range(k):
  a, b = map(int, input().split())
  if u.same(a - 1, b - 1):
    counts[a - 1] += 1
    counts[b - 1] += 1

groups = defaultdict(int)
for i in range(n):
  groups[u.root(i)] += 1

print(*[groups[u.root(i)] - counts[i] for i in range(n)])

Solution (Python):
"""
unioufind
集合の中で、直接の友達 と直接のブロックを引く
TLE

bfsで集合をまず見ておく
"""
from collections import deque
from collections import defaultdict
N,M,K = map(int, input().split())


G = defaultdict(list)
for i in range(M):
    
    u,v = map(int,input().split())
    G[u-1].append((v-1))
    G[v-1].append((u-1))

tomodachi_group = defaultdict(int)
used = [False] * N
parent = [-1] * N
group_cnt = {}
for i in range(N):
    if used[i]: continue
    used[i] = True
    parent[i] = i
    q = deque([])
    q.append(i)
    cnt = 0
    while len(q) > 0:
        a = q.popleft()
        Vs = G[a]
        for u in Vs:
            if not used[u]:
                q.append(u)
                parent[u] = i
                used[u] = True
                cnt += 1
    group_cnt[i] = cnt

block = defaultdict(int)
for i in range(K):
    c,d = map(int, input().split())
    c -= 1
    d -= 1
    
    if parent[c] != parent[d] :continue
    block[c] += 1
    block[d] += 1

ans = []
for i in range(N):
    cnt = group_cnt[parent[i]] - len(G[i]) - block[i]
    ans.append(cnt)
print(*ans)