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:
# input
N, M, K = map(int, input().split())

Frends = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a < b:
        Frends[a].append(b)
    else:
        Frends[b].append(a)

Blocked = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if c < d:
        Blocked[c].append(d)
    else:
        Blocked[d].append(c)

# process
# 友人グループを作成
fg = []
for i in range (N):
    fs = Frends[i]
    for f in fs:
        t = -1
        for j in range(len(fg)):
            g = fg[j]
            if i in g and f in g:
                if t < 0:
                    t = j              
                else:
                    fg[t] = fg[t] | g
                    fg.remove(g)
            elif not (i in g or f in g):
                continue
            else:
                if t < 0:
                    if i in g:
                        g.add(f)
                    else:
                        g.add(i)

                    t = j
                else:
                    fg[t] = fg[t] | g
                    fg.remove(g)

        if t < 0:
            fg.append(set([i, f]))

#print(fg)

# 友人候補を抽出
cand = []
for i in range(N):
    for g in fg:
        if i in g:
            for f in g:
                if i < f and not f in Frends[i] and not f in Blocked[i]:
                    cand.append((i, f,))

#print(cand)

# 友人候補をカウント
ans = [0 for _ in range(N)]
for c in cand:
    a, b = c
    ans[a] += 1
    ans[b] += 1

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

Submission status: Runtime Error

Solution code:
import numpy as np
import math as m

def main(**kwargs):
    friends = {}
    blocks = {}

    for i in range(1, n + 1):
        friends[i] = []
        blocks[i] = []

    for i in range(m):
        friends[A[i]].append(B[i])
        friends[B[i]].append(A[i])

    for i in range(k):
        blocks[C[i]].append(D[i])
        blocks[D[i]].append(C[i])

    candidates = {}

    for i in range(1, n + 1):
        candidates[i] = DFS(friends, i, [])
        candidates[i].remove(i)

        for j in friends[i]:
            if j in candidates[i]:
                candidates[i].remove(j)

        for j in blocks[i]:
            if j in candidates[i]:
                candidates[i].remove(j)

    res = " ".join([str(len(r)) for r in candidates.values()])
    return res

def DFS(G, s, vs):
    vs.append(s)

    for u in G[s]:
        if not u in vs:
            DFS(G, u, vs)

    return vs

if __name__ == "__main__":
    cin = np.array(input().split(" ")).astype("int")
    n, m, k, *_ = cin

    A = np.zeros(m, dtype="int")
    B = np.zeros(m, dtype="int")
    C = np.zeros(k, dtype="int")
    D = np.zeros(k, dtype="int")

    for i in range(m):
        cin = np.array(input().split(" ")).astype("int")
        A[i], B[i] = np.array(cin)

    for i in range(k):
        cin = np.array(input().split(" ")).astype("int")
        C[i], D[i] = np.array(cin)
    
    cout = main(n=n, m=m, k=k, A=A, B=B, C=C, D=D)
    print(cout)

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
friends=[set() for i in range(N)]
block=[set() for i in range(N)]
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1]*n
    self.group=[]
    self.groupnum=0
  
  def root(self,x):
    if self.parents[x]<0:
      return x
    else:
      return self.root(self.parents[x])
  def unite(self,x,y):
    xp=self.root(x)
    yp=self.root(y)
    if xp==yp:
      return 'a'
    if self.parents[xp] > self.parents[yp]:
      xp,yp=yp,xp
    if self.parents[xp]==-1:
#      print(self.parents,self.group)
#      print(self.parents[xp],self.parents[yp])
      self.parents[xp]=-2-self.groupnum
      self.groupnum+=1
      self.parents[yp]=xp
      self.group.append(set([x,y]))
#      print(x,y,xp,yp,self.parents)
      return 'c'
    else:
      if self.parents[yp]==-1:
        self.group[-self.parents[xp]-2].add(yp)
#        print('a!')
      else:
        self.group[-self.parents[xp]-2]=self.group[-self.parents[xp]-2].union(self.group[-self.parents[yp]-2])
      self.parents[yp]=xp
#      print('!',self.parents,self.group)
      return 'd'
    return
  def same(self,x,y):
    return self.root(x)==self.root(y)
  def members(self, x):
    xp = self.root(x)
    return self.group[-self.parents[xp]-2]
Tree=UnionFind(N)
for i in range(M):
  a,b=map(int,input().split())
  Tree.unite(a-1,b-1)
  friends[a-1].add(b-1)
  friends[b-1].add(a-1)
for i in range(K):
  c,d=map(int,input().split())
  block[c-1].add(d-1)
  block[d-1].add(c-1)
print(*[len(Tree.members(i)-friends[i]-block[i])-1 for i in range(N)])

Submission status: Runtime Error

Solution code:
    class union_find():
        def __init__(self, n):
            self.par = [i for i in range(n + 1)]
            self.rank = [1 for i in range(n + 1)]
            self.size = [1 for i in range(n + 1)]
     
        def find(self, c):
            if self.par[c] == c:
                return c
     
            ret = self.find(self.par[c])
            self.par[c] = ret
            return ret
     
        def union(self, x, y):
     
            xr = self.find(x)
            yr = self.find(y)
            if xr == yr:
                return
     
            if self.rank[yr] > self.rank[xr]:
                self.par[xr] = yr
            else:
                self.par[yr] = xr
                self.size[xr] += self.size[yr]
                if self.rank[xr] == self.rank[yr]:
                    self.rank[xr] += 1
     
        def mass_size(self):
            return [i == v for i, v in enumerate(self.par)].count(True) - 1
        
        def size_belong(self, i):
        	return self.size[self.find(i)]
     
        def show(self):
            print('parent', self.par[1:])
            print('rank', self.rank[1:])
     
    def main():
        from collections import defaultdict
     
        dicf = defaultdict(lambda :[])
        dicb = defaultdict(lambda :[])
     
        N, M, K = map(int, input().split())
     
        uf = union_find(N)
        for i in range(M):
            a, b = map(int, input().split())
            dicf[a].append(b)
            dicf[b].append(a)
            if a > b:
                a, b = b, a
            uf.union(a, b)
     
        for i in range(K):
            c, d = map(int, input().split())
            dicb[c].append(d)
            dicb[d].append(c)
     
        ans = []
        for i in range(1, N + 1):
            x = uf.size_belong(i) - len(dicf[i]) - 1
            m = 0
            for b in dicb[i]:
                if uf.find(b) == uf.find(i):
                    m += 1
     
            ans.append(x - m)
     
     
        print(' '.join(map(str, ans)))
     
     
     
     
    if __name__ == '__main__':
        main()

Submission status: Runtime Error

Solution code:
def main():
    n,m,k = map(int,input().split())
    friend = []
    block = []
    # Union-Find作る
    uf = UnionFind(n)
    #　iとすでに友達　iとブロックの数は最後に除外する
    exclude_i = [0] * n

    for _ in range(m):
        a,bb = map(int,input().split())
        # aとbを同じグループにする
        uf.union(a-1,bb-1)
        friend.append([a-1,bb-1])

    for _ in range(k):
        c,d = map(int,input().split())
        block.append([c-1,d-1])
        # CとDが友達候補（同じグループ）なら除外する　可哀想
        if uf.same(c-1,d-1):
            exclude_i[c-1] += 1
            exclude_i[d-1] += 1


    for i, f in enumerate(friend):
        # すでに友達ならそれは友達候補ではなく、もはや親友なんだよ（除外）
        if uf.same(f[0],f[1]):
            exclude_i[f[0]] += 1
            exclude_i[f[1]] += 1



    for i in range(n):
        # uf.sizeは自分を含んでるから、自分を除外する-1
        print(str(uf.size(i)-dame[i]-1 ), end = " ")
    print("")

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


if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
def dfs(g_idx, idx):
    if gps[idx] != 'o':
        return
    gps[idx] = g_idx
    mbs[g_idx] += 1
    for f in fs[idx]:
        dfs(g_idx, f)


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

fs = {}
bs = {}
for _ in range(m):
    a, b = map(int, input().split())
    if a in fs:
        fs[a].append(b)
    else:
        fs[a] = [b]
    if b in fs:
        fs[b].append(a)
    else:
        fs[b] = [a]
for _ in range(k):
    c, d = map(int, input().split())
    if c in bs:
        bs[c].append(d)
    else:
        bs[c] = [d]
    if d in bs:
        bs[d].append(c)
    else:
        bs[d] = [c]

g_idx = 0
gps = ['o'] * (n + 1)
mbs = {}

for idx in range(1, n + 1):
    if gps[idx] != 'o':
        continue
    gps[idx] = g_idx
    mbs[g_idx] = 1
    for f in fs.get(idx, []):
        dfs(g_idx, f)
    g_idx += 1

out = ''
for idx in range(1, n + 1):
    ans = mbs[gps[idx]] - 1 - len(fs.get(idx, []))
    for b_idx in bs.get(idx, []):
        if gps[b_idx] == gps[idx]:
            ans -= 1
    out += str(ans) + ' '
print(out.rstrip())

Submission status: Runtime Error

Solution code:
# スペース区切りの整数入力
N,M,K = map(int, input().split())

fcnum = [ 0 for i in range(N+1)]
fring = [[] for i in range(N+1)]
frno =  [-1 for i in range(N+1)]

ab = []
for i in range(M):
    aa,bb = map(int, input().split())
    if aa > bb:
        aa,bb = bb,aa
    #ab.append([aa,bb])
    fcnum[aa] -= 1
    fcnum[bb] -= 1
    #for aa,bb in ab:
    if frno[aa] == -1 and frno[bb] == -1:
        frn = min(aa,bb)
        frno[aa] = frn
        frno[bb] = frn
        fring[frn].append(aa)
        fring[frn].append(bb)
    elif frno[aa] == -1 and frno[bb] != -1:
        frn = frno[bb]
        frno[aa] = frn
        fring[frn].append(aa)
    elif frno[aa] != -1 and frno[bb] == -1:
        frn = frno[aa]
        frno[bb] = frn
        fring[frn].append(bb)
    else:
        if frno[aa] != frno[bb]:
            if len(fring[aa]) > len(fring[bb]):
                frnto = frno[aa]
                frnfrom = frno[bb]
            else:
                frnto = frno[bb]
                frnfrom = frno[aa]
            fring[frnto].extend(fring[frnfrom])
            for mvf in fring[frnfrom]:
                frno[mvf] = frnto
            del fring[frnfrom]

for k in range(len(fring)):
    cnum = len(fring[k]) - 1
    for ff in fring[k]:
        fcnum[ff] += cnum

cd = []
for i in range(K):
    cc,dd = map(int, input().split())
    #if cc > dd:
    #    cc,dd = dd,cc
    #cd.append([cc,dd])
    if frno[cc] == frno[dd]:
        fcnum[cc] -= 1
        fcnum[dd] -= 1

for i in range(1,len(fcnum)):
    print(fcnum[i]," ",end="")

Submission status: Runtime Error

Solution code:
def dfs(g_idx, idx):
    if gps[idx] != 'o':
        return
    gps[idx] = g_idx
    mbs[g_idx] += 1
    for f in fs[idx]:
        dfs(g_idx, f)


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

fs = {}
bs = {}
for _ in range(m):
    a, b = map(int, input().split())
    if a in fs:
        fs[a].append(b)
    else:
        fs[a] = [b]
    if b in fs:
        fs[b].append(a)
    else:
        fs[b] = [a]
for _ in range(k):
    c, d = map(int, input().split())
    if c in bs:
        bs[c].append(d)
    else:
        bs[c] = [d]
    if d in bs:
        bs[d].append(c)
    else:
        bs[d] = [c]

g_idx = 0
gps = ['o'] * (n + 1)
mbs = {}

for idx in range(1, n + 1):
    if gps[idx] != 'o':
        continue
    gps[idx] = g_idx
    mbs[g_idx] = 1
    for f in fs[idx]:
        dfs(g_idx, f)
    g_idx += 1

out = ''
for idx in range(1, n + 1):
    ans = mbs[gps[idx]] - 1 - len(fs[idx])
    for b_idx in bs.get(idx, []):
        if gps[b_idx] == gps[idx]:
            ans -= 1
    out += str(ans) + ' '
print(out.rstrip())

Submission status: Runtime Error

Solution code:
line = input().split()
nPerson = int(line[0])
nFriend = int(line[1])
nBlock  = int(line[2])
 
friends = [[] for i in range(nFriend)]
for i in range(nFriend):
  line = input().split()
  friends[i] =[int(line[0]), int(line[1]) ]
 
blocks = [[] for i in range(nBlock)]
for i in range(nBlock):
  line = input().split()
  blocks[i] = [int(line[0]), int(line[1]) ]
  
connected = [[] for i in range(nPerson+1)]
  
for i in friends:
  connected[i[0]].append(i[1])
  connected[i[1]].append(i[0])
 
blocked = [[] for i in range(nPerson+1)]
for i in blocks:
  blocked[i[0]].append(i[1])
  blocked[i[1]].append(i[0])
  
for i in range(len(connected)):
  connected[i] = set(connected[i])
for i in range(len(blocked)):
  blocked[i] = set(blocked[i])
  
nCand = [0]*(nPerson+1)
 
def findCand(target,curPer):
  if visited[curPer] == True :
    return
  visited[curPer] = True
  if curPer not in connected[target] and curPer not in blocked[target]:
    nCand[target] += 1
  for i in connected[curPer]:
    findCand(target,i)
 
for i in range(1,nPerson+1):
  visited = [False]*(nPerson+1)
  visited[i] = True
  for j in connected[i]:
    findCand(i,j)
 
res = ""
for i in range(1,nPerson+1):
  res += str(nCand[i]) + " "
  
print(res

Submission status: Runtime Error

Solution code:
from collections import defaultdict
class UnionFind:
    def __init__(self, n=0):
        self.d = [-1 for _ in range(n)]
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return False
        if -self.d[x] < -self.d[y]: # swap
            t = self.d[x]
            self.d[x] = self.d[y]
            self.d[y] = t
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.d[self.find(x)]
    

def main():
    N, M, K = map(int, input().split())
    uf = UnionFind(N)

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

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


    ret = []
    for i in range(N):
        ans = uf.size(i) - 1 - deg[i]
        for u in to[i]:
            if uf.same(i, u): ans -= 1
        ret.append(str(ans))

    print(' '.join(ret))


main()

Submission status: Runtime Error

Solution code:
line = input().split()
nPerson = int(line[0])
nFriend = int(line[1])
nBlock  = int(line[2])

friends = [[] for i in range(nFriend)]
for i in range(nFriend):
  line = input().split()
  friends[i] =[int(line[0]), int(line[1]) ]

blocks = [[] for i in range(nBlock)]
for i in range(nBlock):
  line = input().split()
  blocks[i] = [int(line[0]), int(line[1]) ]
  
connected = [[] for i in range(nPerson+1)]
  
for i in friends:
  connected[i[0]].append(i[1])
  connected[i[1]].append(i[0])

blocked = [[] for i in range(nPerson+1)]
for i in blocks:
  blocked[i[0]].append(i[1])
  blocked[i[1]].append(i[0])
  
for i in range(len(connected)):
  connected[i] = set(connected[i])
for i in range(len(blocked)):
  blocked[i] = set(blocked[i])
  
nCand = [0]*(nPerson+1)

def findCand(target,curPer):
  if visited[curPer] == True :
    return
  visited[curPer] = True
  if curPer not in connected[target] and curPer not in blocked[target]:
    nCand[target] += 1
  for i in connected[curPer]:
    findCand(target,i)

for i in range(1,nPerson+1):
  visited = [False]*(nPerson+1)
  visited[i] = True
  for j in connected[i]:
    findCand(i,j)

res = ""
for i in range(1,nPerson+1):
  res += str(nCand[i]) + " "
  
print(res)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
input = sys.stdin.readline
N, M, K = map(int, input().split())
graph = [[] for _ in range(N)]
block = [[] for _ in range(N)]
connected_components = []
count = 0
counts = [0 for _ in range(N)]
seen = [False for _ in range(N)]
def dfs(v, c, seen, origin):
    global count
    seen[v] = True
    for node in graph[v]:
        if seen[node] == True:
            continue
        if node not in block[origin]:
            count += 1
        dfs(node, c+1, seen, origin)
def dfs_connected(v, order):
    seen[v] = True
    connected_components[order].append(v)
    for node in graph[v]:
        if seen[node] == True:
            continue
        dfs_connected(node, order)
 
for Mi in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
 
for Ki in range(K):
    a, b = map(int, input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
 
for v in range(N):
    if seen[v] == True:
        continue
    connected_components.append([])
    dfs_connected(v, v)
 
for components in connected_components:
    for component in components:
        seen = [False for _ in range(N)]
        count = 0
        dfs(component, count, seen, component)
        counts[component] = count-len(graph[component])
 
print(' '.join(map(str, counts)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
N, M, K = map(int, input().split())
graph = [[] for _ in range(N)]
block = [[] for _ in range(N)]
connected_components = []
count = 0
counts = [0 for _ in range(N)]
seen = [False for _ in range(N)]
def dfs(v, c, seen, origin):
    global count
    seen[v] = True
    for node in graph[v]:
        if seen[node] == True:
            continue
        if node not in block[origin]:
            count += 1
        dfs(node, c+1, seen, origin)
def dfs_connected(v, order):
    seen[v] = True
    connected_components[order].append(v)
    for node in graph[v]:
        if seen[node] == True:
            continue
        dfs_connected(node, order)
 
for Mi in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
 
for Ki in range(K):
    a, b = map(int, input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
 
for v in range(N):
    if seen[v] == True:
        continue
    connected_components.append([])
    dfs_connected(v, v)
 
for components in connected_components:
    for component in components:
        seen = [False for _ in range(N)]
        count = 0
        dfs(component, count, seen, component)
        counts[component] = count-len(graph[component])
 
print(' '.join(map(str, counts)))

Submission status: Runtime Error

Solution code:
line = input().split()
nPerson = int(line[0])
nFriend = int(line[1])
nBlock  = int(line[2])

friends = []
for i in range(nFriend):
  line = input().split()
  friends.append(( int(line[0]), int(line[1]) ))

blocks = []
for i in range(nBlock):
  line = input().split()
  blocks.append(( int(line[0]), int(line[1]) ))
  
connected = [[] for i in range(nPerson+1)]
  
for i in friends:
  connected[i[0]].append(i[1])
  connected[i[1]].append(i[0])

blocked = [[] for i in range(nPerson+1)]
for i in blocks:
  blocked[i[0]].append(i[1])
  blocked[i[1]].append(i[0])
  
for i in range(len(connected)):
  connected[i] = set(connected[i])
for i in range(len(blocked)):
  blocked[i] = set(blocked[i])
  
nCand = [0]*(nPerson+1)

def findCand(target,curPer):
  if visited[curPer] == True :
    return
  visited[curPer] = True
  if curPer not in connected[target] and curPer not in blocked[target]:
    nCand[target] += 1
  for i in connected[curPer]:
    findCand(target,i)

for i in range(1,nPerson+1):
  visited = [False]*(nPerson+1)
  visited[i] = True
  for j in connected[i]:
    findCand(i,j)

res = ""
for i in range(1,nPerson+1):
  res += str(nCand[i]) + " "
  
print(res)

Submission status: Runtime Error

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

def main():
    N, M, K = map(int,input().split())
    friend = {}
    block = {}
    visited = [[False] * (N+1) for _ in range(N+1)]

    for _ in range(M):
        a,b = map(lambda x:int(x)-1,input().split())
        for _ in range(2):
            if not a in friend.keys():
                friend[a] = [b]
            else:
                friend[a].append(b)
            a,b = b,a

    for _ in range(K):
        c,d = map(lambda x:int(x)-1,input().split())
        for _ in range(2):
            if not c in block.keys():
                block[c] = [d]
            else:
                block[c].append(d)
            c,d = d,c


    def solve(x,y): # x: 誰視点なのか
        if visited[x][y]:
            return 0

        visited[x][y] = True
        res = 0
        if x != y:
            if x in friend.keys():
                res = not(y in friend[x])
            if x in block.keys():
                res = res and not(y in block[x])

        for f in friend[y]:
            res += solve(x,f)
        return res

    ans = []
    for i in range(N):
        ans.append(str(solve(i,i)))

    print(" ".join(ans))


if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def main():
    N, M, K = map(int,input().split())
    friend = {}
    block = {}
    visited = [[False] * (N+1) for _ in range(N+1)]

    for _ in range(M):
        a,b = map(lambda x:int(x)-1,input().split())
        for _ in range(2):
            if not a in friend.keys():
                friend[a] = [b]
            else:
                friend[a].append(b)
            a,b = b,a

    for _ in range(K):
        c,d = map(lambda x:int(x)-1,input().split())
        for _ in range(2):
            if not c in block.keys():
                block[c] = [d]
            else:
                block[c].append(d)
            c,d = d,c


    def solve(x,y): # x: 誰視点なのか
        if visited[x][y]:
            return 0

        visited[x][y] = True
        res = 0
        if x != y:
            if x in friend.keys():
                res = not(y in friend[x])
            if x in block.keys():
                res = res and not(y in block[x])

        for f in friend[y]:
            res += solve(x,f)
        return res

    ans = []
    for i in range(N):
        ans.append(str(solve(i,i)))

    print(" ".join(ans))


if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
#解答改良
n,m,k=map(int,input().split())

f=[[]for i in range(n)]
b=[[]for i in range(n)]
option=[]

for i in range(m):
    x,y=map(int,input().split())
    if i==0:
        option.append(x-1)
    f[x-1].append(y-1)
    f[y-1].append(x-1)
for i in range(k):
    x,y=map(int,input().split())
    b[x-1].append(y-1)
    b[y-1].append(x-1)

completed=[False for i in range(n)]
groups=[0]*n

x=0
while option:
    now=option.pop()
    groups[now]=x
    completed[now]=True
    for friend in f[now]:
        if completed[friend]==False and friend not in option:
            option.append(friend)
    if len(option)==0:
        x+=1
        for i in range(n):
            if completed[i]==False:
                option.append(i)
                break

size=[0]*(x)
for i in range(x):
    size[i]=groups.count(i)

for i in range(n):
    cnt=0
    for friend in f[i]:
        if groups[i]==groups[friend]:
            cnt+=1
    for block in b[i]:
        if groups[i]==groups[block]:
            cnt+=1
    print(size[groups[i]]-cnt-1,end=" ")

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N, M, K  = (int(i) for i in input().split())
graph = np.zeros((N+1, N+1))
graph2 = [[0] * (N+1) for i in range(N+1)]

#ABC = [[int(i) for i in input().split()] for i in range(N)]
for i in range(M):
    A, B =  (int(i) for i in input().split())
    graph[A][B] = 1
    graph[B][A] = 1
    graph2[A][B] = 1
    graph2[B][A] = 1

for j in range(K):
    A, B =  (int(i) for i in input().split())
    graph2[A][B] = -1
    graph2[B][A] = -1

#graph = np.array(graph)
#print(graph)
#print(graph2)
n, labels = connected_components(graph)
size = [0]*n
for i in range(1, n):
    size[i] = np.count_nonzero(labels == i)
#print(n)
# 2
#print(labels)
#print(size)
for i in range(1, N+1):
    count = 0
    for j in range(1, N+1):
        if labels[j] == labels[i] and graph2[i][j] != 0:
            count += 1
    print(size[labels[i]]-count-1)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N, M, K  = (int(i) for i in input().split())
graph = np.zeros((N+1, N+1))
graph2 = [[0] * (N+1) for i in range(N+1)]

#ABC = [[int(i) for i in input().split()] for i in range(N)]
for i in range(M):
    A, B =  (int(i) for i in input().split())
    graph[A][B] = 1
    graph[B][A] = 1
    graph2[A][B] = 1
    graph2[B][A] = 1

for j in range(K):
    A, B =  (int(i) for i in input().split())
    graph2[A][B] = -1
    graph2[B][A] = -1

#graph = np.array(graph)
#print(graph)
print(graph2)
n, labels = connected_components(graph)
size = [0]*n
for i in range(1, n):
    size[i] = np.count_nonzero(labels == i)
print(n)
# 2
print(labels)
print(size)
for i in range(1, N+1):
    count = 0
    for j in range(1, N+1):
        if labels[j] == labels[i] and graph2[i][j] != 0:
            count += 1
    print(size[labels[i]]-count-1)

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 search(i0, visited, fr):
	for i1 in fr[i0]:
# 		if i1 not in visited:
# 			visited.add(i1)
		if not visited[i1]:
			visited[i1]=True
			search(i1, visited, fr)

		
def main(inputs):
	n=int(inputs[0][0])
	m=int(inputs[0][1])
	k=int(inputs[0][2])
	
	fr=defaultdict(set)
	for i in range(m):
		a=int(inputs[i+1][0])-1
		b=int(inputs[i+1][1])-1
		fr[a].add(b)
		fr[b].add(a)
		
	bl=defaultdict(set)
	for i in range(k):
		a=int(inputs[i+1+m][0])-1
		b=int(inputs[i+1+m][1])-1
		bl[a].add(b)
		bl[b].add(a)
	
	for i0 in range(n):
# 		visited=set([i0])
		visited=np.zeros(n, np.bool)
		visited[i0]=True
		search(i0, visited, fr)
# 		can=visited-fr[i0]-bl[i0]
# 		num=len(can)-1
		if len(fr[i0])>0:
			visited[np.array(list(fr[i0]))]=False
		if len(bl[i0])>0:
			visited[np.array(list(bl[i0]))]=False
		visited[i0]=False
		num=visited.sum()
# 		print(i0, num)
		print(num, end="")
		if i0<n-1: print(" ", end="")
	
	

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

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
N, M, K = tuple(map(int, input().split()))
friends = [list(map(int, input().split())) for _ in range(M)]
blocks = [list(map(int, input().split())) for _ in range(K)]

friend_matrix = np.zeros((N, N))

for friend in friends:
	friend_matrix[friend[0]-1, friend[1]-1] = 1
	friend_matrix[friend[1]-1, friend[0]-1] = 1

# matrix for direct friendship between 2
# print('friend_matrix')
# print(friend_matrix)

# matrix for friendship distance
friend_distance = shortest_path(friend_matrix)
# print('friend_distance')
# print(friend_distance)

def is_friend_candidate(a, b):
	if a == b:
		return False
	for block in blocks:
		if block == [a, b] or block == [b, a]:
			return False
	for friend in friends:
		if friend == [a, b] or friend == [b, a]:
			return False
	if friend_distance[a-1, b-1] == np.inf:
		return False
	return True

candidate_matrix = np.zeros((N, N))
for i in range(N):
	for other in range(N):
		if candidate_matrix[i, other] == 1:
			continue
		if is_friend_candidate(i+1, other+1):
			candidate_matrix[i, other] = 1
			candidate_matrix[other, i] = 1

# matrix for friendship candidate
# print('candidate_matrix')
# print(candidate_matrix)

# atcoder numpy is outdated
# print(np.__version__)
# candidate_counts = np.count_nonzero(candidate_matrix == 1, axis=0)
candidate_counts = []
for row in candidate_matrix:
	candidate_counts.append(np.count_nonzero(row == 1))

# print('candidate_counts')
# print(candidate_counts)
print(' '.join(map(str, candidate_counts)))