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:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    
    N, M, K = map(int, input().split())
    G = {v: deque([]) for v in range(N)}
    G_original = {v: deque([]) for v in range(N)}
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
        G_original[a].append(b)
        G_original[b].append(a)

    Block = {v: deque([]) for v in range(N)}
    for _ in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        Block[c].append(d)
        Block[d].append(c)

    # seen = [0]*(N)
    # stack = []
    color = {v: None for v in range(N)}
    col2v = {col: set() for col in range(N)}
    
    # def dfs(j, col):
    #     if color[j] is not None:
    #         return
    #     # seen[j] = 1
    #     col2v[col] = set()
    #     stack.append(j)
    #     color[j] = col
    #     col2v[col].add(j)
    #     while stack:
    #         s = stack[-1]
    #         if not G[s]:
    #             stack.pop()
    #             continue
    #         g_NO  = G[s].popleft()
    #         if color[g_NO] is not None:
    #             continue
    #         color[g_NO] = col
    #         col2v[col].add(g_NO)
    #         # color[g_NO] = 1
    #         stack.append(g_NO)
    def dfs(node, co):
        if color[node] is not None:
            return
        
        color[node] = co
        col2v[co].add(node)
        for n in G[node]:
            dfs(n, co)
        return
        
    c = 0
    for start in range(N):
        dfs(start, c)
        c += 1
    
    ans = []
    for v in range(N):
        # kouho = col2v[color[v]]
        # # print(kouho)
        # block = Block[v]
        # # print(block)
        # friend = G_original[v]
        # # print(friend)
        # tmp = kouho - set(block + friend)
        ans.append(len(col2v[color[v]] - set(Block[v]+G_original[v]))-1)
        
        # print("##############")
    print(*ans)
main()

Submission status: Runtime Error

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

def main():
    
    N, M, K = map(int, input().split())
    G = {v: deque([]) for v in range(N)}
    G_original = {v: deque([]) for v in range(N)}
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
        G_original[a].append(b)
        G_original[b].append(a)

    Block = {v: set() for v in range(N)}
    for _ in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        Block[c].add(d)
        Block[d].add(c)

    # seen = [0]*(N)
    # stack = []
    color = {v: None for v in range(N)}
    col2v = {col: set() for col in range(N)}
    
    # def dfs(j, col):
    #     if color[j] is not None:
    #         return
    #     # seen[j] = 1
    #     col2v[col] = set()
    #     stack.append(j)
    #     color[j] = col
    #     col2v[col].add(j)
    #     while stack:
    #         s = stack[-1]
    #         if not G[s]:
    #             stack.pop()
    #             continue
    #         g_NO  = G[s].popleft()
    #         if color[g_NO] is not None:
    #             continue
    #         color[g_NO] = col
    #         col2v[col].add(g_NO)
    #         # color[g_NO] = 1
    #         stack.append(g_NO)
    def dfs(node, co):
        if color[node] is not None:
            return
        
        color[node] = co
        col2v[co].add(node)
        for n in G[node]:
            dfs(n, co)
        return
        
    c = 0
    for start in range(N):
        dfs(start, c)
        c += 1
    
    ans = []
    for v in range(N):
        kouho = col2v[color[v]]
        # print(kouho)
        block = Block[v]
        # print(block)
        friend = G_original[v]
        # print(friend)
        tmp = kouho - block - set(friend)
        ans.append(len(tmp)-1)
        
        # print("##############")
    print(*ans)
main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
c=0
def main():
    global c
    N, M, K = map(int, input().split())
    G = {v: deque([]) for v in range(N)}
    G_original = {v: deque([]) for v in range(N)}
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
        G_original[a].append(b)
        G_original[b].append(a)

    Block = {v: deque([]) for v in range(N)}
    for _ in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        Block[c].append(d)
        Block[d].append(c)

    seen = [0]*(N)
    stack = []
    color = {v: -1 for v in range(N)}
    col2v = {color: [] for color in range(N+4)}
    
    def dfs(j, col):
        global c
        if seen[j]:
            return
        seen[j] = 1
        stack.append(j)
        color[j] = col
        col2v[col].append(j)
        while stack:
            s = stack[-1]
            if not G[s]:
                stack.pop()
                continue
            g_NO  = G[s].popleft()
            if seen[g_NO]:
                continue
            color[g_NO] = col
            col2v[col].append(g_NO)
            seen[g_NO] = 1
            stack.append(g_NO)
        c += 1
        
    
    for start in range(N):
        dfs(start, c)

    ans = []
    for v in range(N):
        kouho = col2v[color[v]]
        # print(kouho)
        block = Block[v]
        # print(block)
        friend = G_original[v]
        # print(friend)
        tmp = set(kouho).difference(block).difference(friend)
        ans.append(len(tmp)-1)
        
        # print("##############")
    print(*ans)
main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000)
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())
path = dict()
block = [set() for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  if a-1 in path:
    path[a-1].add(b-1)
  else:
    path[a-1] = {b-1}
  if b-1 in path:
    path[b-1].add(a-1)
  else:
    path[b-1] = {a-1}
    
for _ in range(k):
  c,d=map(int,input().split())
  block[c-1].add(d-1)
  block[d-1].add(c-1)

uf = UnionFind(n)
for i, x in path.items():
  for j in x:
    uf.union(i,j)

uf.find(0)

ans = [0]*n
for i in range(n):
  ans[i] = len(uf.members(i) - path[i] - block[i]) -1
print(*ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000)

"""
方針
1. つながってるやつ全員candにぶちこむ
2. 各iについて所属candからblock[i]を差し引く
"""
n,m,k=map(int,input().split())
group = list()
path = dict()
block = [set() for i in range(n+1)]
for _ in range(m):
  a,b = map(int,input().split())
  if a in path:
    path[a].add(b)
  else:
    path[a] = {b}
  if b in path:
    path[b].add(a)
  else:
    path[b] = {a}
for _ in range(k):
  c,d = map(int,input().split())
  block[c].add(d)
  block[d].add(c)

group = list()
memo = [-1]*(n+1)

def rec(g, i):
  res = set()
  memo[i] = g
  #print('call', g, i)
  for p in path[i]:
    if memo[p] < 0:
      res |= rec(g, p)
      memo[p] = g
  #print(g,i,path[i], res)
  if len(res) > 0:
    return res | {i}
  else:
    return {i}
  
for i in range(1,n+1):
  if memo[i] < 0:
    group.append(rec(len(group), i))

ans = list()
for i in range(1,n+1):
  candi = group[memo[i]] - path[i] - block[i] - {i}
  ans.append(len(candi))
#print(*group)
#print(*[[i,b] for i,b in enumerate(block) if len(b) > 0])
print(*ans)

Submission status: Runtime Error

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

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=mp()
uf=UnionFind(n+1)
fr=[[0]*(n+1) for i in range(n+1)]
br=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    a,b=mp()
    fr[a][b]=1
    fr[b][a]=1
    uf.union(a,b)
for i in range(k):
    c,d=mp()
    br[c][d]=1
    br[d][c]=1
ans=[]
for i in range(1,n+1):
    c=-1
    for j in uf.members(i):
        if fr[i][j]==0 and br[i][j]==0:
            c+=1
    ans.append(c)
print(*ans)

Submission status: Runtime Error

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

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=mp()
uf=UnionFind(n+1)
fr=[[0]*(n+1) for i in range(n+1)]
br=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    a,b=mp()
    fr[a][b]=1
    fr[b][a]=1
    uf.union(a,b)
for i in range(k):
    c,d=mp()
    br[c][d]=1
    br[d][c]=1
ans=[]
for i in range(1,n+1):
    c=-1
    for j in range(1,n+1):
        if uf.find(i)==uf.find(j) and fr[i][j]==0 and br[i][j]==0:
            c+=1
    ans.append(c)
print(*ans)

Submission status: Runtime Error

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

    G=[[] for i in range(N)]
    B = [[] for i in range(N)]

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

    C=[]
    D=[]
    for i in range(K):
        c,d=map(int,input().split())
        C.append(c-1)
        D.append(d-1)
    trace=[-1 for i in range(N)]
    Group=[]
    Group_tmp=[]
    def dfs(n):
        if trace[n]!=-1:
            return 0
        Group_tmp.append(n)
        trace[n]=0
        for dist in G[n]:
            dfs(dist)
        if len(G[n])==0:
            return 0

    for i in range(len(trace)):
        if trace[i]==-1:
            Group_tmp=[]
            dfs(i)
            Group.append(Group_tmp)

    res=[0 for i in range(N)]
    GroupMarker=[-1 for i in range(N)]

    for i in range(len(Group)):
        for j in range(len(Group[i])):
            person=Group[i][j]
            GroupMarker[person]=i
            r=len(Group[i])-len(G[person])-1
            res[person]=r
    for i in range(K):
        if D[i] in Group[GroupMarker[C[i]]]:
            res[D[i]]-=1
            res[C[i]]-=1

    res=list(map(str,res))
    print(" ".join(res))

if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
def dfs(graph, cur_pos, visited, group):
    if cur_pos in visited:
        return
    group[cur_pos] = visited
    nexts = graph[cur_pos]
    for n in nexts:
        visited.add(cur_pos)
        dfs(graph, n, visited, group)

def solve():
    N,M,K = [int(i) for i in input().split()]
    graph_M = {}
    graph_K = {}
    for i in range(1, N+1):
        graph_M[i] = set([])
        graph_K[i] = set([])
    for i in range(M):
        pair = [int(num) for num in input().split()]
        a,b = pair
        graph_M[a].add(b)
        graph_M[b].add(a)
    for i in range(K):
        pair = [int(num) for num in input().split()]
        a,b = pair
        graph_K[a].add(b)
        graph_K[b].add(a)

    group_M = {}
    for i in range(1, N+1):
        if i in group_M:
            continue
        dfs(graph_M, i, set(), group_M)
    group_K = {}
    for i in range(1, N+1):
        if i in group_K:
            continue
        dfs(graph_K, i, set(), group_K)
    ans = []
    for i in range(1, N+1):
        candidates = group_M[i]-group_K[i]-graph_M[i]-set([i])
        ans.append(str(len(candidates)))
    print(' '.join(ans))

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
friend = {}
for i in range(M):
    A, B = map(lambda x: x-1, map(int, input().split()))
    if A not in friend:
        friend[A] = []
    if B not in friend:
        friend[B] = []
    friend[A].append(B)
    friend[B].append(A)

block = {}
for i in range(K):
    C, D = map(lambda x: x-1, map(int, input().split()))
    if C not in block:
        block[C] = []
    if D not in block:
        block[D] = []
    block[C].append(D)
    block[D].append(C)

first = {}
for i in range(N):
    if i not in first:
        first[i] = i
        queue = []
        queue.extend(friend[i])
        counter = 0
        while counter < len(queue):
            item = queue[counter]
            first[item] = i
            for n in friend[item]:
                if n not in first:
                    queue.append(n)
            counter += 1

size = {}
for key in first:
    if first[key] not in size:
        size[first[key]] = 1
    else:
        size[first[key]] += 1

for i in range(N):
    if i not in friend:
        print(0)
        continue
    no_friend = 0
    if i in block:
        for b in block[i]:
            if first[b] == first[i]:
                no_friend += 1
    print(size[first[i]] - len(friend[i]) - no_friend - 1)

Submission status: Runtime Error

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

n,m,k =map(int,input().split())# nは頂点の数、mは辺の数
g = [[] for _ in range(n)] # 隣接リスト
g_sub = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)
for _ in range(k):
    c, d = [int(x) for x in input().split()]
    g_sub[c-1].append(d-1)
    g_sub[d-1].append(c-1)

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d
answer=[]
for i in range(0,n):
    d=bfs(i)
    for j in range(len(g_sub[i])):
        d[g_sub[i][j]]="#"
    s=0
    for l in range(len(d)):
        if (d[l]!="None" and d[l]!="#"):
            if d[l]>=2:
                s+=1
    answer.append(s)
print(answer)

Submission status: Runtime Error

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

n,m,k =map(int,input().split())# nは頂点の数、mは辺の数
g = [[] for _ in range(n)] # 隣接リスト
g_sub = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a].append(b)
    g[b].append(a)
for _ in range(k):
    c, d = [int(x) for x in input().split()]
    g_sub[c].append(d)
    g_sub[d].append(c)

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d
answer=[]
for i in range(0,N):
    d=bfs(i)
    for j in range(len(g_sub[i])):
        d[g_sub[i][j]]="None"
    s=0
    for l in range(len(d)):
        if g[l]!="None":
            s+=1
    s+=1
    answer.append(s)
print(answer)

Submission status: Runtime Error

Solution code:
import resource;
# 再帰回数上弦を100000回に設定
sys.setrecursionlimit(100000)
# スタックサイズを無制限に設定
# resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

class UnionFind:
    """
    子ノードには自分の親ノードIDを記録。親ノードにはグループサイズの負値を記録。
    """

    def __init__(self, n):
        self.node = [-1] * n
    
    def unite(self, x, y):
        """
        xとyが属するグループを統合
        """
        # xとyの親ノードインデックスを取得
        _x, _y = self.find(x), self.find(y)
        # 一致していれば同じグループに属しているので処理終了。
        # Falseはなぞ。
        if _x == _y:
            return False
        # サイズが小さいグループを大きいグループに結合するので、
        # _y側の絶対値がかならず小さくなるように前処理。(_yを_xのグループへ統合)
        # 大きい方を小さい方へ結合してしまうとノードが深くなってしまうので、
        # 計算量を削減するためのテクニック。
        if abs(self.node[_x]) < abs(self.node[_y]):
             self.node[_x], self.node[_y] = self.node[_y], self.node[_x]
        # グループサイズ更新
        self.node[_x] += self.node[_y]
        # _yの親ノードを_xに更新
        self.node[_y] = _x
        return True

    def find(self, x):
        """
        xが属するグループの親ノードインデックスを検索。
        """
        _val = self.node[x]
        # 負なら親ノードとみなして、そのインデックスを返す。
        if _val < 0: 
            return x
        # グループの親ノードを再帰的に検索。
        # さらに、グループの親ノードIDを子ノードに記録しておくことで
        # 経路縮小を実現。
        self.node[x] = self.find(_val)
        return self.node[x]

    def same(self, x, y):
        """
        xとyが属するグループが同じかチェック。
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        xが属するグループの総サイズ取得
        """
        return abs(self.node[self.find(x)])
 
    def __str__(self):
        return str(self.node)

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

uf = UnionFind(N)
friend = [0] * N
block = [[] for _ in range(N)]

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

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

for i in range(N):
    ans = uf.size(i) - friend[i] - 1
    for j in block[i]:
        if uf.same(i, j):
            ans -= 1
    print("{} ".format(ans), end="")
print("")

Submission status: Runtime Error

Solution code:
class UnionFind:
    """
    子ノードには自分の親ノードIDを記録。親ノードにはグループサイズの負値を記録。
    """

    def __init__(self, n):
        self.node = [-1] * n
    
    def unite(self, x, y):
        """
        xとyが属するグループを統合
        """
        # xとyの親ノードインデックスを取得
        _x, _y = self.find(x), self.find(y)
        # 一致していれば同じグループに属しているので処理終了。
        # Falseはなぞ。
        if _x == _y:
            return False
        # サイズが小さいグループを大きいグループに結合するので、
        # _y側の絶対値がかならず小さくなるように前処理。(_yを_xのグループへ統合)
        # 大きい方を小さい方へ結合してしまうとノードが深くなってしまうので、
        # 計算量を削減するためのテクニック。
        if abs(self.node[_x]) < abs(self.node[_y]):
             self.node[_x], self.node[_y] = self.node[_y], self.node[_x]
        # グループサイズ更新
        self.node[_x] += self.node[_y]
        # _yの親ノードを_xに更新
        self.node[_y] = _x
        return True

    def find(self, x):
        """
        xが属するグループの親ノードインデックスを検索。
        """
        _val = self.node[x]
        # 負なら親ノードとみなして、そのインデックスを返す。
        if _val < 0: 
            return x
        # グループの親ノードを再帰的に検索。
        # さらに、グループの親ノードIDを子ノードに記録しておくことで
        # 経路縮小を実現。
        self.node[x] = self.find(_val)
        return self.node[x]

    def same(self, x, y):
        """
        xとyが属するグループが同じかチェック。
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        xが属するグループの総サイズ取得
        """
        return abs(self.node[self.find(x)])
 
    def __str__(self):
        return str(self.node)

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

uf = UnionFind(N)
friend = [0] * N
block = [[] for _ in range(N)]

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

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

for i in range(N):
    ans = uf.size(i) - friend[i] - 1
    for j in block[i]:
        if uf.same(i, j):
            ans -= 1
    print("{} ".format(ans), end="")
print("")

Submission status: Runtime Error

Solution code:
class UnionFind:
    """
    子ノードには自分の親ノードIDを記録。親ノードにはグループサイズの負値を記録。
    """

    def __init__(self, n):
        self.node = [-1] * n
    
    def unite(self, x, y):
        """
        xとyが属するグループを統合
        """
        # xとyの親ノードインデックスを取得
        _x, _y = self.find(x), self.find(y)
        # 一致していれば同じグループに属しているので処理終了。
        # Falseはなぞ。
        if _x == _y:
            return False
        # サイズが小さいグループを大きいグループに結合するので、
        # _y側の絶対値がかならず小さくなるように前処理。(_yを_xのグループへ統合)
        # 大きい方を小さい方へ結合してしまうとノードが深くなってしまうので、
        # 計算量を削減するためのテクニック。
        if abs(self.node[_x]) < abs(self.node[_y]):
             self.node[_x], self.node[_y] = self.node[_y], self.node[_x]
        # グループサイズ更新
        self.node[_x] += self.node[_y]
        # _yの親ノードを_xに更新
        self.node[_y] = _x
        return True

    def find(self, x):
        """
        xが属するグループの親ノードインデックスを検索。
        """
        _val = self.node[x]
        # 負なら親ノードとみなして、そのインデックスを返す。
        if _val < 0: 
            return x
        # グループの親ノードを再帰的に検索。
        # さらに、グループの親ノードIDを子ノードに記録しておくことで
        # 経路縮小を実現。
        self.node[x] = self.find(_val)
        return self.node[x]

    def same(self, x, y):
        """
        xとyが属するグループが同じかチェック。
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        xが属するグループの総サイズ取得
        """
        return abs(self.node[self.find(x)])
 
    def __str__(self):
        return str(self.node)

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

uf = UnionFind(N)
friend = [0] * N
block = [[] for _ in range(N)]

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

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


for i in range(N):
    ans = uf.size(i) - friend[i] - 1
    for j in block[i]:
        if uf.same(i, j):
            ans -= 1
    print("{} ".format(ans), end="")
print()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5)

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

F = [[] for _ in range(n+1)]
B = [[] for _ in range(n+1)]

for _ in range(m):
    x,y = map(int, input().split())
    F[x].append(y)
    F[y].append(x)

for _ in range(k):
    x,y = map(int, input().split())
    B[x].append(y)
    B[y].append(x)

belongs = [-1 for _ in range(n+1)]
group_ID = 0

def f_search(root, group_ID):
    if belongs[root] == -1:
        belongs[root] = group_ID
    for j in F[root]:
        if belongs[j] == -1:
            belongs[j] = group_ID
            f_search(j, group_ID)

for i in range(n+1):
    f_search(i, group_ID)
    group_ID += 1

cnt_members = [0 for _ in range(len(set(belongs)))]
for i in belongs[1:]:
    cnt_members[i] += 1

ans = [0 for _ in range(n+1)]
for i in range(1, n+1):
    tmp = 0
    for j in B[i]:
        if belongs[j] == belongs[i]:
            tmp += 1
    ans[i] = cnt_members[belongs[i]] - 1 - len(F[i]) - tmp

print(*ans[1:])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5)

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

F = [[] for _ in range(n+1)]
B = [[] for _ in range(n+1)]

for _ in range(m):
    x,y = map(int, input().split())
    F[x].append(y)
    F[y].append(x)

for _ in range(k):
    x,y = map(int, input().split())
    B[x].append(y)
    B[y].append(x)

belongs = [-1 for _ in range(n+1)]

def f_search(root, group_ID):
    for j in F[root]:
        if belongs[j] == -1:
            belongs[j] = group_ID
            f_search(j, group_ID)

group_ID = 0
for i in range(n+1):
    if belongs[i] == -1:
        belongs[i] = group_ID
        f_search(i, group_ID)
    group_ID += 1

cnt_members = [0 for _ in range(len(set(belongs)))]
for i in belongs[1:]:
    cnt_members[i] += 1

ans = [0 for _ in range(n+1)]
for i in range(1, n+1):
    tmp = 0
    for j in B[i]:
        if belongs[j] == belongs[i]:
            tmp += 1
    ans[i] = cnt_members[belongs[i]] - 1 - len(F[i]) - tmp

print(*ans[1:])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5)

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

F = [[] for _ in range(n+1)]
B = [[] for _ in range(n+1)]

for _ in range(m):
    x,y = map(int, input().split())
    F[x].append(y)
    F[y].append(x)

for _ in range(k):
    x,y = map(int, input().split())
    B[x].append(y)
    B[y].append(x)

belongs = [-1 for _ in range(n+1)]

def f_search(root, group_ID):
    for j in F[root]:
        if belongs[j] == -1:
            belongs[j] = group_ID
            f_search(j, group_ID)

group_ID = 0
for i in range(n+1):
    if belongs[i] == -1:
        belongs[i] = group_ID
        for j in F[i]:
            f_search(j, group_ID)
    group_ID += 1

cnt_members = [0 for _ in range(len(set(belongs)))]
for i in belongs[1:]:
    cnt_members[i] += 1

ans = [0 for _ in range(n+1)]
for i in range(1, n+1):
    tmp = 0
    for j in B[i]:
        if belongs[j] == belongs[i]:
            tmp += 1
    ans[i] = cnt_members[belongs[i]] - 1 - len(F[i]) - tmp

print(*ans[1:])

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

import sys
sys.setrecursionlimit(10**9)
n,m,k=[int(i) for i in input().split()]
frends_num=[0 for i in range(n)]
def make_frends(m,n):
    data=[1 for i in range(m)]

    row=[]
    col=[]
    for k in range(m):
        i,j=[int(l) for l in input().split()]
        new_i=min(i,j)-1
        new_j=max(i,j)-1
        row.append(new_i)
        col.append(new_j)
        frends_num[new_i]+=1
        frends_num[new_j]+=1
    frend_sparce_matrix=csr_matrix((data, (row, col)),shape=(n,n))
    return frend_sparce_matrix


frends=make_frends(m,n)
l,labels=connected_components(frends)
labels
labels=list(labels)

class Group:
    def __init__(self,labels):
        self.labels=labels
        self.group_num=[0 for i in range(l)]
        for i in labels:
            self.group_num[i]+=1
    def get_group_num(self,i):
        return self.group_num[self.labels[i]]

group=Group(labels)


def get_frend_num(i):
    return frends_num[i]


def make_block(k,n):
    block_num=[0 for i in range(n)]
    for p in range(k):
        i,j =[int(l)-1 for l in input().split()]
        new_i=min(i,j)
        new_j=max(i,j)
        if labels[new_i]==labels[new_j]:
            block_num[i]+=1
            block_num[j]+=1
    return block_num

block=make_block(k,n)

def get_block_num(i):
    return block[i]

ans=[]
for i in range(n):
    ans.append(str(group.get_group_num(i)-1-get_frend_num(i)-get_block_num(i)))
print(" ".join())