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):
from collections import defaultdict


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):
        d = {}
        for i in range(self.n):
            p = self.find(i)
            if p in d:
                d[p].append(i)
            else:
                d[p] = [i]
        return d

    def __str__(self):
        return '\n'.join('{}: {}'.format(k, v) for k, v in self.all_group_members().items())


def resolve():
    n, m, k = map(int, input().split())
    u = UnionFind(n)
    d = defaultdict(int)
    e = defaultdict(int)
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        u.union(a, b)
        d[a] += 1
        d[b] += 1
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        if u.same(a, b):
            e[a] += 1
            e[b] += 1
    ans = [0] * n
    for i, v in u.all_group_members().items():
        x = len(v) - 1
        for j in v:
            ans[j] = x-d[j] - e[j]
    print(*ans)


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import defaultdict


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):
        d = {}
        for i in range(self.n):
            p = self.find(i)
            if p in d:
                d[p].append(i)
            else:
                d[p] = [i]
        return d

    def __str__(self):
        return '\n'.join('{}: {}'.format(k, v) for k, v in self.all_group_members().items())


def resolve():
    n, m, k = map(int, input().split())
    u = UnionFind(n)
    d = defaultdict(int)
    e = defaultdict(int)
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        u.union(a, b)
        d[a] += 1
        d[b] += 1
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        if u.same(a, b):
            e[a] += 1
            e[b] += 1
    ans = [0] * n
    for i, v in u.all_group_members().items():
        x = len(v) - 1
        for j in v:
            ans[j] = x-d[j] - e[j]
    print(*ans)


if __name__ == '__main__':
    resolve()

Solution (Python):

from sys import setrecursionlimit 
setrecursionlimit(10**6)

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

fr = [set() for _ in range(n)]
bl = [set() for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    fr[a-1].add(b-1)
    fr[b-1].add(a-1)
    
for i in range(k):
    c ,d = map(int, input().split())
    bl[c-1].add(d-1)
    bl[d-1].add(c-1)
    

def connectedcomponents():
    visited = []
    cc = [0]*n
    for i in range(n):
        visited.append(False)
    for v in range(n):
        if visited[v] == False:
            temp = set()
            for i in dfs(fr,v,temp,visited):
                cc[i] = dfs(fr,v,temp,visited)
    return cc
            

def dfs(fr, v, temp, visited):
    visited[v] = True
    temp.add(v)
    for i in fr[v]:
        if visited[i] == False:
            temp = dfs(fr, i, temp, visited)
    return temp

cc = connectedcomponents()

ans = []
for i in range(n):
    aa = len(cc[i]) - len(cc[i] & fr[i]) - len(cc[i] & bl[i]) - 1
    ans.append(aa)
print(*ans)

Solution (Python):
class UnionFindTree:
    def __init__(self, N):
        self.root = [i for i in range(N + 1)]
        self.friendcount = [1] * (N + 1)

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

    def unite(self, x, y):
        xroot = self.getroot(x)
        yroot = self.getroot(y)
        if xroot == yroot:
            return
        if xroot > yroot:
            self.root[xroot] = yroot
            self.friendcount[yroot] += self.friendcount[xroot]
        else:
            self.root[yroot] = xroot
            self.friendcount[xroot] += self.friendcount[yroot]

    def getfriendcount(self, x):
        xroot = self.getroot(x)
        return self.friendcount[xroot]

    def same(self, x, y):
        if self.getroot(x) == self.getroot(y):
            return True
        return False


N, M, K = map(int, input().split())
A = [0] * M
B = [0] * M
C = [0] * K
D = [0] * K

for i in range(M):
    A[i], B[i] = map(int, input().split())
for i in range(K):
    C[i], D[i] = map(int, input().split())

tree = UnionFindTree(N + 1)
for i in range(M):
    tree.unite(A[i], B[i])

friendscount = [0] * (N + 1)
blockcount = [0] * (N + 1)
for i in range(M):
    friendscount[A[i]] += 1
    friendscount[B[i]] += 1
for i in range(K):
    if tree.same(C[i], D[i]):
        blockcount[C[i]] += 1
        blockcount[D[i]] += 1

result = [str(tree.getfriendcount(i) - 1 - friendscount[i] - blockcount[i]) for i in range(1, N + 1)]
print(" ".join(result))

Solution (Python):
class UnionFindTree:
    def __init__(self, N):
        self.root = [i for i in range(N)]
        self.friendcount = [1] * N

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

    def unite(self, x, y):
        xroot = self.getroot(x)
        yroot = self.getroot(y)
        if xroot == yroot:
            return
        if xroot > yroot:
            self.root[xroot] = yroot
            self.friendcount[yroot] += self.friendcount[xroot]
        else:
            self.root[yroot] = xroot
            self.friendcount[xroot] += self.friendcount[yroot]

    def getfriendcount(self, x):
        xroot = self.getroot(x)
        return self.friendcount[xroot]

    def same(self, x, y):
        if self.getroot(x) == self.getroot(y):
            return True
        return False


N, M, K = map(int, input().split())
A = [0] * M
B = [0] * M
C = [0] * K
D = [0] * K

for i in range(M):
    A[i], B[i] = map(int, input().split())
for i in range(K):
    C[i], D[i] = map(int, input().split())

tree = UnionFindTree(N + 1)
for i in range(M):
    tree.unite(A[i], B[i])

friendscount = [0] * (N + 1)
blockcount = [0] * (N + 1)
for i in range(M):
    friendscount[A[i]] += 1
    friendscount[B[i]] += 1
for i in range(K):
    if tree.same(C[i], D[i]):
        blockcount[C[i]] += 1
        blockcount[D[i]] += 1

result = [str(tree.getfriendcount(i) - 1 - friendscount[i] - blockcount[i]) for i in range(1, N + 1)]
print(" ".join(result))

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

n, m, k = map(int, input().split())
friend = UnionFind(n + 1)

a, b = [], []
num = [0] * (n + 1)
for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
    num[aa] += 1
    num[bb] += 1
    friend.union(aa, bb)

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

ans = [0] * (n + 1)
for i in range(1, n + 1):
    ans[i] = friend.size(i)
    ans[i] -= num[i]
    ans[i] -= 1

for i in range(k):
    if friend.same(c[i], d[i]):
        ans[c[i]] -= 1
        ans[d[i]] -= 1

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

Solution (Python):


class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    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 Unite(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
    

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


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

uf = UnionFind(N+1)

friends = [0]*(N+1)
for A, B in AB:
    friends[A] += 1
    friends[B] += 1
    uf.Unite(A, B)

ans = [0]*(N+1)
for i in range(1, N+1):
    ans[i] = uf.Count(i)-1-friends[i]

for C, D in CD:
    if uf.isSameGroup(C, D):
        ans[C] -= 1
        ans[D] -= 1

print(*ans[1:])

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 0
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] = self.par[y] + self.par[x]
        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())
U = UnionFind(n)
fl = [0] * n
bl = [0] * n

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

for _ in range(k):
    c, d = map(int, input().split())
    if U.same_check(c - 1, d - 1):
        bl[c - 1] += 1
        bl[d - 1] += 1

ans_list = []
for i in range(n):
    ans = -U.size(i) - fl[i] - bl[i] - 1
    ans_list.append(ans)
print(*ans_list)

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

int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')


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 solve():
    n, m, k = MI()
    uf = UnionFind(n)

    friends = [0] * n
    for i in range(m):
        a, b = MI1()
        uf.union(a, b)
        friends[a] += 1
        friends[b] += 1
    
    

    blocks = [0] * n
    for i in range(k):
        c, d = MI1()
        if uf.same(c, d):
            blocks[c] += 1
            blocks[d] += 1

    

    ans = [0] * n

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

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

if __name__ == '__main__':
    solve()

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

N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    
    if i != group_list[i]:
        continue
    next_stack = [i]
    friend = [i]
    while next_stack:
        u = next_stack.pop(-1)
        for v in friends_table[u]:
            
            if i == group_list[v]:
                continue
            friend += [v]
            group_list[v] = i
            next_stack += [v]
    for f in friend:
        friends_candidate[f] = friend

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    if group_list[a-1] == group_list[b-1]:
        blocks_table[a-1] += [b-1]
        blocks_table[b-1] += [a-1]

for i in range(N):
    print(len(friends_candidate[i]) - len(friends_table[i]) - len(blocks_table[i])-1)

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

int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')


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 solve():
    n, m, k = MI()
    uf = UnionFind(n)

    friends = [0] * n
    for i in range(m):
        a, b = MI1()
        uf.union(a, b)
        friends[a] += 1
        friends[b] += 1
    
    

    

    blocks = {}
    for i in range(k):
        c, d = MI1()
        
        
        blocks.setdefault(c, [])
        blocks[c].append(d)

        blocks.setdefault(d, [])
        blocks[d].append(c)

    

    ans = [0] * n

    for i in range(n):
        
        block = 0
        
        for bb in blocks.get(i, []):
            
            if uf.same(i, bb):
                
                block += 1
        ans[i] = uf.size(i) - 1 - block - friends[i]
        

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

if __name__ == '__main__':
    solve()

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

N, M, K = map(int, input().split())
friend = [deque() for _ in range(N)]
status = [-1]*N
numList = [0]*N
ans = [0]*N

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

def DFS(graph, v, num):
    cnt = 0
    stack = [v]
    status[v] = num
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if status[w] == -1:
                status[w] = num
                cnt += 1
                stack.append(w) 
        else:
            stack.pop() 
    numList[num] = cnt

cnt = 0
for i in range(N):
    if status[i] == -1:
        DFS(friend, i, cnt)
        cnt += 1

for i in range(N):
    ans[i] += numList[status[i]]

for i in range(K):
    a, b = map(int, input().split())
    if status[a-1] == status[b-1]:
        ans[a-1] -= 1
        ans[b-1] -= 1

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque 


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush



def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds


def tree_init(N):
    edgelist = [[] for _ in range(N)]
    for a, b in [map(int, input().split()) for i in range(N-1)]:
        edgelist[a-1].append(b-1)
        edgelist[b-1].append(a-1)
    return edgelist

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


def main():
    

    
    N,M,K = map(int, input().split())
    
    
    
    par=[i for i in range(N)]
    fl=[[] for _ in range(N)]
    counts=[0]*N
    for _ in range(M):
        a, b= map(int,input().split())
        counts[a-1]-=1
        counts[b-1]-=1
        fl[a-1].append(b-1)
        fl[b-1].append(a-1)

    visited=[False]*N
    roots=[0]*N
    pcount=[0]*N
    for i in range(N):
        if visited[i]:
            continue
        q=deque([i])
        while len(q):
            
            e=q.pop()
            if visited[e]:
                continue
            
            roots[e]=i
            pcount[i]+=1
            visited[e]=True
            for ne in fl[e]:
                if visited[ne]:
                    continue
                q.append(ne)
    

    for i in range(N):
        counts[i]+=pcount[roots[i]]-1

    for _ in range(K):
        a, b= map(int,input().split())
        if roots[a-1]==roots[b-1]:
            counts[a-1]-=1
            counts[b-1]-=1

    print(*counts)
    



if __name__ == "__main__":
    main()

Solution (Python):
import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=qb
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
def dq():
	return queue.deque()

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 -1*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()} 

n,m,k = readInts()

uf = UnionFind(n)
fc = [0]*(n+1) 

for i in range(m):
	a,b = readInts()
	uf.union(a-1,b-1)
	fc[a]+=1
	fc[b]+=1

br = [0]*(n+1)

for i in range(k):
	c,d = readInts()
	if uf.find(c-1)==uf.find(d-1):
		br[c]+=1
		br[d]+=1

for i in range(1,n+1):
	print(uf.size(i-1)-1-fc[i]-br[i],end=" ")
print()

Solution (Python):


from queue import Queue

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

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

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

Q = Queue()
visited = [False] * N
group = [0] * N
for i in range(N):
    if visited[i]:
        continue
    Q.put(friends[i])
    visited[i] = True
    while not Q.empty():
        q = Q.get()
        group[q[0]] = i
        for j in q[1]:
            if not visited[j]:
                visited[j] = True
                Q.put(friends[j])

cnt = {}
for num in group:
    if num in cnt:
        cnt[num] += 1
    else:
        cnt[num] = 1

ans = [0] * N
for i in range(N):
    ans[i] = cnt[group[i]] - len(friends[i][1]) - 1
    for block in blocks[i][1]:
        if group[i] == group[block]:
            ans[i] -= 1

print(*ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
n,m,k = [int(i) for i in readline().split()]
ab = [[int(i) for i in readline().split()] for _ in range(m)]
cd = [[int(i) for i in readline().split()] for _ in range(k)]

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

    def find(self, x):
        """
        根のIDを返す
        """
        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 -self.d[self.find(x)]

MAXN = 100005
deg = [0]*MAXN
to = [[] for _ in range(MAXN)]

uf = UnionFind(n)

for a,b in ab:
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.unite(a, b)

for c,d in cd:
    c -= 1
    d -= 1
    to[c].append(d)
    to[d].append(c)

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

Solution (Python):

import sys
from collections import Counter, defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M, K = lr()

def find(A, x):
    parent = A[x]
    if parent == x: return x
    root = find(A, parent)
    A[x] = root
    return root

def union(A, x, y):
    root, second = find(A, x), find(A, y)
    if root > second:
        second, root = root, second
    A[second] = root

V = list(range(N+1))
friend = [[] for _ in range(N+1)]  
for _ in range(M):
    a, b = lr()
    friend[a].append(b)
    friend[b].append(a)
    if find(V, a) != find(V, b):
        union(V, a, b)

V = [find(V, x) for x in V]
counter = Counter(V)
dic = defaultdict(int)
for k, v in counter.items():
    dic[k] = v

block = [[] for _ in range(N+1)]
for _ in range(K):
    c, d = lr()
    block[c].append(d)
    block[d].append(c)

answer = []
for i in range(1, N+1):
    root = V[i]
    x = dic[root] - 1
    x -= sum(1 for y in block[i] if V[y] == root)
    x -= sum(1 for y in friend[i] if V[y] == root)
    answer.append(x)

print(*answer)

Solution (Python):

import sys

sysread = sys.stdin.readline


sys.setrecursionlimit(10**7)


def run():
    N,M,K = map(int, sysread().split())
    to = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int, sysread().split())
        to[a].append(b)
        to[b].append(a)

    seen = [False] * (N+1)
    groups = [[]]
    belongs = [-1] * (N+1)
    def dfs(node, g = 0 ,parent=None):
        seen[node] = True
        groups[g].append(node)
        belongs[node] = g
        for next in to[node]:
            if not seen[next]:
                dfs(next, g=g, parent=node)

    g = 0
    for idx in range(1, N+1):
        if not seen[idx]:
            dfs(idx, g)
            g += 1
            groups.append([])

    block = [[] for _ in range(N+1)]
    for _ in range(K):
        c,d = map(int, sysread().split())
        if belongs[c] == belongs[d]:
            block[c].append(d)
            block[d].append(c)

    for i in range(1, N+1):
        tmp_g = belongs[i]
        print(len(groups[tmp_g]) - len(to[i]) - len(block[i]) - 1, end=' ')



if __name__ == "__main__":
    run()

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)
import sys
input = sys.stdin.readline
N,M,K = map(int,input().split())
uf = UnionFind(N)
lst=[0]*(N)
for i in range(M):
 A,B=map(int,input().split())
 uf.union(A-1,B-1)
 lst[A-1]-=1
 lst[B-1]-=1
for i in range(K):
 A,B=map(int,input().split())
 if uf.same(A-1,B-1):
  lst[A-1]-=1
  lst[B-1]-=1
lst=[lst[i]+uf.size(i)-1 for i in range(N)]
L=[str(a) for a in lst]
L=' '.join(L)
print(L)

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)

N,M,K = map(int,input().split())
uf = UnionFind(N)
lst=[0]*(N)
for i in range(M):
 A,B=map(int,input().split())
 uf.union(A-1,B-1)
 lst[A-1]-=1
 lst[B-1]-=1
for i in range(K):
 A,B=map(int,input().split())
 if uf.same(A-1,B-1):
  lst[A-1]-=1
  lst[B-1]-=1
lst=[lst[i]+uf.size(i)-1 for i in range(N)]
L=[str(a) for a in lst]
L=' '.join(L)
print(L)