Problem:
 Score : 400 points    Problem Statement An SNS has N users - User 1 , User 2 , \cdots , User N .  Between these N users, there are some relationships - M  friendships and K  blockships .  For each i = 1, 2, \cdots, M , there is a bidirectional friendship between User A_i and User B_i .  For each i = 1, 2, \cdots, K , there is a bidirectional blockship between User C_i and User D_i .  We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:   a \neq b .  There is not a friendship between User a and User b .  There is not a blockship between User a and User b .  There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a , c_L = b , and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1 .   For each user i = 1, 2, ... N , how many friend candidates does it have?      Constraints  All values in input are integers.  2 ≤ N ≤ 10^5  0 \leq M \leq 10^5  0 \leq K \leq 10^5  1 \leq A_i, B_i \leq N  A_i \neq B_i  1 \leq C_i, D_i \leq N  C_i \neq D_i  (A_i, B_i) \neq (A_j, B_j) (i \neq j)  (A_i, B_i) \neq (B_j, A_j)  (C_i, D_i) \neq (C_j, D_j) (i \neq j)  (C_i, D_i) \neq (D_j, C_j)  (A_i, B_i) \neq (C_j, D_j)  (A_i, B_i) \neq (D_j, C_j)         Input Input is given from Standard Input in the following format:  N  M  K  A_1  B_1  \vdots  A_M  B_M  C_1  D_1  \vdots  C_K  D_K       Output Print the answers in order, with space in between.        Sample Input 1 4 4 1
2 1
1 3
3 2
3 4
4 1      Sample Output 1 0 1 0 1  There is a friendship between User 2 and 3 , and between 3 and 4 . Also, there is no friendship or blockship between User 2 and 4 . Thus, User 4 is a friend candidate for User 2 .  However, neither User 1 or 3 is a friend candidate for User 2 , so User 2 has one friend candidate.       Sample Input 2 5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5      Sample Output 2 0 0 0 0 0  Everyone is a friend of everyone else and has no friend candidate.       Sample Input 3 10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1      Sample Output 3 1 3 5 4 3 3 3 3 1 0

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(1000000)
input = lambda: sys.stdin.readline().rstrip()


class UnionFind:
    def __init__(self, size):
        self.par = [i for i in range(size)]
        self.rk = [0] * size

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rk[x] < self.rk[y]:
            self.par[x] = y
        elif self.rk[x] > self.rk[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            self.rk[y] += 1


N, M, K = map(int, input().split())
uf = UnionFind(N)
friend = defaultdict(set)
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    uf.unite(a, b)
    friend[a].add(b)
    friend[b].add(a)

block = defaultdict(set)
for _ in range(K):
    c, d = map(lambda x: int(x) - 1, input().split())
    block[c].add(d)
    block[d].add(c)

group = defaultdict(set)
for i in range(N):
    group[uf.find(i)].add(i)

ans = [0] * N
for people in group.values():
    for p in people:
        ans[p] = len(people) - 1 - sum(1 if i in people else 0 for i in friend[p]) - sum(1 if i in people else 0 for i in block[p])

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

Solution (Python):
class Union:
  def __init__(s, num):
    s.T = [-1 for i in range(num)]
 
  def root(s, x):
    if s.T[x] < 0: return x, -s.T[x]
    t, k = s.root(s.T[x])
    s.T[x] = t
    return t, k
 
  def merge(s, x, y):
    an, am = s.root(x)
    bn, bm = s.root(y)
    if an == bn: return False
    if am < bm: an, bn  = bn, an
    s.T[an] += s.T[bn]
    s.T[bn] = an
    return True
 
  def size(s, x):
    return s.root(x)[1]

  def same(s, x, y):
    return s.root(x)[0] == s.root(y)[0]

import sys
input = sys.stdin.readline

N, M, K = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]
 
uni = Union(N)
ans = [-1] * N
for a, b in AB:
  a -= 1
  b -= 1
  uni.merge(a, b)
  ans[a] -= 1
  ans[b] -= 1
 
L = [[] for _ in range(N)]
for c, d in CD:
  c -= 1
  d -= 1
  L[c].append(d)
  L[d].append(c)
 
for i in range(N):
  ans[i] += uni.size(i)
  for j in L[i]:
    if uni.same(i, j):
      ans[i] -= 1
 
ans = map(str, ans)
print(" ".join(ans))

Solution (Python):
class Union:
  def __init__(s, num):
    s.T = [-1 for i in range(num)]
 
  def root(s, x):
    if s.T[x] < 0: return x, -s.T[x]
    t, k = s.root(s.T[x])
    s.T[x] = t
    return t, k
 
  def merge(s, x, y):
    an, am = s.root(x)
    bn, bm = s.root(y)
    if an == bn: return False
    if am < bm: an, bn  = bn, an
    s.T[an] += s.T[bn]
    s.T[bn] = an
    return True
 
  def size(s, x):
    return s.root(x)[1]

  def same(s, x, y):
    return s.root(x)[0] == s.root(y)[0]

N, M, K = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]
 
uni = Union(N)
ans = [-1] * N
for a, b in AB:
  a -= 1
  b -= 1
  uni.merge(a, b)
  ans[a] -= 1
  ans[b] -= 1
 
L = [[] for _ in range(N)]
for c, d in CD:
  c -= 1
  d -= 1
  L[c].append(d)
  L[d].append(c)
 
for i in range(N):
  ans[i] += uni.size(i)
  for j in L[i]:
    if uni.same(i, j):
      ans[i] -= 1
 
ans = map(str, ans)
print(" ".join(ans))

Solution (Python):
class unionfind:
    def __init__(self,n): 
        self.par=[-1]*(n+1) 
        
    def find(self,x): 
        if self.par[x]<0:
            return x 
        else:
            self.par[x]=self.find(self.par[x]) 
            return self.par[x]
        
    def union(self,x,y): 
        x=self.find(x) 
        y=self.find(y) 
        if x==y: 
            return
        if self.par[y]<self.par[x]: 
            x,y=y,x
        
        self.par[x]+=self.par[y]
        self.par[y]=x
        
                
    def same_check(self,x,y): 
        return self.find(x)==self.find(y)
    
    def size(self,x):
        return -self.par[self.find(x)] 

n,m,k=map(int,input().split())
uf=unionfind(n)
kankei=[0]*(n+1) 
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a,b)
    kankei[a]+=1
    kankei[b]+=1
for i in range(k):
    c,d=map(int,input().split())
    if uf.same_check(c,d):
        kankei[c]+=1
        kankei[d]+=1
for i in range(1,n+1):
    print(str(uf.size(i)-kankei[i]-1),end=" ")

Solution (Python):

import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    from collections import defaultdict
    from collections import deque

    N,M,K = LMIIS()
    AB = XLMIIS(M)
    CD = XLMIIS(K)
    edge = defaultdict(set)
    redge = defaultdict(set)
    blocks = defaultdict(set)
    
    for a,b in AB:
        
        
        edge[a].add(b)
        
        edge[b].add(a)
    for c,d in CD:
        
        
        blocks[c].add(d)
        blocks[d].add(c)
        
        

    visited = [False] * (N+1)
    
    num_graph = 0
    which_graph = [-1] * (N+1)
    num_grapth_node = [0] * N

    friends = deque()
    

    for i in range(1,N+1):
        if visited[i]:
            continue
        friends.append(i)
        while len(friends) > 0:
            node = friends.pop()
            if visited[node]:
                continue
            visited[node] = True
            which_graph[node] = num_graph
            num_grapth_node[num_graph] += 1
            for e in edge[node]:
                friends.append(e)
        num_graph+=1


    for i in range(1,N+1):
        num_friends = 0
        for f in edge[i]:
            if which_graph[i] == which_graph[f]:
                num_friends += 1
        num_blocks = 0
        for b in blocks[i]:
            if which_graph[i] == which_graph[b]:
                num_blocks += 1
        print(num_grapth_node[which_graph[i]] - num_friends - num_blocks -1)









    

if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind:
  def __init__(self, N):
    self.par=[i for i in range(N)]
    self.rank=[0 for _ in range(N)]
    self.size=[1 for _ in range(N)]
    
  def unite(self, x, y):
    x=self.getroot(x)
    y=self.getroot(y)
    if x!=y:
      if self.rank[x]<self.rank[y]:
        x, y=y, x
      if self.rank[x]==self.rank[y]:
        self.rank[x]+=1
      self.par[y]=x
      self.size[x]+=self.size[y]
      
  def united(self, x, y):
    return self.getroot(x)==self.getroot(y)
      
  def getroot(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x]=self.getroot(self.par[x])
      return self.par[x]

  def getsize(self, x):
    return self.size[self.getroot(x)]
  
def LN2NL(N, LN):
  out=[[] for _ in range(N)]
  M=len(LN)
  for i in range(M):
    out[LN[i][0]].append(LN[i][1])
    out[LN[i][1]].append(LN[i][0])
  return out

N, M, K=map(int, input().split())
UF=UnionFind(N+1)
AB=[list(map(int, input().split())) for _ in range(M)]
CD=[list(map(int, input().split())) for _ in range(K)]
ABNL=LN2NL(N+1, AB)
CDNL=LN2NL(N+1, CD)

for i in range(M):
  UF.unite(AB[i][0], AB[i][1])
  
ans=[UF.getsize(i)-len(ABNL[i])-1 for i in range(N+1)]
for i in range(1, N+1):
  for j in range(len(CDNL[i])):
    if UF.united(i, CDNL[i][j]):
      ans[i]-=1
      
print(*ans[1:])

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

    
    def find(self, x):
        if self.par[x] < 0:
            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 not x==y: 
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x] 
                self.par[x] = y 
            else:
                self.par[x] += self.par[y]
                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) 

import sys
input = sys.stdin.readline
from collections import defaultdict

N,M,K = map(int,input().split())
Fr = [0]*N
FrKi = UnionFind(N)
Bl = defaultdict(list)

for i in range(M):
    A,B = map(int,input().split())
    A -=1
    B-=1
    Fr[A]+=1
    Fr[B]+=1
    FrKi.union(A,B)
    
for i in range(K):
    A,B = map(int,input().split())
    A-=1
    B-=1
    Bl[A].append(B)
    Bl[B].append(A)
    
Ans = [0]*N


for i in range(N):
    tmp = -FrKi.par[FrKi.find(i)] - Fr[i] -1
    for j in Bl[i]:
        if FrKi.same_check(i,j):
            tmp -= 1
    Ans[i] = tmp
print(*Ans)

Solution (Python):
class UnionFind:
    
    
    def __init__(self, n):
        
        
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    
    """ノードxのrootノードを見つける"""
    def Find_Root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x]) 
            return self.root[x]
    
    """木の合併"""
    def Union(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        
        if (x==y):
            return 
        
        
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y] += 1
    
    """xとyが同じグループに所属するか"""
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    
    """ノードxが属する木のサイズ"""
    def Count(self, x):
        return -self.root[self.Find_Root(x)]     
    
    """木(非連結成分)の数を数える"""
    
    def Count_Unconnected_Component(self):
        cnt = 0
        for i in range(self.n):
            if self.root[i+1] < 0:
                cnt += 1
        return cnt
    
    def Members(self, x):
        r = self.Find_Root(x)
        return [i for i in range(self.n+1) if self.Find_Root(i) == r]
    
    """xが属する集合の個数"""
    def Size(self, x):
        return -self.root[self.Find_Root(x)]

n,m,k = map(int,input().split())
uf = UnionFind(n)
num = [0]*(n+1)
for _ in range(m):
    a,b = map(int,input().split())
    num[a] += 1
    num[b] += 1
    uf.Union(a,b)
block_edge = [[] for _ in range(n+1)]
for _ in range(k):
    c,d = map(int,input().split())
    block_edge[c].append(d)
    block_edge[d].append(c)
for i in range(1, n+1):
    res = uf.Size(i) - num[i] - 1
    for e in block_edge[i]:
        if uf.isSameGroup(i,e):
            res -= 1
    print(res, end=' ')

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 unite(x,y):
    x = find(x)
    y = find(y)
    if x==y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

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

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

edge = [[] for i in range(n)]

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

for i in range(n):
    cnt = size(i) - num[i] - 1
    for e in edge[i]:
        if same(e, i):
            cnt -= 1
    print(cnt, end=' ')

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n,m,k = mi()

nakama = [0] * n
d = UnionFind(n)
for i in range(m):
    a,b = mi()
    a -= 1
    b -= 1
    d.union(a,b)
    nakama[a] += 1
    nakama[b] += 1
teki =[[] for _ in range(n)]
for i in range(k):
    a,b = mi()
    a -= 1
    b -= 1
    teki[a].append(b)
    teki[b].append(a)
ans = [0] * n
for i in range(n):
    ans[i] = d.size(i) -1 -nakama[i]
    for j in teki[i]:
        if d.same(i,j):
            ans[i] -= 1
print(*ans)

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

follow = [[] for _ in range(N)]
labels = [-1 for _ in range(N)]
edges = [0 for _ in range(N)]

for i in range(M):
    A,B = map(int,input().split())
    A = A-1
    B = B-1
    follow[A].append(B)
    follow[B].append(A)
    edges[A] = edges[A] + 1
    edges[B] = edges[B] + 1

c = 0
for i in range(N):
    if (labels[i] == -1):
        s = []
        s.append(i)
        labels[i] = c
        while(len(s) != 0):
            u = s.pop()
            for i in range(len(follow[u])):
                if (labels[follow[u][i]] == -1):
                    labels[follow[u][i]] = c
                    s.append(follow[u][i])
        c += 1

groupV = [0]*(c+1)
for i in range(N):
    groupV[labels[i]] = groupV[labels[i]] + 1

for i in range(K):
    C,D = map(int,input().split())
    C = C-1
    D = D-1
    if (labels[C] != labels[D]) : continue
    edges[C] = edges[C] + 1
    edges[D] = edges[D] + 1

ans = ["0"]*N

for i in range(N):
    ans[i] = str(groupV[labels[i]] - 1 - edges[i])

print(" ".join(ans))

Solution (Python):



from math import *
from copy import *
from string import *                
from random import *                
from sys import stdin
from sys import maxsize
from operator import *                
from itertools import *
from collections import Counter        
from collections import defaultdict 

'''
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
'''

class DSU:

	def __init__(self,n):
		self.n = n
		self.par = list(range(self.n))
		self.size = [1 for i in range(self.n)]

	def find(self,i):
		while(i != self.par[i]):
			self.par[i] = self.par[self.par[i]]
			i = self.par[i]
		return i

	def unite(self,a,b):
		par_a = self.find(a)
		par_b = self.find(b)
		if(par_a == par_b):
			return False
		else:
			if(par_a <= par_b):
				self.par[par_b] = par_a
				self.size[par_a] += self.size[par_b]
				self.size[par_b] = 0
			else:
				self.par[par_a] = par_b
				self.size[par_b] += self.size[par_a]
				self.size[par_a] = 0
			return True

	def same(self,a,b):
		return self.par[a] == self.par[b]

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

N,M,K = map(int, stdin.readline().rstrip().split())
dsu = DSU(N)
directFriends = [0]*N
for i in range(M):
	a,b = map(int, stdin.readline().rstrip().split())
	a -= 1
	b -= 1
	dsu.unite(a,b)
	directFriends[a] += 1
	directFriends[b] += 1

enemiesInSameComponent = [0]*N
for i in range(K):
	a,b = map(int, stdin.readline().rstrip().split())
	a -= 1
	b -= 1
	if(dsu.find(a) == dsu.find(b)):
		enemiesInSameComponent[a] += 1
		enemiesInSameComponent[b] += 1


candidates = [0]*N
for i in range(N):
	tot = dsu.size[dsu.find(i)]
	candidates[i] = tot - directFriends[i] - enemiesInSameComponent[i] - 1







print(*candidates)

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

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

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.size(x) < self.size(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)]
    
uf = UnionFind(n)
for a, b in ab: uf.unite(a, b)
ans = [uf.size(i)-1 for i in range(n)]

for a, b in ab:
    if uf.same(a, b): ans[a] -= 1; ans[b] -= 1
for c, d in cd:
    if uf.same(c, d): ans[c] -= 1; ans[d] -= 1

print(*ans)

Solution (Python):
import unittest
import collections


class TestD(unittest.TestCase):
    def test_1(self):
        self.assertEqual(
            think(
                4,
                [
                    [2, 1],
                    [1, 3],
                    [3, 2],
                    [3, 4],
                ],
                [
                    [4, 1]
                ]
            ),
            [0, 1, 0, 1]
        )

    def test_2(self):
        self.assertEqual(
            think(
                5,
                [
                    [1, 2],
                    [1, 3],
                    [1, 4],
                    [1, 5],
                    [3, 2],
                    [2, 4],
                    [2, 5],
                    [4, 3],
                    [5, 3],
                    [4, 5],
                ],
                [
                ]
            ),
            [0, 0, 0, 0, 0]
        )

    def test_3(self):
        self.assertEqual(
            think(
                10,
                [
                    [10, 1],
                    [6, 7],
                    [8, 2],
                    [2, 5],
                    [8, 4],
                    [7, 3],
                    [10, 9],
                    [6, 4],
                    [5, 8],
                ],
                [
                    [2, 6],
                    [7, 5],
                    [3, 1],
                ]
            ),
            [1, 3, 5, 4, 3, 3, 3, 3, 1, 0]
        )


def solve():
    n, list_of_a_and_b, list_of_c_and_d = read()
    result = think(n, list_of_a_and_b, list_of_c_and_d)
    write(result)


def read():
    n, m, k = read_int(3)
    list_of_a_and_b = []
    for _ in range(m):
        a, b = read_int(2)
        list_of_a_and_b.append([a, b])
    list_of_c_and_d = []
    for _ in range(k):
        c, d = read_int(2)
        list_of_c_and_d.append([c, d])
    return n, list_of_a_and_b, list_of_c_and_d


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(n, list_of_a_and_b, list_of_c_and_d):
    adjacency_list_of_friend = make_adjacency_list_from(n, list_of_a_and_b)
    adjacency_list_of_block = make_adjacency_list_from(n, list_of_c_and_d)
    list_of_connected_graph = collect_connected_graph_from(n, adjacency_list_of_friend)
    candidate_of_friends = [0] * n
    for connected_graph in list_of_connected_graph:
        for vertex in connected_graph:
            index = vertex - 1
            candidate_of_friends[index] = len(connected_graph)
            candidate_of_friends[index] -= len(adjacency_list_of_friend[vertex])
            for blocked in adjacency_list_of_block[vertex]:
                if blocked in connected_graph:
                    candidate_of_friends[index] -= 1
            candidate_of_friends[index] -= 1
    return candidate_of_friends


def write(result):
    print(' '.join(map(str, result)))


def make_adjacency_list_from(n, list_of_pair):
    adjacency_list = {}
    for i in range(1, n + 1):
        adjacency_list[i] = []
    for left, right in list_of_pair:
        adjacency_list[left].append(right)
        adjacency_list[right].append(left)
    return adjacency_list


def collect_connected_graph_from(n, adjacency_list):
    visited = [False for _ in range(n + 1)]
    list_of_connected_graph = []
    for vertex in range(1, len(visited)):
        if visited[vertex]:
            continue
        connected_graph = set([vertex])
        queue = collections.deque([vertex])
        while queue:
            data = queue.popleft()
            if visited[data]:
                continue
            visited[data] = True
            connected_graph.add(data)
            for next_data in adjacency_list[data]:
                queue.append(next_data)
        list_of_connected_graph.append(connected_graph)
    return list_of_connected_graph


if __name__ == '__main__':
    
    solve()

Solution (Python):
n,m,k=[int(j) for j in input().split()]
par=[-1 for i in range(n)]    

def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True


f=set(tuple(int(j)-1 for j in input().split()) for _ in range(m))
b=set(tuple(int(j)-1 for j in input().split()) for _ in range(k))

for a in f:
    if root(a[0])!=root(a[1]):
        connect(a[0],a[1])

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

for i,j in f:
    if root(i)==root(j):
        ans[i]-=1
        ans[j]-=1
for i,j in b:
    if root(i)==root(j):
        ans[i]-=1
        ans[j]-=1

print(*ans)

Solution (Python):
from collections import Counter

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


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

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

    def unite(self, x, y):
        root_x = self.root(x)
        root_y = self.root(y)
        if self.rank[x] > self.rank[y]:
            self.parent[root_y] = root_x
        elif self.rank[x] < self.rank[y]:
            self.parent[root_x] = root_y
        elif root_x != root_y:
            self.parent[root_y] = root_x
            self.rank[x] += 1
        pass


uf = UnionFind(N)

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

roots = [uf.root(i) for i in range(N)]
counter_roots = Counter(roots)

ans = [counter_roots[roots[i]] - 1 for i in range(N)]

for a, b in AB:
    if roots[a - 1] == roots[b - 1]:
        ans[a - 1] -= 1
        ans[b - 1] -= 1
for a, b in CD:
    if roots[a - 1] == roots[b - 1]:
        ans[a - 1] -= 1
        ans[b - 1] -= 1

print(*ans)

Solution (Python):







class UnionFind():

    def __init__(self, n=0):
        self.d = [-1 for _ in range(N)] 
    
    def find(self, x): 
        if self.d[x]<0:
            return x
        res = self.find(self.d[x])
        self.d[x] = res 
        return res
    
    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 -self.d[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)
deg = [0 for _ in range(N)] 
to = [[] for _ in range(N)] 


for i in range(M):
    a, b = AB[i]
    a-=1
    b-=1
    deg[a]+=1
    deg[b]+=1
    uf.unite(a, b)

for i in range(K):
    c, d = CD[i]
    c-=1
    d-=1
    to[c].append(d)
    to[d].append(c)

ans=[0 for _ in range(N)]
for i in range(N):
    
    ans[i]=uf.size(i)-1-deg[i]
    
    for u in to[i]:
        if uf.same(i, u):
            ans[i]-=1
print(*ans)

Solution (Python):

import sys
input = sys.stdin.readline

n,m,k = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(m)]
cd = [list(map(int,input().split())) for i in range(k)]

from bisect import bisect_left



class UniFindTree():
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size_of_group = [0] * n
    def find_root(self,i):
        if self.par[i]==i:
            
            return i
        else:
            self.par[i] = self.find_root(self.par[i])
            return self.par[i]

    def unite(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x==y:
            return
        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(self,x,y):
        return self.find_root(x)==self.find_root(y)
    def set_size_of_group(self):
        for i in self.par:
            self.size_of_group[i]+=1
    def shukuyaku(self):
        for i in range(len(self.par)):
            self.find_root(i)
uni = UniFindTree(n+1)
for a,b in ab:
    uni.unite(a,b)
uni.shukuyaku()
uni.set_size_of_group()
ret = [uni.size_of_group[i]-1 for i in uni.par]
for a,b in ab:
    if uni.same(a,b):
        ret[a]-=1
        ret[b]-=1

for c,d in cd:
    if uni.same(c,d):
        ret[c]-=1
        ret[d]-=1

print(" ".join(map(str,ret[1::])))

Solution (Python):
N,M,K=map(int,input().split())
fdic={}
for i in range(1,N+1):
  fdic[i]=set()  
for i in range(M):
  a,b=map(int,input().split())
  fdic[a].add(b)
  fdic[b].add(a)

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



dic_cluster={}
cluster_num=0
cluster_list=[0]*(N+1)

for i in range(1,N+1):
  if cluster_list[i]>0:
    continue
  else:
    cluster_num+=1
    dic_cluster[cluster_num]=set()
    visited=set()
    queue=[i]
    while(len(queue)>0):
      new_queue=set()
      for q in queue:
        cluster_list[q]=cluster_num
        dic_cluster[cluster_num].add(q)
        visited.add(q)
        nx=fdic[q]
        for n in nx:
          if not n in visited:
            new_queue.add(n)

      queue=new_queue
      
      



candlist=[0]*(N+1)
for i in range(1,N+1):
  candlist[i]=len(dic_cluster[cluster_list[i]])-len(fdic[i])-1
for c,d in blist:
  if d in dic_cluster[cluster_list[c]]:
    candlist[c]-=1
    candlist[d]-=1
  
print(" ".join(map(str,candlist[1:])))

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    def find(i):
        x = S[i]
        if x < 0:
            return i
        S[i] = find(x)
        return S[i]

    def join(i, j):
        ai = find(i)
        aj = find(j)
        diff = ai - aj
        if diff == 0:
            return
        elif diff > 0:
            ai, aj = aj, ai
        S[ai] += S[aj]
        S[aj] = ai
    def same(i, j):
        ai = find(i)
        aj = find(j)
        return ai == aj
    def size(i):
        return -S[find(i)]

    N, M, K = iim()
    S = [-1] * N
    T = [1] * N
    for i in range(M):
        ai, bi = iim()
        ai -= 1; bi -= 1
        join(ai, bi)
        T[ai] += 1
        T[bi] += 1
        

    for i in range(K):
        ai, bi = iim()
        ai -= 1; bi -= 1
        if same(ai, bi):
            T[ai] += 1
            T[bi] += 1
    
    

    ans = [size(i) - T[i] for i in range(N)]
    print(*ans)


if __name__ == "__main__":
    resolve()

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

from bisect import bisect

def resolve():
    def find(i):
        x = S[i]
        if x < 0:
            return i
        S[i] = find(x)
        return S[i]

    def join(i, j):
        ai = find(i)
        aj = find(j)
        diff = ai - aj
        if diff == 0:
            return
        elif diff > 0:
            ai, aj = aj, ai
        S[ai] += S[aj]
        S[aj] = ai
    def same(i, j):
        ai = find(i)
        aj = find(j)
        return ai == aj
    def size(i):
        return -S[find(i)]

    N, M, K = iim()
    S = [-1] * N
    T = [1] * N
    for i in range(M):
        ai, bi = iim()
        ai -= 1; bi -= 1
        join(ai, bi)
        T[ai] += 1
        T[bi] += 1
        

    for i in range(K):
        ai, bi = iim()
        ai -= 1; bi -= 1
        if same(ai, bi):
            T[ai] += 1
            T[bi] += 1
    
    

    ans = [size(i) - T[i] for i in range(N)]
    print(*ans)


if __name__ == "__main__":
    resolve()