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

Solution (Python):
class union_find():
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [1 for i in range(n + 1)]
        self.size = [1 for i in range(n + 1)]

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

        ret = self.find(self.par[c])
        self.par[c] = ret
        return ret

    def union(self, x, y):

        xr = self.find(x)
        yr = self.find(y)
        if xr == yr:
            return

        if self.rank[yr] > self.rank[xr]:
            self.par[xr] = yr
            self.size[xr] += self.size[yr]
            self.size[yr] = self.size[xr]
        else:
            self.par[yr] = xr
            self.size[yr] += self.size[xr]
            self.size[xr] = self.size[yr]
            if self.rank[xr] == self.rank[yr]:
                self.rank[xr] += 1

    def mass_size(self):
        return [i == v for i, v in enumerate(self.par)].count(True) - 1

    def show(self):
        print('parent', self.par[1:])
        print('rank', self.rank[1:])

def main():
    from collections import defaultdict

    dicf = defaultdict(lambda :[])
    dicb = defaultdict(lambda :[])

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

    uf = union_find(N)
    for i in range(M):
        a, b = map(int, input().split())
        dicf[a].append(b)
        dicf[b].append(a)
        if a > b:
            a, b = b, a
        uf.union(a, b)

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

    ans = []
    for i in range(1, N + 1):
        x = uf.size[uf.find(i)] - len(dicf[i]) - 1
        m = 0
        for b in dicb[i]:
            if uf.find(b) == uf.find(i):
                m += 1

        ans.append(x - m)


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




if __name__ == '__main__':
    main()

Solution (Python):
import sys

line = sys.stdin.readline().strip()
n,m,k = map(int, line.split())
roots = [-1]*n
linked = [0]*n
def find_root(x):
    if roots[x] < 0:
        return x
    else:
        roots[x] = find_root(roots[x])
        return roots[x]
def unite(x, y):
    x = find_root(x)
    y = find_root(y)
    if (x==y):
        return
    if roots[x] > roots[y]:
        c, d = y,x
        x,y = c,d
    roots[x] += roots[y]
    roots[y] = x

for i in range(m):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c, d = a-1,b-1
    linked[c] += 1 
    linked[d] += 1
    unite(c,d)

blacks = [[]for i in range(n)]
for i in range(k):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c,d = a-1, b-1
    blacks[c].append(d)
    blacks[d].append(c)
res = []
for i in range(n):
    r = -roots[find_root(i)] - 1 - linked[i]
    for one in blacks[i]:
        if find_root(one) == find_root(i):
            r -= 1
    res.append(r)
    
print (" ".join(map(str, res)))

Solution (Python):
from sys import setrecursionlimit

def find(parent, i):
   t = parent[i]
   if t < 0:
      return i
   t = find(parent, t)
   parent[i] = t
   return t

def unite(parent, i, j):
   i = find(parent, i)
   j = find(parent, j)
   if i == j:
      return
   parent[j] += parent[i]
   parent[i] = j

setrecursionlimit(10 ** 5)

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

parent = [-1] * n
friends = [[] for _ in range(n)]
for A, B in ab:
   unite(parent, A-1, B-1)
   friends[A-1].append(B-1)
   friends[B-1].append(A-1)

blocks = [[] for _ in range(n)]
for C, D in cd:
   blocks[C-1].append(D-1)
   blocks[D-1].append(C-1)

result = []
for i in range(n):
   p = find(parent, i)
   t = -parent[p] - 1
   t -= len(friends[i])
   for b in blocks[i]:
      if p == find(parent, b):
         t -= 1
   result.append(t)

print(*result)

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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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

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

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

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

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

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

def main():
  L = []
  n, m, k = map(int, input().split())
  uf = UnionFind(n+1)
  F = [[] for _ in range(n+1)]
  for _ in range(m):
    a, b = map(int, input().split())
    F[a].append(b)
    F[b].append(a)
    uf.unite(a, b)
  G = [set() for _ in range(n+1)]
  for _ in range(k):
    c, d = map(int, input().split())
    G[c].add(d)
    G[d].add(c)
  for i in range(1, n+1):
    temp = uf.size(i)
    temp -= len(F[i])
    for v in G[i]:
      if uf.same(i, v):
        temp -= 1
    L.append(temp-1)
  print(*L)
    
if __name__ == "__main__":
  main()

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

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def find(i):
    rireki = []
    while parent[i] != i:
        rireki.append(i)
        i = parent[i]
    for r in rireki:
        parent[r]=i
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    parent[j] = i



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    












kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    n, m, k = map(int,input().split())
    E = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(int,input().split())
        u-=1; v-=1
        E[u].append(v)
        E[v].append(u)
    block = [tuple(map(int,input().split())) for _ in range(k)]

    
    cnt = 0
    color = [None]*n
    def dfs(v)->bool:
        if color[v] is not None: return False
        stack = [v]
        while stack:
            v = stack.pop()
            color[v] = cnt
            for nv in E[v]:
                if color[nv] is not None: continue
                stack.append(nv)
        return True

    for v in range(n):
        cnt += dfs(v)

    C = Counter(color)
    res = [C[color[v]]-len(E[v])-1 for v in range(n)]
    
    for u, v in block:
        u-=1; v-=1
        if color[u]==color[v]:
            res[u]-=1
            res[v]-=1
    print(*res)
resolve()

Solution (Python):




class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*n
    def root(self, x):
        if self.par[x] != x:
            self.par[x] = self.root(self.par[x])
        return self.par[x]
    def unite(self, x, y):
        if self.root(x) == self.root(y):
            return
        if self.rank[x] > self.rank[y]:
            self.size[self.root(x)] += self.size[self.root(y)]
            self.par[self.root(y)] = self.root(x)
        else:
            self.size[self.root(y)] += self.size[self.root(x)]
            self.par[self.root(x)] = self.root(y)
        if self.rank[x] == self.rank[y]:
            self.rank[y]+=1
    def check(self, x, y):
        return self.root(x) == self.root(y)
    def sizeCheck(self, x):
        return self.size[self.root(x)]
    def len(self):
        return len(self.par)

n,m,k = map(int,input().split())
uf = UnionFind(n)
ans = [0]*n
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    ans[a]-=1
    ans[b]-=1
co = [0]*n
for i in range(n):
    ans[i] += uf.sizeCheck(i)-1
for i in  range(k):
    c,d = map(int,input().split())
    if uf.check(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n):
    if i == n-1:
        print(ans[i])
    else:
        print(ans[i],end=' ')

Solution (Python):




class UnionFind:
    def __init__(self, n):
        self.size = n
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*n
    def root(self, x):
        if self.par[x] != x:
            self.par[x] = self.root(self.par[x])
        return self.par[x]
    def unite(self, x, y):
        if self.root(x) == self.root(y):
            return
        if self.rank[x] > self.rank[y]:
            self.size[self.root(x)] += self.size[self.root(y)]
            self.par[self.root(y)] = self.root(x)
        else:
            self.size[self.root(y)] += self.size[self.root(x)]
            self.par[self.root(x)] = self.root(y)
        if self.rank[x] == self.rank[y]:
            self.rank[y]+=1
    def check(self, x, y):
        return self.root(x) == self.root(y)
    def sizeCheck(self, x):
        return self.size[self.root(x)]

n,m,k = map(int,input().split())
uf = UnionFind(n)
ans = [0]*n
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    ans[a]-=1
    ans[b]-=1
co = [0]*n
for i in range(n):
    ans[i] += uf.sizeCheck(i)-1
for i in  range(k):
    c,d = map(int,input().split())
    if uf.check(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n):
    if i == n-1:
        print(ans[i])
    else:
        print(ans[i],end=' ')

Solution (Python):




class UnionFind:
    def __init__(self, n):
        self.size = n
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
    def root(self, x):
        if self.par[x] != x:
            self.par[x] = self.root(self.par[x])
        return self.par[x]
    def unite(self, x, y):
        if self.root(x) == self.root(y):
            return
        if self.rank[x] > self.rank[y]:
            self.par[self.root(y)] = self.root(x)
        else:
            self.par[self.root(x)] = self.root(y)
        if self.rank[x] == self.rank[y]:
            self.rank[x]+=1
    def check(self, x, y):
        return self.root(x) == self.root(y)

n,m,k = map(int,input().split())
uf = UnionFind(n)
ans = [0 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    ans[a]-=1
    ans[b]-=1
co = [0 for i in range(n)]
for i in range(n):
    co[uf.root(i)]+=1
for i in range(n):
    ans[i] += co[uf.root(i)]-1
for i in  range(k):
    c,d = map(int,input().split())
    if uf.check(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n):
    if i == n-1:
        print(ans[i])
    else:
        print(ans[i],end=' ')

Solution (Python):



def mi():return map(int,input().split())

n,m,k=mi()
ab=[tuple(mi()) for _ in range(m)]
cd=[tuple(mi()) for _ in range(k)]



class UnionFind:
  def __init__(self,n):
    self.parent=[i for i in range(n)]
    self.rank=[0]*n
    self.count=0
  def root(self,a):
    if self.parent[a]==a:
      return a
    else:
      self.parent[a]=self.root(self.parent[a])
      return self.parent[a]
  def is_same(self,a,b):
    return self.root(a)==self.root(b)
  def unite(self,a,b):
    ra=self.root(a)
    rb=self.root(b)
    if ra==rb:
      return
    if self.rank[ra]<self.rank[rb]:
      self.parent[ra]=rb
    else:
      self.parent[rb]=ra
    if self.rank[ra]==self.rank[rb]:
      self.rank[ra]+=1
      self.count+=1
      
            
uf=UnionFind(n)
friends=[0 for _ in range(n)]
blocks=[[] for _ in range(n)]


for a,b in ab:
  a=a-1
  b=b-1
  friends[a]+=1
  friends[b]+=1
  uf.unite(a,b)
  
  
for i in range(n):
  uf.root(i)
  
for c,d in cd:
  c-=1;d-=1
  blocks[c]+=d,
  blocks[d]+=c,
  
    
import collections 
ctr=collections.Counter()
for i in range(n):
  ctr[uf.parent[i]]+=1
  
  
ans=[0]*n
for i in range(n):
  tmp=ctr[uf.root(i)]-1-friends[i]
  for b in blocks[i]:
    if uf.is_same(i,b):
      tmp-=1
  ans[i]=tmp
print(*ans)

Solution (Python):




class UnionFind:
    def __init__(self, n):
        self.size = n
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
    def root(self, x):
        if self.par[x] != x:
            self.par[x] = self.root(self.par[x])
        return self.par[x]
    def unite(self, x, y):
        if self.root(x) == self.root(y):
            return
        if self.rank[x] > self.rank[y]:
            self.par[self.root(y)] = self.root(x)
        else:
            self.par[self.root(x)] = self.root(y)
        if self.rank[x] == self.rank[y]:
            self.rank[x]+=1
    def check(self, x, y):
        return self.root(x) == self.root(y)

n,m,k = map(int,input().split())
uf = UnionFind(n)
ans = [0 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    ans[a]-=1
    ans[b]-=1
co = [0 for i in range(n)]
for i in range(n):
    co[uf.root(i)]+=1
for i in range(n):
    ans[i] += co[uf.root(i)]-1
for i in  range(k):
    c,d = map(int,input().split())
    if uf.check(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n):
    if i == n-1:
        print(ans[i])
    else:
        print(ans[i],end=' ')

Solution (Python):




class UnionFind:
    def __init__(self, n):
        self.size = n
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
    def root(self, x):
        if self.par[x] != x:
            self.par[x] = self.root(self.par[x])
        return self.par[x]
    def unite(self, x, y):
        if self.root(x) == self.root(y):
            return
        if self.rank[x] > self.rank[y]:
            self.par[self.root(y)] = self.root(x)
        else:
            self.par[self.root(x)] = self.root(y)
        if self.rank[x] == self.rank[y]:
            self.rank[x]+=1
    def check(self, x, y):
        return self.root(x) == self.root(y)

n,m,k = map(int,input().split())
uf = UnionFind(n)
ans = [0 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    ans[a]-=1
    ans[b]-=1
co = [0 for i in range(n)]
for i in range(n):
    co[uf.root(i)]+=1
for i in range(n):
    ans[i] += co[uf.root(i)]-1
for i in  range(k):
    c,d = map(int,input().split())
    if uf.check(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n):
    if i == n-1:
        print(ans[i])
    else:
        print(ans[i],end=' ')

Solution (Python):
import collections
import sys

readline = sys.stdin.buffer.readline


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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(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(x) == self.find(y)


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

    E = UnionFind(N)

    ans = [0 for _ in range(N)]
    for a, b in AB:
        a -= 1
        b -= 1
        E.unite(a, b)
        ans[a] -= 1
        ans[b] -= 1

    for i in range(N):
        E.find(i)

    ll = collections.defaultdict(int)
    for i in E.par:
        ll[i] += 1

    for i in range(N):
        ans[i] += ll[E.par[i]] - 1

    for i, j in CD:
        i -= 1
        j -= 1
        if E.same(i, j):
            ans[i] -= 1
            ans[j] -= 1

    print(*ans)


main()

Solution (Python):
import collections
import itertools
import sys

readline = sys.stdin.buffer.readline


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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(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(x) == self.find(y)


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

    E = UnionFind(N)

    ans = [0 for _ in range(N)]
    for a, b in AB:
        a -= 1
        b -= 1
        E.unite(a, b)
        ans[a] -= 1
        ans[b] -= 1

    for i in range(N):
        E.find(i)

    ll = collections.defaultdict(int)
    for i in E.par:
        ll[i] += 1

    for i in range(N):
        ans[i] += ll[E.par[i]] - 1

    for i, j in CD:
        i -= 1
        j -= 1
        if E.same(i, j):
            ans[i] -= 1
            ans[j] -= 1

    print(*ans)


main()

Solution (Python):
class UnionFind:
    def __init__(self, N):
        self.rank = [0] * N
        self.parent = [i for i in range(N)]
        self.n = N
        self.size = [1 for i in range(N)]
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if (x == y):
            return
        if (self.rank[x] < self.rank[y]):
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def get_parents(self):
        count = 0
        for i in range(self.n):
            if self.find(i) == i:
                count += 1
        return count
    def get_size(self, x):
        root = self.find(x)
        return self.size[root]
N,M,K = map(int,input().split())
U = UnionFind(N)
direct = [0 for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    U.unite(a,b)
    direct[a] += 1
    direct[b] += 1
neg = [0 for i in range(N)]
for i in range(K):
    c,d = map(int,input().split())
    c,d = c-1,d-1
    if U.same(c,d):
        neg[c] += 1
        neg[d] += 1
ans = []
for i in range(N):
    ans.append(U.get_size(i)-1-neg[i]-direct[i])
print(*ans)

Solution (Python):
class UnionFind:
    """
    素集合データ構造: 要素を素集合（互いに重ならない集合）に分割して管理するデータ構造
        Union: 2つの集合を1つに併合する
        Find: ある要素がどの集合に属しているかを判定する
    """

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

    def find(self, x):
        """
        要素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が属するグループと要素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):
        """
        要素xが属するグループのサイズ（要素数）を返す
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        要素x, yが同じグループに属するかどうかを返す
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        要素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):
        """
        print()での表示用
        """
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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

uf = UnionFind(n)
friend = [set() for _ in range(n)]
block = [set() for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friend[a].add(b)
    friend[b].add(a)
    uf.union(a, b)

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

for i in range(n):
    print(uf.size(i) - len(friend[i]) - len(block[i]) - 1, end=' ')

Solution (Python):
slct='D'


if slct=='C':
    N,M=map(int,input().split())
    cnd=[tuple(int(i) for i in input().split()) for j in range(M)]
    ans=-1
    for n in range(10**N):
        
        flag=True
        n_str=str(n)
        if len(n_str)!= N:
            continue
        for s,c in cnd:
            if n_str[s-1]!=str(c):
                
                flag=False
                break
        if flag:
            ans=n
            break
    print(ans)


elif slct=='D':
    N,M,K=map(int,input().split())
    
    par=[-1 for _ in range(N)]
    
    

    def root(n):
        if par[n]<0:
            return n
        else:
            par[n]=root(par[n]) 
            return par[n]
    
    def unite(m,n):
        x=root(m)
        y=root(n)
        if x==y: 
            return
        if par[x]>par[y]: 
            x,y=y,x 
        par[x]+=par[y] 
        par[y]=x 

    def issame(m,n):
        return root(m)==root(n)
    
    def size(n): 
        return -par[root(n)]
    
    
    
    ans=[-1 for _ in range(N)] 
    
    for _ in range(M): 
        A,B=map(int,input().split())
        unite(A-1,B-1)
        
        ans[A-1]-=1
        ans[B-1]-=1
    for _ in range(K): 
        C,D=map(int,input().split())
        
        if issame(C-1,D-1):
            ans[C-1]-=1
            ans[D-1]-=1
    for i in range(N): 
        print(ans[i]+size(i))

Solution (Python):
from collections import Counter
n, m, k = map(int, input().split())

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

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

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


friends = []
for i in range(n + 1):
    friends.append(UnionFind(i))

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    x, y = friends[a], friends[b]
    x_root, y_root = x.get_root(), y.get_root()
    if x_root.rank == y_root.rank:
        y_root.parent = x_root
        x_root.rank += 1
    elif x_root.rank > y_root.rank:
        y_root.parent = x_root
    else:
        x_root.parent = y_root

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


labels = [None] * (n + 1)
parents = [0] * (n + 1)
for i in range(1, n + 1):
    u = friends[i]
    parents[i] = u.get_root().val
CounterDict = Counter(parents)

for i in range(len(parents)):
    p = parents[i]
    labels[i] = [p, CounterDict.get(p)]

ans = []
for i in range(1, n + 1):
    num = labels[i][1] - 1
    for j in graph[i]:
        if labels[i][0] == labels[j][0]:
            num -= 1
    for k in block[i]:
        if labels[i][0] == labels[k][0]:
            num -= 1
    ans.append(num)
print(*ans)

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

    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.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[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)]

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

    def address(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.address()}

    def size(self,x):
        return -self.root[self.Find_Root(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)]

A=UnionFind(n+1)
C=[[] for _ in range(n+1)]
D=[[] for _ in range(n+1)]

for a,b in AB:
    A.Unite(a,b)
    C[a] +=[b]
    C[b] +=[a]

for c,d in CD:
    if A.isSameGroup(c,d):
        D[c] +=[d]
        D[d] +=[c]

ans=[]
for i in range(1,n+1):
    ans +=[A.size(i)-len(C[i])-len(D[i])-1]

print(*ans)

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

    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.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[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)]

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

    def address(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.address()}

    def size(self,x):
        return -self.root[self.Find_Root(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)]

A=UnionFind(n+1)
C=[[] for _ in range(n+1)]
D=[[] for _ in range(n+1)]

for a,b in AB:
    A.Unite(a,b)
    C[a] +=[b]
    C[b] +=[a]

for c,d in CD:
    if A.isSameGroup(c,d):
        D[c] +=[d]
        D[d] +=[c]

ans=[]
for i in range(1,n+1):
    ans +=[A.size(i)-len(C[i])-len(D[i])-1]

print(*ans)

Solution (Python):
class UnionFind:
    def __init__(self, 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 is_same_root(self, x, y):
        return self.find(x) == self.find(y)
 
    def get_group_size(self, x):
        return -self.parents[self.find(x)]
    
    
n,m,k=map(int,input().split())
uf = UnionFind(n)

ans=[0  for i in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    uf.union(x-1,y-1)
    ans[x-1]-=1
    ans[y-1]-=1
    
for i in range(k):
    x,y=map(int,input().split())
    if uf.is_same_root(x-1,y-1):
        ans[x-1]-=1
        ans[y-1]-=1

for i in range(n):
    ans[i]+=uf.get_group_size(i)-1
print(*ans)