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:
#!/usr/bin/env python3
import sys
from collections import deque

class UnionFind:
    def __init__(self, num):
        self.par = list(range(1,num+1))
        self.size = [1]*num
    
    def root(self, n):
        if self.par[n-1] == n: return n
        self.par[n-1] = self.root(self.par[n-1])
        return self.par[n-1]

    def unite(self, a, b):
        a=self.root(a)
        b=self.root(b)
        if a!=b:
            self.par[b-1]=a
            self.size[a-1] += self.size[b-1]
        return
    
    def get_size(self, n):
        return self.size[self.root(n)-1]


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):

    fris = [0]*N
    blos = [0]*N

    union = UnionFind(N)
    for ai, bi in zip(A, B):
        union.unite(ai,bi)
        fris[ai-1]+=1
        fris[bi-1]+=1
    
    for ci, di in zip(C, D):
        if union.root(ci) == union.root(di):
            blos[ci-1]+=1
            blos[di-1]+=1
    
    ans = [0]*N
    for i in range(1,N+1):
        s = union.get_size(i)
        s -= fris[i-1]
        s -= blos[i-1]
        s -= 1
        ans[i-1] = s

    print(*ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  # type: "List[int]"
    D = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

class UnionFind:
    def __init__(self, num):
        self.par = list(range(1,num+1))
        self.size = [1]*num
    
    def root(self, n):
        if self.par[n-1] == n: return n
        self.par[n-1] = self.root(self.par[n-1])
        return self.par[n-1]

    def unite(self, a, b):
        a=self.root(a)
        b=self.root(b)
        if a!=b:
            self.par[b-1]=a
            self.size[a-1] += self.size[b-1]
        return
    
    def get_size(self, n):
        return self.size[self.root(n)-1]


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):

    union = UnionFind(N)
    for ai, bi in zip(A, B):
        union.unite(ai,bi)
    # [union.root(x) for x in range(N)]
    # print(union.par)
    # print(union.size)
    
    fris = [0]*N
    blos = [0]*N

    for ai, bi in zip(A, B):
        fris[ai-1]+=1
        fris[bi-1]+=1

    for ci, di in zip(C, D):
        if union.root(ci) == union.root(di):
            blos[ci-1]+=1
            blos[di-1]+=1
    
    ans = [0]*N
    for i in range(1,N+1):
        s = union.get_size(i)
        s -= fris[i-1]
        s -= blos[i-1]
        s -= 1
        ans[i-1] = s

    print(*ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  # type: "List[int]"
    D = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

color = [-1]*N
V_block = []

#各連結成分の次元テーブル
dic = {}

dim = 0
#深さ優先探索
def dfs(node, c):
    global dim

    if color[node]!=-1:
        return
    color[node] = c
    dim = dim + 1
    for next_node in V[node]:
        dfs(next_node, c)
    return

for _ in range(N):
    V.append(set())
    V_block.append(set())
for _ in range(M):
    a,b = map(int, input().split())
    V[a-1].add(b-1)
    V[b-1].add(a-1)

#一旦捨てる
for _ in range(K):
    c,d = map(int, input().split())
    V_block[c-1].add(d-1)
    V_block[d-1].add(c-1)
    
c = 0
for node in range(N):
    if color[node]!=-1:
        continue
    dim = 0
    dfs(node, c)
    dic[c] = dim

    c = c + 1

ans_list = []
for node in range(N):
    num = 0
    for block_node in V_block[node]:
        if color[node]==color[block_node]:
            num = num + 1
    ans_list.append(dic[color[node]]-num-len(V[node])-1)

print(*ans_list)

Submission status: Runtime Error

Solution code:
# 2020-05-22
from collections import deque


def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    networks = {}  # The dict of networks as sets. Keys are leaders.
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        networks[person] = set()
        stack = deque([person])
        while stack:
            new = stack.pop()
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack.append(adj)
                networks[person].add(adj)
                visited[adj] = True
                net_leaders[adj] = person

    answers = []
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        bb = sum(block in net for block in blocks[person])
        answers.append(ans - bb)

    print(*answers)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# 2020-05-22
from collections import deque


def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    networks = {}  # The dict of networks as sets. Keys are leaders.
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        networks[person] = set()
        stack = deque([person])
        while stack:
            new = stack.pop()
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack.append(adj)
                networks[person].add(adj)
                visited[adj] = True
                net_leaders[adj] = person

    answers = []
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        bb = len(net & blocks[person])
        answers.append(ans - bb)

    print(*answers)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

F=[set() for i in range(n)]
B=[set() for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	F[a-1].add(b-1)
	F[b-1].add(a-1)
for i in range(k):
	c,d=map(int,input().split())
	B[c-1].add(d-1)
	B[d-1].add(c-1)
	
T=[[] for i in range(n)]
D=[0]*n
for i in range(n):
	if D[i]==1:
	    continue
	que=deque([])
	que.append(i)
	T[i].append(i)
	while que:
	    p=que.popleft()
	    for np in F[p]:
	        if D[np]!=1:
	            que.append(np)
	            T[i].append(np)
	            D[np]=1

S=[[] for i in range(n)]
for i in range(n):
    if T[i]:
        for t in T[i]:
            S[t]=set(T[i][:])
            S[t].remove(t)
		
R=[0]*n
for i in range(n):
	R[i]=len(S[i])-len(F[i])-len(set(S[i])&set(B[i]))
print(*R)

Submission status: Runtime Error

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

F=[set() for i in range(n)]
B=[set() for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	F[a-1].add(b-1)
	F[b-1].add(a-1)
for i in range(k):
	c,d=map(int,input().split())
	B[c-1].add(d-1)
	B[d-1].add(c-1)
	
T=[[] for i in range(n)]
D=[0]*n
for i in range(n):
	if D[i]==1:
	    continue
	stack=deque([])
	que.append(i)
	T[i].append(i)
	while que:
	    p=que.popleft()
	    for np in F[p]:
	        if D[np]!=1:
	            que.append(np)
	            T[i].append(np)
	            D[np]=1

S=[[] for i in range(n)]
for i in range(n):
    if T[i]:
        for t in T[i]:
            S[t]=set(T[i][:])
            S[t].remove(t)
		
R=[0]*n
for i in range(n):
	R[i]=len(S[i])-len(F[i])-len(set(S[i])&set(B[i]))
print(*R)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
n,m,k=map(int,input().split())

L=[[] for i in range(n)]
U=[[] for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	L[a-1].append(b-1)
	L[b-1].append(a-1)
for i in range(k):
	c,d=map(int,input().split())
	U[c-1].append(d-1)
	U[d-1].append(c-1)
	
S=[[] for i in range(n)]
D=[0]*n

def dfs(n):
	D[n]=1
	T.append(n)
	for np in L[n]:
		if D[np]!=1:
			dfs(np)
			
for i in range(n):
	if D[i]!=1:
		T=[]
		dfs(i)
	for t in T:
		S[t]=T[:]
		S[t].remove(t)
		
R=[0]*n
for i in range(n):
	R[i]=len(S[i])-len(L[i])-len(set(S[i])&set(U[i]))
print(*R)

Submission status: Runtime Error

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

L=[[] for i in range(n)]
U=[[] for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	L[a-1].append(b-1)
	L[b-1].append(a-1)
for i in range(k):
	c,d=map(int,input().split())
	U[c-1].append(d-1)
	U[d-1].append(c-1)
	
S=[[] for i in range(n)]
D=[0]*n

def dfs(n):
	D[n]=1
	T.append(n)
	for np in L[n]:
		if D[np]!=1:
			dfs(np)
			
for i in range(n):
	if D[i]!=1:
		T=[]
		dfs(i)
	for t in T:
		S[t]=T[:]
		S[t].remove(t)
		
R=[0]*n
for i in range(n):
	R[i]=len(S[i])-len(L[i])-len(set(S[i])&set(U[i]))
print(*R)

Submission status: Runtime Error

Solution code:
from collections import deque

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

cnt=[0]*n
l=deque()
x=1
dic={}
for i in range(n):
    if cnt[i]==0:
        l.append(i)
    while l:
        now=l.popleft()
        for to in fre[now]:
            if cnt[to]==0:
                cnt[to]=x
                if x in dic:
                    dic[x]+=1
                else:
                    dic[x]=1
                l.append(to)
    x+=1

for i in range(n):
    k=len(fre[i])
    for b in blo[i]:
        if cnt[b]==cnt[i]:
            k+=1
    if dic=={}:
        print(0)
    else:
        print(dic[cnt[i]]-k-1)

Submission status: Runtime Error

Solution code:
from collections import deque

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

cnt=[0]*n
l=deque()
x=1
dic={}
for i in range(n):
    if cnt[i]==0:
        l.append(i)
    while l:
        now=l.popleft()
        for to in fre[now]:
            if cnt[to]==0:
                cnt[to]=x
                if x in dic:
                    dic[x]+=1
                else:
                    dic[x]=1
                l.append(to)
    x+=1

for i in range(n):
    k=len(fre[i])
    for b in blo[i]:
        if cnt[b]==cnt[i]:
            k+=1
    print(dic[cnt[i]]-k-1)

Submission status: Runtime Error

Solution code:
n,m,k = map(int,input().split(" "))
groups = [[] for i in range(1)]
friends = [[] for i in range(n)]
potentials = [[] for i in range(n)]

#グループリスト作成
for i in range(m):
  a,b = map(int, input().split(" "))
  friends[a-1].append(b)
  friends[b-1].append(a)
  a_judge = [(a in x) for x in groups] 
  b_judge = [(b in x) for x in groups] 
  if any(a_judge) and any(b_judge) and a_judge.index(True)!=b_judge.index(True):
    new_list = groups[a_judge.index(True)] + groups[b_judge.index(True)]
    groups.pop(b_judge.index(True))
    groups.pop(a_judge.index(True))
    groups.append(new_list)
  elif any(a_judge) and not any(b_judge):
    groups[a_judge.index(True)].append(b)
  elif not any(a_judge) and any(b_judge):
    groups[b_judge.index(True)].append(a)
  elif not any(a_judge) and not any(b_judge):
    groups.append([a,b])
 
#グループリスト展開、ポテンシャルリスト作成
for i in range(n):
  i_judge = [(i+1 in x) for x in groups] 
  potentials[i].extend(groups[i_judge.index(True)])
  potentials[i].remove(i+1)

#ブロック関係排除
for i in range(k):
  c,d = map(int, input().split(" "))
  if d in potentials[c-1]:
    potentials[c-1].remove(d)
  if c in potentials[d-1]:
    potentials[d-1].remove(c)

for i in range(n):
  for j in friends[i]:
    if j in potentials[i]:
      potentials[i].remove(j)

count=[str(len(l)) for l in potentials]
      
count=" ".join(count)
print(count)

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
sys.setrecursionlimit(20000)
N,M,K=list(map(int,input().split()))
friend_list=[[] for _ in range(N+1)]
block_list=[[] for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color :
            friend_tansaku(i,friend)





for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].append(b)
   friend_list[b].append(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].append(b)
    block_list[b].append(a)
for i in range(1,N+1):
    color =set()
    friend_tansaku(i,i)
    for k in block_list[i]:
        color.add(k)
    count=len(color)-(len(friend_list[i])+len(block_list[i]))-1
    if i==N:print(count)
    else:print(count,end=" ")

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
sys.setrecursionlimit(20000)
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
                candidate.add(friend)
                count[0]+=1
            friend_tansaku(i,i)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
sys.setrecursionlimit(20000)
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
                candidate.add(friend)
                count[0]+=1
            friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
sys.setrecursionlimit(2000)
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            # if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
            #     candidate.add(friend)
            #     count[0]+=1
            friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

Submission status: Runtime Error

Solution code:
from sys import stdin
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        # if friend not in color:
            # if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
            #     candidate.add(friend)
            #     count[0]+=1
            friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

Submission status: Runtime Error

Solution code:
from sys import stdin
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            # if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
            #     candidate.add(friend)
            #     count[0]+=1
            friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

Submission status: Runtime Error

Solution code:
from sys import stdin
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
                # candidate.add(friend)
                count[0]+=1
            friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

Submission status: Runtime Error

Solution code:
from sys import stdin
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            # if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
            candidate.add(friend)
            count[0]+=1
            friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

Submission status: Runtime Error

Solution code:
from sys import stdin
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
                candidate.add(friend)
                count[0]+=1
            friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque
N,M,K=list(map(int,input().split()))
friend_list=[[] for i in range(N+1)]
block_list=[[] for i in range(N+1)]
def friend_tansaku(i,j):
    color[j]="gray"
    for friend in friend_list[j]:
        if color[friend]=="white":
            if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
                candidate.append(friend)
            friend_tansaku(i,friend)
    color[j]="black"




for i in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].append(b)
   friend_list[b].append(a)
for i in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].append(b)
    block_list[b].append(a)
for i in range(1,N+1):
    color = ["white"] * (N + 1)
    candidate=[]
    friend_tansaku(i,i)
    if i==N:print(len(candidate))
    else:print(len(candidate),end=" ")

Submission status: Runtime Error

Solution code:
def dfs(GF,group,gn,i):
    size = 1
    group[i]=gn
    for node in GF[i]:
        if group[node]==-1:
            group[node]=gn
            size+=dfs(GF,group,gn,node)
    return size

def main():
    from sys import stdin
    n,m,k = map(int,stdin.readline().rstrip().split())
    F=[]
    for _ in range(m):
        F.append(list(map(int,stdin.readline().rstrip().split())))
    GF = [[] for _ in range(n+1)]
    for a,b in F:
        GF[a].append(b)
        GF[b].append(a)
    
    B=[]
    for _ in range(k):
        B.append(list(map(int,stdin.readline().rstrip().split())))
    GB = [[] for _ in range(n+1)]
    for a,b in B:
        GB[a].append(b)
        GB[b].append(a)    

    U = []
    group= [-1]*(n+1)
    gn = 0

    for i in range(1,n+1):
        if group[i] == -1:
            sz = dfs(GF,group,gn,i)
            gn+=1
            U.append(sz)
    
    for i in range(1,n+1):
        g = group[i]
        ans = U[g]-1-len(GF[i])

        for b in GB[i]:
            if group[b]==g:
                ans-=1
        print(ans,end=" ")
main()

Submission status: Runtime Error

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if 0 > self.parents[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.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    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 0 > x]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M, K = MAP()
friends = [[] for _ in range(M)]
tree = UnionFind(N)

for _ in range(M):
	A, B = MAP()
	friends[A-1].append(B-1)
	friends[B-1].append(A-1)
	tree.union(A-1, B-1)

blocks = [[] for _ in range(N)]

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

for i in range(N):
	block_cnt = 0
	for j in blocks[i]:
		if tree.same(i, j):
			block_cnt += 1

	print(tree.size(i)-1-len(friends[i])-block_cnt, end = " ")
print()

"""
print("friends")
print(friends)

print("blocks")
print(blocks)

i = 1
print("i={}".format(i))
print("tree.size(i)={}".format(tree.size(i)))
print("tree.find(i))={}".format(tree.find(i)))
print("tree.members(i)={}".format(tree.members(i)))
print("tree.roots={}".format(tree.roots()))
print("tree.group_count={}".format(tree.group_count()))
print("tree.all_group_members={}".format(tree.all_group_members()))
"""

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000)

def DFS(i):
    if i not in done:
        done.add(i)
        circle.add(i)
        for f in F[i]:
            DFS(f)
    else:
        return

N,M,K=map(int,input().split())
F=[[] for _ in range(N)]
B=[[] for _ in range(N)]

for f in range(M):
    f1,f2=map(int,input().split())
    F[f1-1].append(f2-1)
    F[f2-1].append(f1-1)
for b in range(K):
    b1,b2=map(int,input().split())
    B[b1-1].append(b2-1)
    B[b2-1].append(b1-1)

Group=[]
circle=set()
done=set()
for i in range(N):
    if i not in done:
        DFS(i)
        Group.append(circle)
        circle=set()

ans=[-1 for _ in range(N)]
for i in range(N):
    for j in range(len(Group)):
        if i in Group[j]:
            ans[i]+=len(Group[j])
            break
    for fr in F[i]:
        if fr in Group[j]:
            ans[i]-=1
    for bl in B[i]:
        if bl in Group[j]:
            ans[i]-=1

print(*ans)

Submission status: Runtime Error

Solution code:
def DFS(i):
    if i not in done:
        done.add(i)
        circle.add(i)
        for f in F[i]:
            DFS(f)
    else:
        return

N,M,K=map(int,input().split())
F=[[] for _ in range(N)]
B=[[] for _ in range(N)]

for f in range(M):
    f1,f2=map(int,input().split())
    F[f1-1].append(f2-1)
    F[f2-1].append(f1-1)
for b in range(K):
    b1,b2=map(int,input().split())
    B[b1-1].append(b2-1)
    B[b2-1].append(b1-1)

Group=[]
circle=set()
done=set()
for i in range(N):
    if i not in done:
        DFS(i)
        Group.append(circle)
        circle=set()

ans=[-1 for _ in range(N)]
for i in range(N):
    for j in range(len(Group)):
        if i in Group[j]:
            ans[i]+=len(Group[j])
            break
    for fr in F[i]:
        if fr in Group[j]:
            ans[i]-=1
    for bl in B[i]:
        if bl in Group[j]:
            ans[i]-=1

print(*ans)