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

    def __init__(self, N):
        self.parents = [i for i in range(N)]
        self.size = [1]*N

    def find_parent(self, x):
        path = []
        while self.parents[x] != x:
            x = self.parents[x]
            path.append(x)
        for p in path:
            self.parents[p] = x
        return x

    def find_size(self, x):
        return self.size[self.find_parent(x)]

    def union(self, x, y):
        root_x = self.find_parent(x)
        root_y = self.find_parent(y)
        if self.find_parent(root_x) != self.find_parent(root_y):
            self.parents[root_x] = root_y
            self.size[root_y] += self.size[root_x]


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M, K = read_ints()
    disjoint_set = DisjointSet(N)
    suggestions = [-1]*N
    for _ in range(M):
        a, b = read_ints()
        a -= 1
        b -= 1
        disjoint_set.union(a, b)
        suggestions[a] -= 1
        suggestions[b] -= 1
    for _ in range(K):
        c, d = read_ints()
        c -= 1
        d -= 1
        if disjoint_set.find_parent(c) == disjoint_set.find_parent(d):
            suggestions[c] -= 1
            suggestions[d] -= 1
    return [disjoint_set.find_size(i)+suggestions[i] for i in range(N)]


if __name__ == '__main__':
    print(*solve())

Solution (Python):

from typing import Iterable
import sys
def main(N, M, K, AB, CD):
    friend_chain = UnionFindTree(N)
    friend_count = [0] * N
    block_count = [0] * N
    for a, b in AB:
        a, b = a - 1, b - 1
        friend_chain.union(a, b)
        friend_count[a] += 1
        friend_count[b] += 1
    for c, d in CD:
        c, d = c - 1, d - 1
        if friend_chain.same(c, d):
            block_count[c] += 1
            block_count[d] += 1
    print(*[friend_chain.size(i) - 1 - friend_count[i] - block_count[i] for i in range(N)])

class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.parent = [-1] * n

    def find(self, x: int) -> int:
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x: int, y: int) -> bool:
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

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

    def same_all(self, indices: Iterable[int]) -> bool:
        f, v = self.find, self.find(indices[0])
        return all(f(i) == v for i in indices)

if __name__ == '__main__':
    input = sys.stdin.readline
    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)]
    main(N, M, K, AB, CD)

Solution (Python):
from collections import deque

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



ad={} 
block={} 
for n in range(N):
    n=n+1
    ad[n]=set([])
    block[n]=set([])
    
for m in range(M):
    m1,m2 = list(map(int,input().split()))
    ad[m1].add(m2)
    ad[m2].add(m1)

for k in range(K):
    k1,k2 = list(map(int,input().split()))
    block[k1].add(k2)
    block[k2].add(k1)

visit = deque([])
color={}
tree={}
t=0
for n in range(N):
    n=n+1
    color[n] = -1
    tree[n] = -1
    
start_ = 1
    
while len(visit) < N:
    t += 1
    for c_k in range(start_,N):
        if color[c_k] == -1:
            start = c_k
            start_ = start + 1
            break
    color[start] = 0
    tree[start] = t
    visit_temp=deque([start])

    while len(visit_temp) > 0: 
        start=visit_temp[0]
        for v in ad[start] :
            if color[v] == -1: 
                visit_temp.append(v)
                color[v] = 0
                
        color[start] = 1
        tree[start] = t
        
        pop_ = visit_temp.popleft()
        visit.append(pop_)
        
tree_={}
for v in set(tree.values()):
    tree_[v]=set()
    
for k in set(tree.keys()):
    tree_[tree[k]].add(k)
    
ans=[]
for n in range(N):

    n=n+1
    
    tree_len=len(tree_[tree[n]])
    friend_len=len(ad[n])
    
    brock_len=0
    for b in block[n]:
        if tree[n] == tree[b]:
            brock_len += 1
            


    ans.append(tree_len-friend_len-brock_len-1)
            
print(' '.join(map(str,ans)))

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

class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
        self.sizes = [1] * numV
    def getRoot(self, x):
        par = self.pars[x]
        if par != x:
            self.pars[x] = par = self.getRoot(par)
        return par
    def merge(self, x, y):
        x, y = self.getRoot(x), self.getRoot(y)
        sx, sy = self.sizes[x], self.sizes[y]
        if x == y: return (0, 0)
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
            self.sizes[y] += sx
        else:
            self.pars[y] = x
            self.sizes[x] += sy
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
        return (sx, sy)
    def isSame(self, x, y):
        return self.getRoot(x) == self.getRoot(y)
    def updatePars(self):
        for v in range(len(self.pars)):
            self.getRoot(v)
    def getSize(self, x):
        return self.sizes[self.getRoot(x)]

N, M, K = map(int, input().split())
UF = UnionFind(N)
anss = [-1] * N
for _ in range(M):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    UF.merge(A, B)
    anss[A] -= 1
    anss[B] -= 1

for i in range(N):
    anss[i] += UF.getSize(i)

for _ in range(K):
    C, D = map(int, input().split())
    C, D = C-1, D-1
    if UF.isSame(C, D):
        anss[C] -= 1
        anss[D] -= 1

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

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

par=[-1]*N
num=[0]*N

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

def union(x,y):
  p,q=find(x),find(y)
  if p==q:
    return
  if p>q:
    p,q=q,p
  par[p]+=par[q]
  par[q]=p   

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

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

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

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

for i in range(N):
  print(size(i)-1-num[i],end=" ")

Solution (Python):
from collections import deque


def init_tree(x, par):
    for i in range(x + 1):
        par[i] = i


def find(x, par):
    q = deque()
    q.append(x)
    while len(q) > 0:
        v = q.pop()
        if v == par[v]:
            return v
        q.append(par[v])


def union(x, y, par, rank):
    px, py = find(x, par), find(y, par)
    if px == py:
        return
    if rank[px] < rank[py]:
        par[px] = py
        return
    elif rank[px] == rank[py]:
        rank[px] += 1
    par[py] = px


n, m, k = map(int, input().split())
par = [0] * (n + 1)
rank = [0] * (n + 1)
init_tree(n, par)
eg = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    union(a, b, par, rank)
    eg[a].append(b)
    eg[b].append(a)
for _ in range(k):
    a, b = map(int, input().split())
    eg[a].append(b)
    eg[b].append(a)

xs = [0] * (n + 1)
ys = [0] * (n + 1)
for i in range(1, n + 1):
    p = find(i, par)
    xs[p] += 1
    for v in eg[i]:
        if p == find(v, par):
            ys[i] += 1

ans = [-1] * (n + 1)
for i in range(1, n + 1):
    ans[i] += xs[find(i, par)] - ys[i]
ans = [-1] * (n + 1)
for i in range(1, n + 1):
    ans[i] += xs[find(i, par)] - ys[i]
print(*ans[1:])

Solution (Python):
from collections import deque


def init_tree(x, par):
    for i in range(x + 1):
        par[i] = i


def find(x, par):
    q = deque()
    q.append(x)
    while len(q) > 0:
        v = q.pop()
        if v == par[v]:
            return v
        q.append(par[v])


def union(x, y, par, rank):
    px, py = find(x, par), find(y, par)
    if px == py:
        return
    if rank[px] < rank[py]:
        par[px] = py
        return
    elif rank[px] == rank[py]:
        rank[px] += 1
    par[py] = px


n, m, k = map(int, input().split())
par = [0] * (n + 1)
rank = [0] * (n + 1)
init_tree(n, par)
eg = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    union(a, b, par, rank)
    eg[a].append(b)
    eg[b].append(a)
for _ in range(k):
    a, b = map(int, input().split())
    eg[a].append(b)
    eg[b].append(a)

xs = [0] * (n + 1)
ys = [0] * (n + 1)
for i in range(1, n + 1):
    p = find(i, par)
    xs[p] += 1
    for v in eg[i]:
        if p == find(v, par):
            ys[i] += 1

ans = [-1] * (n + 1)
for i in range(1, n + 1):
    ans[i] += xs[find(i, par)] - ys[i]
print(*ans[1:])

Solution (Python):
N, M, K = map(int, input().split())
friend = {}
for i in range(M):
    A, B = map(lambda x: x-1, map(int, input().split()))
    if A not in friend:
        friend[A] = []
    if B not in friend:
        friend[B] = []
    friend[A].append(B)
    friend[B].append(A)

block = {}
for i in range(K):
    C, D = map(lambda x: x-1, map(int, input().split()))
    if C not in block:
        block[C] = []
    if D not in block:
        block[D] = []
    block[C].append(D)
    block[D].append(C)

first = {}
for i in range(N):
    if i not in first:
        first[i] = i
        if i in friend:
            queue = []
            queue.extend(friend[i])
            counter = 0
            while counter < len(queue):
                item = queue[counter]
                first[item] = i
                if item in friend:
                    for n in friend[item]:
                        if n not in first:
                            queue.append(n)
                counter += 1

size = {}
for key in first:
    if first[key] not in size:
        size[first[key]] = 1
    else:
        size[first[key]] += 1

for i in range(N):
    if i not in friend:
        print(0)
        continue
    no_friend = 0
    if i in block:
        for b in block[i]:
            if first[b] == first[i]:
                no_friend += 1
    print(size[first[i]] - len(friend[i]) - no_friend - 1)

Solution (Python):
N,M,K = list(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)      
V = [[] for _ in range(N)]

for _ in range(M):
  a,b = map(int, input().split())
  a,b = a-1, b-1
  V[a].append(b)
  V[b].append(a)
  uf.union(a,b)
  
for _ in range(K):
  a,b = map(int, input().split())
  a,b = a-1, b-1
  if uf.same(a,b):
    V[a].append(b)
    V[b].append(a)

ans = [-1] * N
for i in range(N):
  ans[i] = uf.size(i) - len(V[i]) - 1
  
print(" ".join(list(map(str, ans))))

Solution (Python):
N,M,K = list(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)      
V = [[] for _ in range(N)]

for _ in range(M):
  a,b = map(int, input().split())
  a,b = a-1, b-1
  V[a].append(b)
  V[b].append(a)
  uf.union(a,b)
  
for _ in range(K):
  a,b = map(int, input().split())
  a,b = a-1, b-1
  if uf.same(a,b):
    V[a].append(b)
    V[b].append(a)

ans = [-1] * N
for i in range(N):
  ans[i] = uf.size(i) - len(V[i]) - 1
  
print(" ".join(list(map(str, ans))))

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

import sys
sys.setrecursionlimit(10**9)
n,m,k=[int(i) for i in input().split()]
frends_num=[0 for i in range(n)]
def make_frends(m,n):
    data=[1 for i in range(m)]

    row=[]
    col=[]
    for k in range(m):
        i,j=[int(l) for l in input().split()]
        new_i=min(i,j)-1
        new_j=max(i,j)-1
        row.append(new_i)
        col.append(new_j)
        frends_num[new_i]+=1
        frends_num[new_j]+=1
    frend_sparce_matrix=csr_matrix((data, (row, col)),shape=(n,n))
    return frend_sparce_matrix


frends=make_frends(m,n)
l,labels=connected_components(frends)
labels
labels=list(labels)

class Group:
    def __init__(self,labels):
        self.labels=labels
        self.group_num=[0 for i in range(l)]
        for i in labels:
            self.group_num[i]+=1
    def get_group_num(self,i):
        return self.group_num[self.labels[i]]

group=Group(labels)


def get_frend_num(i):
    return frends_num[i]


def make_block(k,n):
    block_num=[0 for i in range(n)]
    for p in range(k):
        i,j =[int(l)-1 for l in input().split()]
        new_i=min(i,j)
        new_j=max(i,j)
        if labels[new_i]==labels[new_j]:
            block_num[i]+=1
            block_num[j]+=1
    return block_num

block=make_block(k,n)

def get_block_num(i):
    return block[i]

ans=[]
for i in range(n):
    ans.append(str(group.get_group_num(i)-1-get_frend_num(i)-get_block_num(i)))
print(" ".join(ans))

Solution (Python):
import sys

sys.setrecursionlimit(100000)



class UnionFind:
    """
    子ノードには自分の親ノードIDを記録。親ノードにはグループサイズの負値を記録。
    """

    def __init__(self, n):
        self.node = [-1] * n
    
    def unite(self, x, y):
        """
        xとyが属するグループを統合
        """
        
        _x, _y = self.find(x), self.find(y)
        
        
        if _x == _y:
            return False
        
        
        
        
        if abs(self.node[_x]) < abs(self.node[_y]):
             self.node[_x], self.node[_y] = self.node[_y], self.node[_x]
        
        self.node[_x] += self.node[_y]
        
        self.node[_y] = _x
        return True

    def find(self, x):
        """
        xが属するグループの親ノードインデックスを検索。
        """
        _val = self.node[x]
        
        if _val < 0: 
            return x
        
        
        
        self.node[x] = self.find(_val)
        return self.node[x]

    def same(self, x, y):
        """
        xとyが属するグループが同じかチェック。
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        xが属するグループの総サイズ取得
        """
        return abs(self.node[self.find(x)])
 
    def __str__(self):
        return str(self.node)

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

uf = UnionFind(N)
friend = [0] * N
block = [[] for _ in range(N)]

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

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

for i in range(N):
    ans = uf.size(i) - friend[i] - 1
    for j in block[i]:
        if uf.same(i, j):
            ans -= 1
    print("{} ".format(ans), end="")
print("")

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


def main():
  N, M, K = list(map(int, input().split()))

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

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

  num_cand = [-1]*(N)
  member = {}
  group = {}

  for i in range(N):
    if i in group:
      continue
    start = i
    
    q = deque([start])
    member[start] = set([start])
    group[start] = start
    is_visited = set([start])
    while len(q):
      now = q.popleft()
      for next_ in friends[now]:
        num_cand[now] -= 1
        
        if next_ not in is_visited:
          member[start].add(next_)
          group[next_] = start
          
          
          
          
          q.append(next_)
          is_visited.add(next_)

  
  
  for i in range(N):
    num_cand[i] += len(member[group[i]])
    for enemy in block[i]:
      if enemy in member[group[i]]:
        num_cand[i] -= 1

  print(*num_cand, sep=' ')


if(__name__ == '__main__'):
  main()

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

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

F = [[] for _ in range(n+1)]
B = [[] for _ in range(n+1)]

for _ in range(m):
    x,y = map(int, input().split())
    F[x].append(y)
    F[y].append(x)

for _ in range(k):
    x,y = map(int, input().split())
    B[x].append(y)
    B[y].append(x)

belongs = [-1 for _ in range(n+1)]
group_ID = 0

def f_search(root, group_ID):
    for j in F[root]:
        if belongs[j] == -1:
            belongs[j] = group_ID
            f_search(j, group_ID)

for i in range(n+1):
    if belongs[i] == -1:
        belongs[i] = group_ID
        f_search(i, group_ID)
        group_ID += 1

cnt_members = [0 for _ in range(len(set(belongs)))]
for i in belongs[1:]:
    cnt_members[i] += 1

ans = [0 for _ in range(n+1)]
for i in range(1, n+1):
    tmp = 0
    for j in B[i]:
        if belongs[j] == belongs[i]:
            tmp += 1
    ans[i] = cnt_members[belongs[i]] - 1 - len(F[i]) - tmp

print(*ans[1:])

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

friend = [[] for i in range(n)]
block = [[] 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 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())
    a-=1
    b-=1
    uf.union(a,b)
    friend[a].append(b)
    friend[b].append(a)

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

ans=[]

for i in range(n):
    ans1 = uf.size(i)-1
    for j in block[i]:
        if uf.same(i,j):
            ans1-=1
    ans1 -= len(friend[i])
    ans.append(str(ans1))

print(' '.join(ans))

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

import sys
sys.setrecursionlimit(10**9)
n,m,k=[int(i) for i in input().split()]
frends_num=[0 for i in range(n)]
def make_frends(m,n):
    data=[1 for i in range(m)]

    row=[]
    col=[]
    for k in range(m):
        i,j=[int(l) for l in input().split()]
        new_i=min(i,j)-1
        new_j=max(i,j)-1
        row.append(new_i)
        col.append(new_j)
        frends_num[new_i]+=1
        frends_num[new_j]+=1
    frend_sparce_matrix=csr_matrix((data, (row, col)),shape=(n,n))
    return frend_sparce_matrix


frends=make_frends(m,n)
l,labels=connected_components(frends)
labels
labels=list(labels)

class Group:
    def __init__(self,labels):
        self.labels=labels
        self.group_num=[0 for i in range(l)]
        for i in labels:
            self.group_num[i]+=1
    def get_group_num(self,i):
        return self.group_num[self.labels[i]]

group=Group(labels)


def get_frend_num(i):
    return frends_num[i]


def make_block(k,n):
    block_num=[0 for i in range(n)]
    for p in range(k):
        i,j =[int(l)-1 for l in input().split()]
        new_i=min(i,j)
        new_j=max(i,j)
        if labels[new_i]==labels[new_j]:
            block_num[i]+=1
            block_num[j]+=1
    return block_num

block=make_block(k,n)

def get_block_num(i):
    return block[i]

ans=[]
for i in range(n):
    ans.append(str(group.get_group_num(i)-1-get_frend_num(i)-get_block_num(i)))
print(" ".join(ans))

Solution (Python):
f=lambda:map(int,input().split())
n,m,k=f()


p=[-1]*n
def root(x):
  while p[x]>=0: x=p[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return -p[root(x)]

l=[-1]*n
for _ in range(m):
  a,b=f()
  unite(a-1,b-1)
  l[a-1]-=1
  l[b-1]-=1
for i in range(n):
  l[i]+=size(i)
for _ in range(k):
  c,d=f()
  if same(c-1,d-1):
    l[c-1]-=1
    l[d-1]-=1
print(*l)

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}
    stack.append(i)
    visited[i] = 1
    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,collections
input = sys.stdin.readline

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)]

          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    s = set(range(1,N+1))
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            s.discard(now)
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        
            
        
            
        if len(s) == 0:
            nxt = 0
        else:
            nxt = s.pop()


    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        mbf.append(ff)
    print(*mbf)

if __name__ == '__main__':
    main()

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

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)]

          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    s = set(range(1,N+1))
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            s.discard(now)
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        
            
        
            
        if len(s) == 0:
            nxt = 0
        else:
            nxt = s.pop()


    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        mbf.append(ff)
    print(*mbf)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

for _ in range(m):
    a, b = map(int, input().split())
    friend[a - 1].add(b - 1)
    friend[b - 1].add(a - 1)
for _ in range(k):
    a, b = map(int, input().split())
    block[a - 1].add(b - 1)
    block[b - 1].add(a - 1)
visited = [0 for _ in range(n)]
ans = [None for _ in range(n)]
for i in range(n):
    if visited[i]:
        continue
    prefriends = {i}
    check = deque([i])
    while check:
        now = check.pop()
        visited[now] = 1
        for next in friend[now]:
            if visited[next] == 0:
                check.append(next)
                prefriends.add(next)
    for j in prefriends:
        ans[j] = len(prefriends) - 1 - len(friend[j]) - len(prefriends & block[j])
print(' '.join(list(map(str, ans))))

Solution (Python):
import sys
from collections import defaultdict


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2

    def friend_candidate(self):
        tbl = self.table
        n = len(tbl)
        candidates = [0] * n
        root = [-1] * n
        for i, parent in enumerate(tbl):
            if parent >= 0:
                root[i] = self._root(parent)
                candidates[root[i]] += 1
        for i in range(n):
            if tbl[i] >= 0:
                candidates[i] = candidates[root[i]]
        return candidates


def main():
    input = sys.stdin.buffer.readline
    n, m, k = map(int, input().split())
    uf = UnionFind(n)
    num_friends = [0] * n
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        uf.union(a, b)
        num_friends[a] += 1
        num_friends[b] += 1
    num_block = [0] * n
    for _ in range(k):
        c, d = map(lambda x: int(x) - 1, input().split())
        if uf.find(c, d):
            num_block[c] += 1
            num_block[d] += 1
    fc = uf.friend_candidate()
    ans = [0] * n
    for i in range(n):
        ans[i] = fc[i] - num_friends[i] - num_block[i]
    print(*ans)


if __name__ == "__main__":
    main()