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 deque

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

fri = [[] for _ in range(n+1)]
blo = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    fri[a].append(b)
    fri[b].append(a)

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


gru = [-1] * (n+1)
gru[0] = 0
visited = [False]*(n+1)
D = {}

for root in range(1,n+1):
    if visited[root]:
        continue
    
    D[root]= set([root])
    d = deque()
    d.append(root)
    while d:
        v = d.popleft()
        visited[v] = True
        gru[v] = root
        for to in fri[v]:
            if visited[to]:
                continue
            D[root].add(to)
            d.append(to)


nans = [0]*n
for i in range(1,n+1):
    g = D[gru[i]]
    ans = len(g)-len(fri[i])-1
    for b in blo[i]:
        if b in g:
            ans -= 1
    nans[i-1] = ans

print(*nans, sep='\n')

Solution (Python):
class UnionFind:

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


    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return True


    def root(self, x):
        path = []
        while self.par[x] >= 0:
            path.append(x)
            x = self.par[x]
        for y in path:
            self.par[y] = x
        return x


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


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


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

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

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

uni = UnionFind(n)
for i, v in enumerate(friends):
    for j in v:
        uni.unite(i, j)

for i in range(n):
    ans = uni.size(i) - len(friends[i]) - 1
    for block in blocks[i]:
        if uni.same(i, block):
            ans -= 1
    print(ans, 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())

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

Solution (Python):
from collections import Counter

def main():
    n, m, k = list(map(int, input().split()))
    friendships = [tuple(map(int, input().split())) for _ in range(m)]
    blockships = [tuple(map(int, input().split())) for _ in range(k)]

    components = list(range(n))
    friends = { }

    for u, v in friendships:
        u -= 1
        v -= 1
        if u not in friends:
            friends[u] = []
        if v not in friends:
            friends[v] = []
        friends[u].append(v)
        friends[v].append(u)

    blocks = { }
    for u, v in blockships:
        u -= 1
        v -= 1
        if u not in blocks:
            blocks[u] = []
        if v not in blocks:
            blocks[v] = []
        blocks[u].append(v)
        blocks[v].append(u)

    
    cur_comp = 0
    visited = set()

    def bfs(node):
        st = [node]
        comp = node
        while st:
            n = st.pop()
            if n in visited:
                continue
            components[n] = comp
            visited.add(n)
            if n in friends:
                for nbor in friends[n]:
                    st.append(nbor)


    for u in range(n):
        bfs(u)

    hist = Counter(components)
    new_friends = [0] * n

    
    
    
    for u in range(n):
        comp = components[u]
        comp_size = hist[comp]
        n_blocked = blocks[u] if u in blocks else set()
        n_friends = friends[u] if u in friends else set()
        n_same_comp = list(filter(lambda v: components[v] == comp, n_blocked))
        
        new_friends[u] = comp_size - 1 - len(n_same_comp) - len(n_friends)

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


main()

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


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())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]

uf = Unionfind(n)
frnd = [0] * n
for a, b in ab:
    uf.union(a - 1, b - 1)
    frnd[a - 1] += 1
    frnd[b - 1] += 1

brck = [0] * n
for c, d in cd:
    if uf.same(c - 1, d - 1):
        brck[c - 1] += 1
        brck[d - 1] += 1

ans = []
for i in range(n):
    ans.append(uf.size(i) - frnd[i] - brck[i] - 1)
print(*ans)

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):
class UnionFind:
    """
    size の要素数の UnionFind を管理する
    data 中の負数の要素が根となる
    """

    def __init__(self, size):
        
        self.data = [-1] * size

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y: return False

        
        if self.data[x] < self.data[y]:
            x, y = y, x

        
        self.data[y] += self.data[x]
        self.data[x] = y
        return True

    def root(self, x):
        if self.data[x] < 0:
            return x
        self.data[x] = self.root(self.data[x])
        return self.data[x]

    def size(self, x):
        """
        根は負数でデータ数を管理しているのでそれを返す
        """
        return -self.data[self.root(x)]


N, M, K = [int(_) for _ in input().split()]
NG = [0] * (N + 1)
uf = UnionFind(N + 1)
for i in range(M):
    a, b = [int(_) for _ in input().split()]
    uf.merge(a, b)
    NG[a] += 1
    NG[b] += 1


for i in range(K):
    a, b = [int(_) for _ in input().split()]
    if uf.root(a) == uf.root(b):
        NG[a] += 1
        NG[b] += 1

res = [0] * (N)
for i in range(1, N + 1):
    cnt = uf.size(i) - NG[i] - 1
    res[i-1]=cnt
print(*res)

Solution (Python):
class UnionFind:
    """
    size の要素数の UnionFind を管理する
    data 中の負数の要素が根となる
    """

    def __init__(self, size):
        
        self.data = [-1] * size

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y: return False

        
        if self.data[x] < self.data[y]:
            x, y = y, x

        
        self.data[y] += self.data[x]
        self.data[x] = y
        return True

    def root(self, x):
        if self.data[x] < 0:
            return x
        self.data[x] = self.root(self.data[x])
        return self.data[x]

    def size(self, x):
        """
        根は負数でデータ数を管理しているのでそれを返す
        """
        return -self.data[self.root(x)]


N, M, K = [int(_) for _ in input().split()]
MG = [0] * (N + 1)
uf = UnionFind(N + 1)
for i in range(M):
    a, b = [int(_) for _ in input().split()]
    uf.merge(a, b)
    MG[a] += 1
    MG[b] += 1

KG = [[] for _ in range(N + 1)]
for i in range(K):
    a, b = [int(_) for _ in input().split()]
    KG[a].append(b)
    KG[b].append(a)

res = [0]*(N)
for i in range(1,N+1):
    cnt = uf.size(i) - MG[i]-1
    for k in KG[i]:
        if uf.root(i)==uf.root(k):
            cnt-=1
    res[i-1] =cnt
print(*res)

Solution (Python):



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


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



par = [-1]*N

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

ans = [size(v) - len(G[v]) - 1 for v in range(N)]

H = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    if same(c-1, d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1
    
print(' '.join(map(str, ans)))

Solution (Python):

import collections,sys
sys.setrecursionlimit(10**9)
n,m,k = map(int, input().split())

friend = [[]*(n+1) for _ in range(n+1)]
block = [[]*(n+1) for _ in range(n+1)]
teams = [0]*(n+1)
for _ in range(m):
  a,b = map(int, input().split())
  friend[a].append(b)
  friend[b].append(a)
for _ in range(k):
  c,d = map(int, input().split())
  block[c].append(d)
  block[d].append(c)
  
def dfs(i):
  teams[i] = team
  for j in friend[i]:
    if teams[j] != 0:
      continue
    dfs(j)

team=1
for i in range(1,n+1):
  if teams[i] != 0:
    continue
  dfs(i)
  team+=1

c = collections.Counter(teams)

for i in range(1,n+1):
  temp = c[teams[i]]-len(friend[i])-1
  for j in block[i]:
    if teams[j] == teams[i]:
      temp -= 1
  print(temp, end='')
  if i != n:
    print(" ", end='')

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

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    p = find(x)
    q = find(y)
    if p == q:
        return None
    if p > q:
        p,q = q,p
    par[p] += par[q]
    par[q] = p
def same(x, y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
par = [-1 for i in range(n)]
l = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    unite(a-1, b-1)
    l[a-1] += 1
    l[b-1] += 1
for i in range(k):
    c, d = map(int, input().split())
    if same(c-1, d-1):
        l[c-1] += 1
        l[d-1] += 1
for i in range(n):
    print(size(i) - l[i] - 1, end=" ")

Solution (Python):


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

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

    def union(self, x, y):
        x = self.root(x)
        y = self.root(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 same(self, x, y):
        return self.root(x) == self.root(y)

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

N,M,K = map(int,input().split())
friend = UnionFind(N+1)
block = [1]*(N+1)
for _ in range(M):
    x,y = map(int,input().split())
    block[x] += 1
    block[y] += 1
    friend.union(x,y)
for _ in range(K):
    x,y = map(int,input().split())
    if friend.same(x,y):
        block[x] += 1
        block[y] += 1
ans = [friend.size(i)-block[i] for i in range(1,N+1)]
print(*ans)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


def main():
    N, M, K = map(int, readline().split())
    AB = [tuple(int(s) - 1 for s in readline().split()) for _ in range(M)]
    CD = [tuple(int(s) - 1 for s in readline().split()) for _ in range(K)]

    G = [[] for _ in range(N)]
    for a, b in AB:
        G[a].append(b)
        G[b].append(a)

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

    uf = UnionFind(N)
    for a, b in AB:
        uf.union(a, b)

    ans = [0] * N
    for i in range(N):
        ans[i] = uf.size(i) - len(G[i]) - 1
        for j in H[i]:
            if uf.same(i, j):
                ans[i] -= 1

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n,m,k = map(int, input().split())
f = [[] for _ in range(n)]
g = [[] for _ in range(n)]

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

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

d = {}
parent = [-1] * n
seen = [False] * n


for i in range(n):
    if seen[i]:
        continue
    stack = deque()
    
    d[i] = set([i])
    stack = [i]
    while stack:
        v = stack.pop()
        seen[v] = True
        
        parent[v] = i
        for nv in f[v]:
            if seen[nv]:
                continue
            
            d[i].add(nv)
            stack.append(nv)

ans = [0] * n
for i in range(n):
    
    group = d[parent[i]]
    
    sum = len(group) - len(f[i]) - len(set(g[i]) & group) - 1
    ans[i] = sum

print(*ans)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n,m,k = map(int, input().split())
f = [[] for _ in range(n)]
g = [[] for _ in range(n)]

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

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

d = {}
parent = [-1] * n
seen = [False] * n

for i in range(n):
    if seen[i]:
        continue
    stack = deque()
    d[i] = set([i])
    stack = [i]
    while stack:
        v = stack.pop()
        seen[v] = True
        parent[v] = i
        for nv in f[v]:
            if seen[nv]:
                continue
            d[i].add(nv)
            stack.append(nv)

ans = [0] * n
for i in range(n):
    group = d[parent[i]]
    tmp = len(group) - len(f[i]) - 1
    for j in g[i]:
        if j in group:
            tmp -= 1
    ans[i] = tmp

print(*ans)

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())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

uf = UnionFind(N)
friend = [0]*N
blocked = [0]*N

for a, b in AB:
    uf.union(a-1, b-1)
    friend[a-1] += 1
    friend[b-1] += 1

for c, d in CD:
    if uf.same(d-1, c-1):
        blocked[c-1] += 1
        blocked[d-1] += 1

ans = [uf.size(i)-friend[i]-blocked[i]-1 for i in range(N)]
print(' '.join(map(str, ans)))

Solution (Python):
import collections
class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0]*N
        self.count = 0
    def root(self, a):
        if self.parent[a]==a:
            return a
        else:
            self.parent[a]=self.root(self.parent[a])
            return self.parent[a]
    def size(x):
        return -par[root(x)]

    def is_same(self, a, b):
        return self.root(a)==self.root(b)
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return

        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1
def main():
    n,m,k=map(int, input().split())
    friend = [0]*n
    fr = UnionFind(n)
    blocklist = [0]*n
    for i in range(m):
        a,b = map(int, input().split())
        fr.unite(a-1,b-1)
        friend[a-1]+=1
        friend[b-1]+=1
    for i in range(k):
        c,d=map(int, input().split())
        if(fr.root(c-1)==fr.root(d-1)):
            blocklist[c-1]+=1
            blocklist[d-1]+=1
    
    res = []
    dd = collections.defaultdict(int)
    for i in range(n):
        dd[fr.root(i)]+=1
    for i in range(n):
        res.append(dd[fr.root(i)]- blocklist[i] - friend[i]-1)
    print(*res)

if __name__ == '__main__':
    main()

Solution (Python):
import collections
class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0]*N
        self.count = 0
    def root(self, a):
        if self.parent[a]==a:
            return a
        else:
            self.parent[a]=self.root(self.parent[a])
            return self.parent[a]
    def size(x):
        return -par[root(x)]

    def is_same(self, a, b):
        return self.root(a)==self.root(b)
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return

        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1
def main():
    n,m,k=map(int, input().split())
    friend = [0]*n
    fr = UnionFind(n)
    blocklist = [0]*n
    for i in range(m):
        a,b = map(int, input().split())
        fr.unite(a-1,b-1)
        friend[a-1]+=1
        friend[b-1]+=1
    for i in range(k):
        c,d=map(int, input().split())
        if(fr.root(c-1)==fr.root(d-1)):
            blocklist[c-1]+=1
            blocklist[d-1]+=1
    
    res = []
    dd = collections.defaultdict(int)
    for i in range(n):
        dd[fr.root(i)]+=1
    for i in range(n):
        res.append(dd[fr.root(i)]- blocklist[i] - friend[i]-1)
    print(*res)

if __name__ == '__main__':
    main()

Solution (Python):
N, M, K = map(int, input().split())
table = [-1]*N
def union(x, y):
    global table
    x, y = find(x), find(y)
    if x==y:
        return False
    else:
        if table[x]>table[y]:
            x, y = y, x
        table[x] += table[y]
        table[y] = x
        return True
def find(x):
    if table[x]<0:
        return x
    else:
        table[x] = find(table[x])
        return table[x]
def rank(x):
    return table[find(x)]
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
    union(a-1, b-1)

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

ans = [""]*N
for i in range(N):
    tmp = abs(rank(i)) - len(friend[i]) - 1
    cnt = 0
    for b in block[i]:
        if find(i)==find(b):
            cnt += 1
    ans[i] = str(tmp - cnt)
print(" ".join(ans))

Solution (Python):
N, M, K = map(int, input().split())
table = [-1]*N
def union(x, y):
    global table
    x, y = find(x), find(y)
    if x==y:
        return False
    else:
        if table[x]>table[y]:
            x, y = y, x
        table[x] += table[y]
        table[y] = x
        return True
def find(x):
    if table[x]<0:
        return x
    else:
        table[x] = find(table[x])
        return table[x]
def rank(x):
    return table[find(x)]
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
    union(a-1, b-1)

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

ans = [""]*N
for i in range(N):
    tmp = abs(rank(i)) - len(friend[i]) - 1
    cnt = 0
    for b in block[i]:
        if find(i)==find(b):
            cnt += 1
    ans[i] = str(tmp - cnt)
print(" ".join(ans))

Solution (Python):
from copy import deepcopy
N, M, K = map(int, input().split())

table = [-1]*N
def union(x, y):
    global table
    x, y = find(x), find(y)
    if x==y:
        return False
    else:
        if table[x]>table[y]:
            x, y = y, x
        table[x] += table[y]
        table[y] = x
        return True

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

def rank(x):
    return table[find(x)]

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

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

ans = [""]*N
for i in range(N):
    tmp = abs(rank(i)) - len(friend[i]) - 1
    cnt = 0
    for b in block[i]:
        if find(i)==find(b):
            cnt += 1
    ans[i] = str(tmp - cnt)
print(" ".join(ans))

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

from collections import deque
label=[-1]*n

i=0
for start in range(n):
    if label[start]!=-1:
        continue
    else:
        i+=1
        label[start]=i    
    f=deque([start])
    while f:
        v=f.popleft()        
        for e in edge[v]:
            if label[e]==-1:
                label[e]=i
                f.append(e)   

Renketsu=[0]*(n+1)

for i in label:
    Renketsu[i]+=1

Block=[0]*n
for _ in range(k):
    c,d=map(int,input().split())
    c,d=c-1,d-1
    if label[c]==label[d]:
        Block[c]+=1
        Block[d]+=1

ans=[]
for k in range(n):
    ans.append(Renketsu[label[k]]-1 - len(edge[k]) - Block[k])
print(*ans)

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

from collections import Counter


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

graph1 = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(x) - 1 for x in input().split()]
    graph1[a].append(b); graph1[b].append(a)

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

def dfs(now):
    X[now] = x
    for next in graph1[now]:
        if X[next]:
            continue
        dfs(next)

X = [0] * n
x = 1
for i in range(n):
    if X[i]:
        continue
    dfs(i)
    x += 1

cnt = Counter(X)

ans = []
for i in range(n):
    x = X[i]
    tmp = cnt[x] - 1
    tmp -= len(graph1[i])
    tmp -= sum(X[j] == x for j in graph2[i])
    ans.append(tmp)

print(*ans)

Solution (Python):
def main():
    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 other_members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root and i != x]

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

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

    import sys
    def input():
        return sys.stdin.readline().rstrip()
    n, m, k = list(map(int, input().split()))
    uf = UnionFind(n)
    counts = [0] * n
    for _ in range(m):
        a, b = list(map(lambda x: int(x) - 1, input().split()))
        uf.union(a, b)
        counts[a] += 1
        counts[b] += 1
    for _ in range(k):
        c, d = list(map(lambda x: int(x) - 1, input().split()))
        if uf.same(c, d):
            counts[c] += 1
            counts[d] += 1
    print(' '.join([str(uf.size(i) - counts[i] - 1) for i in range(n)]))

if __name__ == '__main__':
    main()

Solution (Python):


import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    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)]


    n, m, k = na()
    par = [-1] * n
    friend = [0] * n
    block = [list() for i in range(n)]
    for i in range(m):
        a, b = na()
        a -= 1; b -= 1
        unite(a, b)
        friend[a] += 1
        friend[b] += 1
    for i in range(k):
        c, d = na()
        c -= 1; d -= 1
        block[c].append(d)
        block[d].append(c)
    
    for i in range(n):
        ans = size(i) - friend[i] - 1
        for b in block[i]:
            if same(i, b):
                ans -= 1
        print(ans, end=" ")
if __name__ == "__main__":
    main()