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



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    fs = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())
        fs[a].add(b)
        fs[b].add(a)

    bs = tuple(set() for _ in range(N))
    for _ in range(K):
        a, b = (int(x) - 1 for x in input().split())
        bs[a].add(b)
        bs[b].add(a)

    roots = [-1] * N
    sizes = [-1] * N

    def dfs(v):
        """
        return: 連結成分のサイズを返す
        roots: 連結成分の各成分に根のindexを割り当てる
        """
        sz = 1
        for u in fs[v]:
            if ~roots[u]: continue
            roots[u] = roots[v]
            sz += dfs(u)
        return sz

    for v in range(N):
        if ~roots[v]: continue
        roots[v] = v
        sizes[v] = dfs(v)

    ans = []
    for v in range(N):
        r = roots[v]
        res = sizes[r] - 1 - len(fs[v]) - sum(1 for u in bs[v] if roots[u] == r)
        ans.append(res)

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import collections
N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]

CD = [tuple(map(int, input().split())) for i in range(K)]


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

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

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

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


# F = [set() for i in range(N)]
F = unionFind(N)
f = [set() for i in range(N)]
for a, b in AB:
    F.unite(a, b)
    a -= 1
    b -= 1
    f[a].add(b)
    f[b].add(a)

B = [set() for i in range(N)]
for c, d in CD:
    c -= 1
    d -= 1
    B[c].add(d)
    B[d].add(c)

ans = [0]*N
D = collections.defaultdict(set)
for i in range(N):
    D[F.root(i)].add(i)

# print(f)
for i in range(N):
    x = D[F.root(i)]
    ret = len(x)
    ret -= 1
    ret -= len(x & f[i])
    ret -= len(x & B[i])
    ans[i] = ret
print(*ans)

Submission status: Runtime Error

Solution code:
import collections
N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]

CD = [tuple(map(int, input().split())) for i in range(K)]


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

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

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

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


# F = [set() for i in range(N)]
F = unionFind(N)
f = [set() for i in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    f[a].add(b)
    f[b].add(a)
    F.unite(a+1, b+1)

B = [set() for i in range(N)]
for c, d in CD:
    c -= 1
    d -= 1
    B[c].add(d)
    B[d].add(c)

ans = [0]*N
# D = collections.defaultdict(set)
# for i in range(N):
#     D[F.root(i)].add(i)

# # print(f)
# for i in range(N):
#     x = D[F.root(i)]
#     ret = len(x)
#     ret -= 1
#     ret -= len(x & f[i])
#     ret -= len(x & B[i])
#     ans[i] = ret
print(*ans)

Submission status: Runtime Error

Solution code:
import collections
N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]

CD = [tuple(map(int, input().split())) for i in range(K)]


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

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

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

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


# F = [set() for i in range(N)]
F = unionFind(N)
f = [set() for i in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    f[a].add(b)
    f[b].add(a)
    F.unite(a+1, b+1)

B = [set() for i in range(N)]
for c, d in CD:
    c -= 1
    d -= 1
    B[c].add(d)
    B[d].add(c)

ans = [0]*N
D = collections.defaultdict(set)
for i in range(N):
    D[F.root(i)].add(i)

# # print(f)
# for i in range(N):
#     x = D[F.root(i)]
#     ret = len(x)
#     ret -= 1
#     ret -= len(x & f[i])
#     ret -= len(x & B[i])
#     ans[i] = ret
print(*ans)

Submission status: Runtime Error

Solution code:
import collections
N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]

CD = [tuple(map(int, input().split())) for i in range(K)]


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

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

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

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


# F = [set() for i in range(N)]
F = unionFind(N)
f = [set() for i in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    f[a].add(b)
    f[b].add(a)
    F.unite(a+1, b+1)

B = [set() for i in range(N)]
for c, d in CD:
    c -= 1
    d -= 1
    B[c].add(d)
    B[d].add(c)

ans = [0]*N
D = collections.defaultdict(set)
for i in range(N):
    D[F.root(i)].add(i)

# print(f)
for i in range(N):
    x = D[F.root(i)]
    ret = len(x)
    ret -= 1
    ret -= len(x & f[i])
    ret -= len(x & B[i])
    ans[i] = ret

print(*ans)

Submission status: Runtime Error

Solution code:
import collections
N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]

CD = [tuple(map(int, input().split())) for i in range(K)]


class unionFind:
    parent = []
    count = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.count = [1 for i in range(N)]

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

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

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.count[y] += self.count[x]
            self.count[x] = self.count[y]
            return

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


# F = [set() for i in range(N)]
F = unionFind(N)
f = [set() for i in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    f[a].add(b)
    f[b].add(a)
    F.unite(a+1, b+1)

B = [set() for i in range(N)]
for c, d in CD:
    c -= 1
    d -= 1
    B[c].add(d)
    B[d].add(c)

ans = [0]*N
D = collections.defaultdict(set)
for i in range(N):
    D[F.root(i)].add(i)

# print(f)
for i in range(N):
    x = D[F.root(i)]
    ret = len(x)
    ret -= 1
    ret -= len(x & f[i])
    ret -= len(x & B[i])
    ans[i] = ret

print(*ans)

Submission status: Runtime Error

Solution code:
q=int(input())
cnt1=0
for i in range(q):
    query=list(input().split())
    if int(query[0])==1:
        cnt1+=1
    else:
        if (int(query[1])+cnt1)%2==0:
            s.join(query[2])
        else:
            query[2].join(s)
if cnt1%2==0:
    print(s)
else:
    s2=""
    for i in range(len(s)):
        s2.join(s[-1-i])
    print(s2)

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split(' ')]
SC = []
for _ in range(M):
    SC.append([int(i) for i in input().split(' ')])

ch = [-1] * N
for s,c in SC:
    if N >1:
        if s == 1 and c == 0:
            print(-1)
            exit()

    if ch[s-1] == -1 or ch[s-1] == c:
        ch[s-1] = c
    else:
        print(-1)
        exit()
s = 10**(N-1) if N >1 else 0
f = 10 ** N if N >1 else 10
for n in range(s,f):
    n = list(str(n))
    flg = 0
    for s,c in SC:
        if not n[s-1] == str(c):
            flg = 1

    if flg == 0:
        print(''.join(n))
        exit()

Submission status: Runtime Error

Solution code:
#https://www.slideshare.net/chokudai/union-find-49066733
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.ranks = [0] * self.n
    self.parents = list(range(self.n))

  def find(self, x):
    if self.parents[x] == x:
      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.ranks[x] > self.ranks[y]:
      x, y = y, x
    if self.ranks[x] == self.ranks[y]:
      self.ranks[x] += 1

    self.parents[y] = x
        
  def issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def get_root_members(self):
    roots = set(self.parents) 
    self.root_members = {r:[] for r in roots}
    for i, r in enumerate(self.parents):
      if r != i:
      	self.root_members[r].append(i)
    return self.root_members
  
  def get_node_members(self):
    self.get_root_members()
    return [self.root_members[r] for r in self.parents]
  
N = list(map(int, input().split()))
uf = UnionFind(N[0])
results = [[] for i in range(N[0])]
for i in range(N[1]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x].append(y)
  results[y].append(x)
  uf.union(x, y)
#print(uf.parents)

for i in range(N[2]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x].append(y)
  results[y].append(x)
  
node_members = uf.get_node_members()
#print(node_members, results)

# どうやら set で解くべきではなさそう
print(" ".join([str(len(set(node_members[i]) - set(results[i]) - set([i]))) for i in range(N[0])]))

Submission status: Runtime Error

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

groups = [None] * N
visited = set()

# 連結成分を求める
def dfs(group, i):
  if i in visited:
    return
  
  visited.add(i)
  group.add(i)
  groups[i] = group
  # 他のノード
  for c in graph[i]:
    if not c in visited:
      dfs(group, c)
  

graph = [set() for _ in range(N)]

friends_count = [0] * N
block_count = [0] * N

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  friends_count[a] += 1
  friends_count[b] += 1
  graph[a].add(b)
  graph[b].add(a)
  
for i in range(N):
  dfs(set(), i)
      
for _ in range(K):
  c, d = map(int, input().split())
  c, d = c - 1, d - 1
  
  # 同じ連結成分に含まれないブロック関係は無視してok
  if d in groups[c]:
    block_count[c] += 1
    block_count[d] += 1

candidates = []

for i in range(N): 
  candidates.append(
    len(groups[i]) - friends_count[i] - block_count[i] - 1
  )
    
print(' '.join(str(x) for x in candidates))

Submission status: Runtime Error

Solution code:
#https://www.slideshare.net/chokudai/union-find-49066733
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.ranks = [0] * self.n
    self.parents = list(range(self.n))

  def find(self, x):
    if self.parents[x] == x:
      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.ranks[x] > self.ranks[y]:
      x, y = y, x
    if self.ranks[x] == self.ranks[y]:
      self.ranks[x] += 1

    self.parents[y] = x
        
  def issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def get_root_members(self):
    roots = set(self.parents) 
    self.root_members = {r:[] for r in roots}
    for i, r in enumerate(self.parents):
      if r != -1:
      	self.root_members[r].append(i)
    return self.root_members
  
  def get_node_members(self):
    self.get_root_members()
    return [self.root_members[r] for r in self.parents]
  
N = list(map(int, input().split()))
uf = UnionFind(N[0])
results = [[] for i in range(N[0])]
for i in range(N[1]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x].append(y)
  results[y].append(x)
  uf.union(x, y)
#print(uf.parents)

for i in range(N[2]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x].append(y)
  results[y].append(x)
  
node_members = uf.get_node_members()
#print(node_members, results)

print(" ".join([str(len(set(node_members[i]) - set(results[i])) - 1) for i in range(N[0])]))

Submission status: Runtime Error

Solution code:
class UnionFind:
  def __init__(self, size):
    self.parents = [x for x in range(size)]
    self.sizes = [1] * size
  
  def unite(self, a, b):
    if self.find(a) == self.find(b):
      return
    
    if self.size_of(a) > self.size_of(b):
      self.sizes[self.find(a)] += self.size_of(b)
      self.parents[self.find(b)] = self.find(a)
    else:
      self.sizes[self.find(b)] += self.size_of(a)
      self.parents[self.find(a)] = self.find(b)
  
  def is_same(self, a, b):
    return self.find(a) == self.find(b)
  
  def size_of(self, a):
    return self.sizes[self.find(a)]
  
  def find(self, a):
    if a == self.parents[a]:
      return a
    else:
      self.parents[a] = self.find(self.parents[a])
      return self.parents[a]


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

u = UnionFind(N)

# 自分自身・友達・ブロック関係のいずれかの場合はフラグ立つ
relations = [1 << i for i in range(N)]

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  relations[a] |= 1 << b
  relations[b] |= 1 << a
  u.unite(a, b)
  
for _ in range(K):
  c, d = map(int, input().split())
  c, d = c - 1, d - 1
  
  # 同じ連結成分に含まれないブロック関係は無視してok
  if u.is_same(c, d):
    relations[c] |= 1 << d
    relations[d] |= 1 << c

candidates = []

for i in range(N):
  # candidates.append(u.size_of(i) - bin(relations[i]).count('1'))
  candidates.append(u.size_of(i)
    
print(' '.join(str(x) for x in candidates))

Submission status: Runtime Error

Solution code:
import numpy as np
import scipy.sparse
from itertools import combinations
N,M,K = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]
lil = scipy.sparse.lil_matrix((N, N), dtype = int)
for i in range(M):
    lil[AB[i][0]-1, AB[i][1]-1] = 1
    lil[AB[i][1]-1, AB[i][0]-1] = 1
lil2 = scipy.sparse.csgraph.dijkstra(lil, directed = False).astype(int)
block = np.zeros((N, N))
for i in range(K):
    block[CD[i][0]-1, CD[i][1]-1] = -100000
    block[CD[i][1]-1, CD[i][0]-1] = -100000
sug = lil2 + block
ans = [np.count_nonzero(sug[i] > 1) for i in range(N)]
print(*ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
  def __init__(self,n):
    self.n=n
    self.parent=[-1]*(n+1)
    
  def union(self,a,b):
    ra=self.root(a)
    rb=self.root(b)
    if ra==rb:
      return
    if self.rank(a) < self.rank(b):
      self.parent[ra] += self.parent[rb]
      self.parent[rb] = ra
    else:
      self.parent[rb] += self.parent[ra]
      self.parent[ra] = rb
    #print(self.parent)
      
  def root(self,a):
    if self.parent[a] < 0:
      return a
    else:
      r = self.root(self.parent[a])
      return r
  
  def rank(self,a):
    r=0
    x=a
    while True:
      if self.parent[x]<0:
        break
      x=self.parent[x]
      r+=1
    return r
    
  def size(self,a):
    return -self.parent[self.root(a)]
  
n,m,k = map(int,input().split())
uni = UnionFind(n)
friend = [0]*(n+1)
for i in range(m):
  a,b = map(int,input().split())
  uni.union(a,b)
  friend[a] += 1
  friend[b] += 1
block = [0]*(n+1)
for i in range(k):
  a,b = map(int,input().split())
  if uni.root(a) == uni.root(b):
    block[a] += 1
    block[b] += 1
ans=[0]*n
for i in range(1,n+1):
  ans[i-1] = uni.size(i) - friend[i] - block[i] - 1
for i in range(n):
  print(max(0,ans[i]),end=' ')
else:
  print()

Submission status: Runtime Error

Solution code:
class UnionFind:
  def __init__(self,n):
    self.n=n
    self.parent=[-1]*(n+1)
    
  def union(self,a,b):
    if self.root(a) == self.root(b):
      return
    if self.rank(a) < self.rank(b):
      self.parent[self.root(a)] += self.parent[self.root(b)]
      self.parent[self.root(b)] = self.root(a)
    else:
      self.parent[self.root(b)] += self.parent[self.root(a)]
      self.parent[self.root(a)] = self.root(b)
    #print(self.parent)
      
  def root(self,a):
    if self.parent[a] < 0:
      return a
    else:
      r = self.root(self.parent[a])
      return r
  
  def rank(self,a):
    r=0
    x=a
    while True:
      if self.parent[x]<0:
        break
      x=self.parent[x]
      r+=1
    return r
    
  def size(self,a):
    return -self.parent[self.root(a)]
  
n,m,k=map(int,input().split())
uni=UnionFind(n)
friend=[0]*(n+1)
for i in range(m):
  a,b=map(int,input().split())
  uni.union(a,b)
  friend[a]+=1
  friend[b]+=1
block=[0]*(n+1)
for i in range(k):
  a,b=map(int,input().split())
  if uni.root(a)==uni.root(b):
    block[a]+=1
    block[b]+=1
ans=[0]*n
for i in range(1,n+1):
  ans[i-1] = uni.size(i) - friend[i] - block[i] - 1
for i in range(n):
  print(max(0,ans[i]),end=' ')
else:
  print()

Submission status: Runtime Error

Solution code:
class UnionFind:
  def __init__(self,n):
    self.n=n
    self.parent=[-1 for i in range(n)]
    
  def union(self,a,b):
    if self.root(a) == self.root(b):
      return
    if self.size(a) > self.size(b):
      self.parent[a-1] += self.parent[b-1]
      self.parent[b-1] = a-1
    else:
      self.parent[a-1] = b-1
      self.parent[b-1] += self.parent[a-1]
      
  def root(self,a):
    if self.parent[a-1]==-1:
      return a-1
    else:
      return self.root(self.parent[a-1])
    
  def size(self,a):
    return -self.parent[self.root(a)]
  
n,m,k=map(int,input().split())
uni=UnionFind(n)
friend=[0]*n
for i in range(m):
  a,b=map(int,input().split())
  uni.union(a,b)
  friend[a-1]+=1
  friend[b-1]+=1
block=[0]*n
for i in range(k):
  a,b=map(int,input().split())
  if uni.root(a)==uni.root(b):
    block[a]+=1
    block[b]+=1
ans=[0]*n
for i in range(n):
  ans[i]=uni.size(i)-friend[i]-block[i]-1
for i in range(n):
  print(max(0,ans[i]),end=' ')
else:
  print()

Submission status: Runtime Error

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

fgraph = [list() for _ in range(n)]  # 隣接行列のリスト版
bgraph = [list() for _ in range(n)]  # brock関係のグラフ
cgraph = [list() for _ in range(n)]  # 友達候補のグラフ
rks = [None]*n


def dfs(graph, s, r):  # 深さ優先探索
    if rks[s] is None:
        rks[s] = r
    for j in range(len(graph[s])):
        if rks[graph[s][j] - 1] is not None:
            continue
        dfs(graph, graph[s][j]-1, r)


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

 # fgraphの連結成分を調べる
c = -1
for i in range(n):
    if rks[i] is None:
        c += 1
        dfs(fgraph, i, c)  # iから始めるDFS。ｃが同じなら同じ連結成分にいる

for i in range(k):
    c, d = map(int, input().split())
    if rks[c-1] == rks[d-1]:  # 同一連結成分の中でのブロック関係のみ注目
        bgraph[c-1].append(d)
        bgraph[d-1].append(c)

counter = Counter(rks)
for i in range(n):
    print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

Submission status: Runtime Error

Solution code:
＃@YottyPG　Qiita
from collections import deque

N,M,K = map(int,input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int,input().split())) for _ in range(K)]

f = [set() for _ in range(N+1)]
b = [set() for _ in range(N+1)]

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

stack=deque()
ans = [0]*(N+1)
visited = [0]*(N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in f[n]:
            if visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    for i in link:
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1
print(*ans[1:])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def dfs(v, seen, overall, connected_components):
    seen[v] = True
    connected_components.add(v)
    for nv in overall[v]:
        if seen[nv] == True:continue
        dfs(nv, seen, overall, connected_components)
def main():
    N, M, K = map(int, input().split())
    overall = {}
    friends = {}
    blocks = {}
    for i in range(N):
        overall[i] = set()
        friends[i] = set()
        blocks[i] = set()
    for _ in range(M):
        a, b = map(int, input().split())
        overall[a-1].add(b-1)
        overall[b-1].add(a-1)
        friends[a-1].add(b-1)
        friends[b-1].add(a-1)
    for _ in range(K):
        c, d = map(int, input().split())
        blocks[c-1].add(d-1)
        blocks[d-1].add(c-1)
    ans = {}
    seen = [False] * N
    for i in range(N):
        if seen[i] == True:continue
        connected_components = set()
        dfs(i, seen, overall, connected_components)
        for v in list(connected_components):
            ans[v] = connected_components - {v}
    for i in range(N):
        print(len(ans[i]-friends[i]-blocks[i]), end=" ")
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys 
sys.setrecursionlimit(10000)

class union_find:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1 for i in range(N)]
        self.excluded = [0 for i in range(N)]
    
    def root(self, a):
        if self.par[a] == a:
            return a
        else:
            # 経路圧縮
            self.par[a] = self.root(self.par[a])
            return self.par[a]
    
    def same(self, a, b):
        return self.root(a) == self.root(b)
    
    def unite(self, a, b):
        if not self.same(a, b):
            self.size[self.root(b)] += self.get_union_size(a)
            self.par[self.root(a)] = self.root(b)
    
    def friend(self, a, b):
        self.unite(a, b)
        self.excluded[a] += 1
        self.excluded[b] += 1
    
    def block(self, a, b):
        if self.same(a, b):
            self.excluded[a] += 1
            self.excluded[b] += 1

    def get_union_size(self, a):
        return self.size[self.root(a)]
    
    def get_friend_sugestion_size(self, a):
        return self.get_union_size(a) - 1 - self.excluded[a]

N, M, K = map(int, input().split())
UF = union_find(N)
for i in range(M):
    A, B = map(int, input().split())
    UF.friend(A-1, B-1)
for i in range(K):
    A, B = map(int, input().split())
    UF.block(A-1, B-1)
print(*[UF.get_friend_sugestion_size(x) for x in range(N)])

Submission status: Runtime Error

Solution code:
class union_find:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1 for i in range(N)]
        self.excluded = [0 for i in range(N)]
    
    def root(self, a):
        if self.par[a] == a:
            return a
        else:
            # 経路圧縮
            self.par[a] = self.root(self.par[a])
            return self.par[a]
    
    def same(self, a, b):
        return self.root(a) == self.root(b)
    
    def unite(self, a, b):
        if not self.same(a, b):
            self.size[self.root(b)] += self.get_union_size(a)
            self.par[self.root(a)] = self.root(b)
    
    def friend(self, a, b):
        self.unite(a, b)
        self.excluded[a] += 1
        self.excluded[b] += 1
    
    def block(self, a, b):
        if self.same(a, b):
            self.excluded[a] += 1
            self.excluded[b] += 1

    def get_union_size(self, a):
        return self.size[self.root(a)]
    
    def get_friend_sugestion_size(self, a):
        return self.get_union_size(a) - 1 - self.excluded[a]

N, M, K = map(int, input().split())
UF = union_find(N)
for i in range(M):
    A, B = map(int, input().split())
    UF.friend(A-1, B-1)
for i in range(K):
    A, B = map(int, input().split())
    UF.block(A-1, B-1)
print(*[UF.get_friend_sugestion_size(x) for x in range(N)])

Submission status: Runtime Error

Solution code:
class union_find:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.friends = [[] for i in range(N)]
        self.blocks = [[] for i in range(N)]
        self.size = [1 for i in range(N)]
    
    def root(self, a):
        if self.par[a] == a:
            return a
        else:
            # 経路圧縮
            self.par[a] = self.root(self.par[a])
            return self.par[a]
    
    def same(self, a, b):
        return self.root(a) == self.root(b)
    
    def unite(self, a, b):
        if not self.same(a, b):
            self.size[self.root(b)] += self.get_union_size(a)
            self.par[self.root(a)] = self.root(b)
    
    def friend(self, a, b):
        self.friends[a].append(b)
        self.friends[b].append(a)
        self.unite(a, b)
    
    def block(self, a, b):
        self.blocks[a].append(b)
        self.blocks[b].append(a)

    def get_union_size(self, a):
        return self.size[self.root(a)]
    
    def get_friend_sugestion_size(self, a):
        excluded = len([x for x in set(self.friends[a] + self.blocks[a]) if self.root(x) == self.root(a)])
        return self.get_union_size(a) - 1 - excluded

N, M, K = map(int, input().split())
UF = union_find(N)
for i in range(M):
    A, B = map(int, input().split())
    UF.friend(A-1, B-1)
for i in range(K):
    A, B = map(int, input().split())
    UF.block(A-1, B-1)
print(*[UF.get_friend_sugestion_size(x) for x in range(N)])

Submission status: Runtime Error

Solution code:
import sys
import collections
input = sys.stdin.readline

N, M, K = map(int, input().split())
F = []
for i in range(M):
	F.append(list(map(int, input().split())))
B = []
for i in range(K):
	B.append(list(map(int, input().split())))

def get_group(F):
	def root(a):
		if G[a] == a: return a
		G[a] = root(G[a])
		return G[a]
	def union(a, b):
		ra = root(a)
		rb = root(b)
		if ra == rb: return
		G[ra] = rb
	G = [i for i in range(N)]
	for a, b in F:
		a -= 1
		b -= 1
		union(a, b)
	for i in range(N):
		G[i] = root(i)
	return G

def calc_count(F, G):
	edges = collections.defaultdict(set)
	for a, b in F:
		a -= 1
		b -= 1
		if G[a] == G[b]:
			edges[a].add(b)
			edges[b].add(a)
	cnt = [0] * N
	for i in range(N):
		cnt[i] = len(edges[i])
	return cnt

def get_num(c, f, b):
	ret = (c-1) - f - b
	return ret

G = get_group(F)
C = collections.Counter(G)
FC = calc_count(F, G)
BC = calc_count(B, G)
ans = [0] * N
for i in range(N):
	ans[i] = get_num(C[G[i]], FC[i], BC[i])

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

Submission status: Runtime Error

Solution code:
class UnionFind():
    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):#all_group_members O(N)かかるので注意
        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)
ab=[]
cd=[]
for i in range(m):
    ab.append(list(map(int,input().split())))

for i in range(k):
    cd.append(list(map(int,input().split())))



for i in range(m):
   # print("gn")
    a=ab[i][0]
    b=ab[i][1]
    if uf.same(a,b)==False:
        uf.union(a,b)
friend=[]
for i in range(1,n+1):#グループ分けをする（友達でも友達候補でもブロック関係でもカウント
    friend.append(uf.size(i)-1)

block=[0]*n
for i in range(m):#友達のところは友達候補にならない
    a=ab[i][0]-1
    b=ab[i][1]-1
    block[a]+=1
    block[b]+=1

for i in range(k):
    if uf.same(a,b)==True:#そもそも友達候補関係になってなかったら
        a=cd[i][0]-1
        b=cd[i][1]-1
        block[a]+=1
        block[b]+=1

"""
for i in range(n):
    print(block[i],end=" ")
print()
"""
for i in range(n):
    print(friend[i]-block[i],end=" ")