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:
friend_dic = {}
block_dic = {}

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

for i in range(N):
    friend_dic[i+1] = []
    block_dic[i+1] = [i+1]

for _ in range(M):
    a, b = map(int, input().split())
    friend_dic[a].append(b)
    friend_dic[b].append(a)

for _ in range(K):
    a, b = map(int, input().split())
    block_dic[a].append(b)
    block_dic[b].append(a)

def search_friends(n, friends):
    for my_friend in friend_dic[n]:
        if my_friend not in friends:
            friends.append(my_friend)
            search_friends(my_friend, friends)

result = []
for i in range(1, N+1):
    friends = []
    search_friends(i, friends)
    result.append(str(len(set(friends)-set(friend_dic[i])-set(block_dic[i]))))

print(" ".join(result))

Submission status: Runtime Error

Solution code:
import numpy as np
from queue import Queue
N,M,K=map(int, input().split())
F=np.zeros((N,N),dtype=int)
B=np.zeros((N,N),dtype=int)
for i in range(M):
  a,b=map(int, input().split())
  a-=1
  b-=1
  F[a,b]=1
  F[b,a]=1
for i in range(K):
  c,d=map(int, input().split())
  c-=1
  d-=1
  B[c,d]=1
  B[d,c]=1
  
def Adj(u):
  adj=[]
  for v in range(N):
    if F[u,v]==1 and v!=u:
    	adj.append(v)
  return adj    

def BFS():
  cands=[]
  for s in range(N):
    cand=[]
    visited=[s]
    #main関数でスタートを塗りつぶすのを忘れないように
    Q=Queue()
    Q.put(s)
    while not Q.empty():
      u=Q.get()
      if u!=s and B[s,u]==0 and F[s,u]==0:
        cand.append(u)
      for v in Adj(u):  
        if v not in visited:
          Q.put(v)
          visited.append(v)
    cands.append(str(len(cand)))
  print(' '.join(cands))
BFS()

Submission status: Runtime Error

Solution code:
import numpy as np
n,m,k,*abcd = map(int,open(0).read().split())
friends = np.identity(n,int)
block = np.ones((n,n),int)
ab = abcd[:2*m]
cd = abcd[2*m:]
a = np.array(ab[::2])-1
b = np.array(ab[1::2])-1
c = np.array(cd[::2])-1
d = np.array(cd[1::2])-1

if m>0:
    friends[a,b]=1
    friends[b,a]=1
if k>0:
    block[c,d]=0
    block[d,c]=0

friends_candi = friends.copy()
for i in range(int(np.log2(n))+1):
    friends_candi = (np.dot(friends_candi,friends)>0)
count = (friends_candi - friends) & block
print(*count.sum(axis=1))

Submission status: Runtime Error

Solution code:
class Person:
    def __init__(self, i):
        self.friends = []
        self.blocks = []
        self.index = i


def list_nets(persons, visited, current):
    visited.append(current)
    for p in persons[current].friends:
        if p not in visited:
            list_nets(persons, visited, p)


def main():
    N, M, K = map(int, input().split())
    persons = [Person(i) for i in range(N)]

    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        persons[a].friends.append(b)
        persons[b].friends.append(a)
    for i in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        persons[c].blocks.append(d)
        persons[d].blocks.append(c)

    result = []
    for p in persons:
        visited = list()
        list_nets(persons, visited, p.index)
        f = list(filter(lambda x: x not in p.blocks, visited))
        f = list(filter(lambda x: x not in p.friends, f))
        result.append(str(len(f) - 1))

    print(' '.join(result))


if __name__ == '__main__':
    import sys
    sys.exit(main())

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m, k = LI()
G1 = [set() for _ in range(n)]
G2 = [set() for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G1[a - 1].add(b - 1)
    G1[b - 1].add(a - 1)

for _ in range(k):
    a, b = LI()
    G1[a - 1].add(b - 1)
    G1[b - 1].add(a - 1)

flg = 0
li = 0
ri = 0
L = [(-INF, -INF)]
for i in range(n - 1):
    if flg == 0 and i + 1 in G1[i]:
        flg = 1
        li = i
        ri = i + 1
    elif flg:
        if i + 1 in G1[i]:
            ri += 1
        else:
            flg = 0
            L += [(li, ri)]
if flg:
    L += [(li, ri)]


ans = []
for i in range(n):
    l, r = L[bisect_right(L, (i, _)) - 1]
    if l <= i <= r:
        ret = r - l
        for v in G1[i]:
            if l <= v <= r:
                ret -= 1
        for v in G2[i]:
            if l <= v <= r:
                ret -= 1
        ans += [ret]
    else:
        ans += [0]

print(*ans, sep=' ')

Submission status: Runtime Error

Solution code:
# import sys
# input = sys.stdin.readline
n, m, k = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
B = [list(map(int,input().split())) for i in range(k)]
# print(A)
# print(B)
for i in range(m):
    for j in range(2):
        A[i][j] -= 1
for i in range(k):
    for j in range(2):
        B[i][j] -= 1
# print(A)
# print(B)

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 size(self, x):
        if self.parents[x] < 0:
            return -self.parents[x]
        else:
            self.parents[x] = self.size(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 n_cc(self):  # 連結成分の数
        A = [i for i in self.parents if i < 0]
        return len(A)

U = UnionFind(n)
for i in range(m):
    a = A[i][0]
    b = A[i][1]
    U.union(a, b)
C = [0] * n

for i in range(m):
    a = A[i][0]
    b = A[i][1]
    C[a] -= 1
    C[b] -= 1
for i in range(k):
    a = B[i][0]
    b = B[i][1]
    if U.find(a) == U.find(b):
        C[a] -= 1
        C[b] -= 1
# print(C)
ANS = []
for i in range(n):
    ANS.append(U.size(i) + C[i] - 1)
print(" ".join([str(i) for i in ANS]))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200000+10)

N, M, K=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(M)]
CD=[list(map(int, input().split())) for _ in range(K)]
if M==0:
    print("haha")
else:
    AB.sort(key=lambda x:(x[0], x[1]))
    if K!=0:
        CD.sort(key=lambda x:(x[0], x[1]))

    fr=[[] for _ in range(N)] # friends relation
    br=[[] for _ in range(N)] # block relation

    AB.sort(key=lambda x:(x[0], x[1]))
    CD.sort(key=lambda x:(x[0], x[1]))
    for A, B in AB:
        A-=1
        B-=1
        fr[A].append(B)
        fr[B].append(A)
    for C, D in CD:
        C-=1
        D-=1
        br[C].append(D)
        br[D].append(C)

    counts=[0 for _ in range(N)]
    visited=[False for _ in range(N)]

    def dfs(u, p=-1, nodes=[]):
        visited[u]=True
        for n in nodes:
            if n not in fr[u] and n not in br[u]:
                counts[u]+=1
                counts[n]+=1
        nodes.append(u)
        for v in fr[u]:
            if v==p:
                continue
            if visited[v]:
                continue
            dfs(v, p=u, nodes=nodes)

    for i in range(N):
        if not visited[i]:
            dfs(i, p=-1, nodes=[])

print(*counts)

Submission status: Runtime Error

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

friend = [[1]*N for i in range(N)]
block = [[1]*N for i in range(N)]

for i in range(M):
    friend[AB[i][0]][AB[i][1]] = 0
    friend[AB[i][1]][AB[i][0]] = 0
    friend[i][i] = 0

for i in range(K):
    block[CD[i][0]][CD[i][1]] = 0 
    block[CD[i][1]][CD[i][0]] = 0

ans = [0]*N
for i in range(N):
    for j in range(N):
        ans[i] += friend[i][j]*block[i][j]

Submission status: Runtime Error

Solution code:
import sys
# sys.setrecursionlimit(1000000)
input = sys.stdin.readline
# from bisect import *
from collections import *
# from heapq import *
# INF = 500000
mod = 10**9+7

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0] * n
        self.size = [1] * n

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

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

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

N, M, K = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    es[u].append(v)
    es[v].append(u)
uf = UnionFind(N)
g = [-1]*N
def dfs(v, num):
    g[v] = num
    for u in es[v]:
        if g[u] == -1:
            uf.unite(v, u)
            dfs(u, num)
num = 0
for v in range(N):
    if g[v] == -1:
        dfs(v, num)
        num += 1
ans = [uf.getsize(v)-len(es[v])-1 for v in range(N)]
for i in range(K):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    if uf.same(u, v):
        ans[u] -= 1
        ans[v] -= 1
print(*ans)

Submission status: Runtime Error

Solution code:
N, M,K = map(int, input().split())
L=[0]*N*N
ans=[-1]*N
for i in range(M):
  A, B = map(int, input().split())
  L[(A-1)*N+B-1]=1
  L[(B-1)*N+A-1]=1

for i in range(K):
  A, B = map(int, input().split())
  L[(A-1)*N+B-1]=-1
  L[(B-1)*N+A-1]=-1
for i in range(N):
  for j in range(N):
    if(L[i*N+j]==0):
      ans[i]+=1
print(' '.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import sys

class Node:
    def __init__(self, i):
        self.linked = list()
        self.id = i
        self.blocked = list()

line = sys.stdin.readline().strip()
n,m,k = map(int, line.split())
nodes = [] 
for i in range(n):
    nodes.append(Node(i))
for i in range(m):
    line = sys.stdin.readline().strip()
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    nodes[a].linked.append(b)
    nodes[b].linked.append(a)

for i in range(k):
    line = sys.stdin.readline().strip()
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    nodes[a].blocked.append(b)
    nodes[b].blocked.append(a)

start = 0
res = [-1] * n
while True:
    visited = []
    def deep_first(node):
        for one in node.linked:
            if one not in visited:
                visited.append(one)
                #print(visited)
                deep_first(nodes[one])
    deep_first(nodes[start])           
    for one in visited:
        res[one] = 0
        for two in visited:
            if one != two:
                if two not in nodes[one].blocked and two not in nodes[one].linked:
                    res[one] += 1
    start = -1
    for i in range(1, n):
        if res[i] < 0:
            start = i
    if start == -1:
        break

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

Submission status: Runtime Error

Solution code:

#####

# import numpy as np
# from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128
from collections import defaultdict

#####

def getIntList(inp):
	return [int(_) for _ in inp]
	

from sys import stdin

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def st(x,y):
	return tuple(sorted([x,y]))

def main(inputs):
	n=int(inputs[0][0])
	m=int(inputs[0][1])
	k=int(inputs[0][2])

	fr=set()
	frSingle=defaultdict(set)
	for i in range(m):
		a=int(inputs[i+1][0])
		b=int(inputs[i+1][1])
		fr.add(st(a,b))
		frSingle[a].add(b)
		frSingle[b].add(a)
		
	bl=defaultdict(set)
	for i in range(k):
		a=int(inputs[i+1+m][0])
		b=int(inputs[i+1+m][1])
		bl[a].add(b)
		bl[b].add(a)
	
# 	print(fr)
# 	print(bl)
# 	print()
	
	frAll=defaultdict(set)
	for fri in fr:
		i0,i1=fri
		aall=set()
		aall.add(i0)
		aall.add(i1)
		aall.update(frAll[i0])
		aall.update(frAll[i1])
		for i in aall:
			frAll[i].update(aall-bl[i])
	
# 	print()
	for i0 in range(1,n+1):
		i1s=frAll[i0]
		i1s.remove(i0)
		i1s=i1s-frSingle[i0]
		i1s=i1s-bl[i0]
# 		print(i0,i1s)
		num=len(i1s)
		print(num, end="")
		if i0<n: print(" ", end="")
	
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
N,M=map(int,input().split())

l=[]
for _ in range(M):
   s,t=map(int,input().split())
   l.append([s,t])

for i in range(10**(N-1) if N!=1 else 0,10**N):
    temp=list(str(i))
    judge=True
    for s,t in l:
        if temp[s-1]!=str(t):
            judge=False
    if judge:
        print(i)
        exit()
        
print(-1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys
import math
import itertools

def main():
    n, m, k = map(int, sys.stdin.readline().split())
    fs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
    bs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(k)]

    g = [[] for _ in range(n)]
    for u, v in fs:
        g[u - 1].append(v - 1)
        g[v - 1].append(u - 1)
    for u in range(n):
        g[u] = set(g[u])

    bg = [[] for _ in range(n)]
    for u, v in bs:
        bg[u - 1].append(v - 1)
        bg[v - 1].append(u - 1)
    for u in range(n):
        bg[u] = set(bg[u])

    visited = [False] * n
    def get_component(g, root):
        cc = []
        def go(u):
            visited[u] = True
            cc.append(u)
            for v in g[u]:
                if not visited[v]:
                    go(v)
        go(root)
        return set(cc)

    ans = [0 for _ in range(n)]
    for u in range(n):
        if not visited[u]:
            cc = get_component(g, u)
            for v in cc:
                ans[v] = len(cc - g[v] - bg[v] - set([v]))

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

#####

import numpy as np
from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128

#####

def getIntList(inp):
	return [int(_) for _ in inp]
	

from sys import stdin

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def st(x,y):
	return tuple(sorted([x,y]))

def main(inputs):
	n=int(inputs[0][0])
	m=int(inputs[0][1])
	k=int(inputs[0][2])

	fr=set()
	for i in range(m):
		a=int(inputs[i+1][0])
		b=int(inputs[i+1][1])
		fr.add(st(a,b))
		
	bl={}
	for i in range(1,n+1):
		bl[i]=set()
	for i in range(k):
		a=int(inputs[i+1+m][0])
		b=int(inputs[i+1+m][1])
		bl[a].add(b)
		bl[b].add(a)
	
# 	print(fr)
# 	print(bl)
# 	print()
	
	frAll={}
	for i in range(1,n+1):
		frAll[i]=set()
	
	for fri in fr:
		i0,i1=fri
		aall=set()
		aall.add(i0)
		aall.add(i1)
		aall.update(frAll[i0])
		aall.update(frAll[i1])
		for i in aall:
			frAll[i].update(aall-bl[i])
	
# 	print()
	for i0 in range(1,n+1):
		i1s=frAll[i0]
		i1s.remove(i0)
# 		print(i0,i1s)
		num=0
		for i1 in i1s:
			p=st(i0,i1)
			if (p not in fr) and (i1 not in bl[i0]) and (i0 not in bl[i1]):
				num+=1
		print(num, end="")
		if i0<n: print(" ", end="")
	
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().rstrip().split())
if N == 0:
    print(-1)
else:
    d = {}
    success_flg = True
    for _ in range(M):
        s, c = map(int, input().rstrip().split())
        if s == 0:
            success_flg = False
            break
        if s > N:
            success_flg = False
            break
        elif s in d.keys() and c != d[s]:
            success_flg = False
            break
        else:
            d[s] = c
    if success_flg:
        tmp_result = '0' * N
        success_flg2 = True
        for s, c in d.items():
            if s == 1 and c == 0:
                success_flg2 = False
                print(-1)
                break
            tmp_result = tmp_result[:s - 1] + str(c) + tmp_result[s:]
        if success_flg2:
            if tmp_result[0] == '0':
                tmp_result = str(1) + tmp_result[1:]
            print(int(tmp_result))
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]
ans = [0] * N

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

def dfs(start, i):
	global visited
	global friend
	global block
	global ans
	visited[i] = 1
	for adj in friend[i]:
		if visited[adj]: continue
		if not adj in friend[start] and not adj in block[start]:
			ans[start] += 1
		dfs(start, adj)
		
	
for i in range(N):
	visited = [0] * N
	dfs(i, i)
	
print(*ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.tree = range(n)
        # self.rank = [0] * n
    
    def root(self, n):
        if self.tree[n] == n:
            return n
        self.tree[n] = self.root(self.tree[n])
        return self.tree[n]

    def merge(self, a, b):
        aa = self.root(a)
        bb = self.root(b)
        self.tree[aa] = bb

    def clusters(self):
        c = {}
        for i in xrange(self.n):
            j = self.root(i)
            c.setdefault(j, set()).add(i)
        return c.values()


def main():
    n, m, k = map(int, raw_input().split())
    uf = UnionFind(n)
    ff = {}
    block = {}
    for _ in xrange(m):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        ff.setdefault(a, set()).add(b)
        ff.setdefault(b, set()).add(a)
        uf.merge(a, b)
    for _ in xrange(k):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        block.setdefault(a, set()).add(b)
        block.setdefault(b, set()).add(a)

    clusters = uf.clusters()
    ans = [0] * n
    for cluster in clusters:
        for i in cluster:
            size = len(cluster - {i} - block.get(i, set()) - ff.get(i, set()))
            ans[i] = size
    print ' '.join(map(str, ans))

main()

Submission status: Runtime Error

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

N, M, K = map(int, input().split())
friend_link = np.zeros(shape=(N, N), dtype=np.int8)
block = np.zeros(shape=(N, N), dtype=np.int8)

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

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

distance = shortest_path(friend_link)
friend_candidate = np.where((1e7 > distance) & (distance > 1), 1, 0)
friend_candidate *= 1 - block
friend_candidate_num = friend_candidate.sum(axis=1).astype(str).tolist()
print(" ".join(friend_candidate_num))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, src, dest, w=1):
        self.E[src].append((dest, w))
        self.E[dest].append((src, w))  # 無向グラフ


class UnionFind(object):
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


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

    # ブロック関係
    block = Graph(N)
    for c, d in zip(C, D):
        block.add_edge(c-1, d-1)

    # 友好関係
    friendUF = UnionFind(N)
    degree = [0]*N
    for a, b in zip(A, B):
        friendUF.unite(a-1, b-1)
        degree[a-1] += 1
        degree[b-1] += 1

    # 友好的に連結している数を調べる
    group = defaultdict(int)
    for i in range(N):
        group[friendUF.root(i)] += 1

    ans = []
    for i in range(N):
        # iの連結している個数 - 次数 - 1 （自身を除く）
        # print(" -- {} --".format(i))
        # print(group[friendUF.root(i)], degree[i])
        ans.append(group[friendUF.root(i)] - degree[i] - 1)
        # ブロックを考慮する
        for dest, _ in block.E[i]:
            if friendUF.same(dest, i):
                ans[-1] -= 1
    print(*ans, sep=" ")
    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:
import sys
input = sys.stdin.readline
n, m, k = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
B = [list(map(int,input().split())) for i in range(k)]
# print(A)
# print(B)
for i in range(m):
    for j in range(2):
        A[i][j] -= 1
for i in range(k):
    for j in range(2):
        B[i][j] -= 1
# print(A)
# print(B)

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 size(self, x):
        if self.parents[x] < 0:
            return -self.parents[x]
        else:
            self.parents[x] = self.size(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 n_cc(self):  # 連結成分の数
        A = [i for i in self.parents if i < 0]
        return len(A)

U = UnionFind(n)
for i in range(m):
    a = A[i][0]
    b = A[i][1]
    U.union(a, b)
C = [0] * n

for i in range(m):
    a = A[i][0]
    b = A[i][1]
    C[a] -= 1
    C[b] -= 1
for i in range(k):
    a = B[i][0]
    b = B[i][1]
    if U.find(a) == U.find(b):
        C[a] -= 1
        C[b] -= 1
# print(C)
ANS = []
for i in range(n):
    ANS.append(U.size(i) + C[i] - 1)
print(" ".join([str(i) for i in ANS]))

Submission status: Runtime Error

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

class UnionFind:
	def __init__(self, n):
		self.groups = [g for g in range(n)]

	def get_root(self, i):
		parent = self.groups[i]
		if parent == i:
			return parent
		else:
			root = self.get_root(parent)
			self.groups[i] = root
			return root
	
	def set_root(self, i, root):
		parent = self.groups[i]
		self.groups[i] = root
		if parent == i:
			return
		else:
			self.set_root(parent, root)
	
	def combine(self, i1, i2):
		self.set_root(i2, self.get_root(i1))
	
	def in_same_group(self, i1, i2):
		return self.get_root(i1) == self.get_root(i2)
	
	def counts(self):
		table = [None] * len(self.groups)
		for i in range(len(self.groups)):
			g = self.get_root(i)
			if table[g] != None:
				table[g] += 1
			else:
				table[g] = 1
		
		ret = [0] * len(self.groups)
		
		for i in range(len(self.groups)):
			ret[i] = table[self.get_root(i)]
		
		return ret
	
	def to_list(self):
		table = self.to_dic()
		return [table[g] for g in table]


groups = UnionFind(N)
minus_list = [0] * N

for _ in range(M):
	a, b = map(lambda x: int(x) - 1, input().split())
	groups.combine(a, b)
	minus_list[a] -= 1
	minus_list[b] -= 1

for _ in range(K):
	c, d = map(lambda x: int(x) - 1, input().split())
	if groups.in_same_group(c, d):
		minus_list[c] -= 1
		minus_list[d] -= 1

counts = groups.counts()

print(" ".join((str(counts[i] + minus_list[i] - 1) for i in range(N))))

Submission status: Runtime Error

Solution code:
import numpy as np
n, m, k = map(int, input().split())
relation = np.zeros((n + 1, n + 1), dtype=np.int)
rinsetu = {i:[] for i in range(1,n+1)}
for i in range(n):
  relation[i+1,i+1] = 1
for i in range(m):
    a, b = map(int, input().split())
    relation[a, b] = 1
    relation[b, a] = 1
    rinsetu[a].append(b)
    rinsetu[b].append(a)
for i in range(k):
    a, b = map(int, input().split())
    relation[a, b] = 1
    relation[b, a] = 1

def dfs(v):
    kouho.add(v)
    for nxt in rinsetu[v]:
        if nxt in kouho:
            continue
        dfs(nxt)

for i in range(1,n+1):
    kouho = set()
    s = 0
    dfs(i)
    for k in kouho:
      if(relation[i,k] == 0):
        s += 1
    print(s,end=' ')

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra

n, m, k = map(int, input().split())
graph = [[10 ** 9 + 7 for i in range(n)] for i in range(n)]

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

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

cost = dijkstra(graph)
ans2 = []
for i in range(n):
    ans = 0
    for j in range(n):
        if i == j:
            continue
        if cost[i][j] < 10 ** 9 + 7 and cost[i][j] != 1:
            if j not in block[i]:
                ans += 1
    ans2.append(str(ans))

print(' '.join(ans2))