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:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):#要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):#要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):#要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):#要素x, yが同じグループに属するかどうかを返す

        return self.find(x) == self.find(y)

    def members(self, x):#要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):#すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):#グループの数を返す
        return len(self.roots())

    def all_group_members(self):#all_group_members O(N)かかるので注意
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
 

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

uff=UnionFind(n+1)
ab=[]
cd=[]
for i in range(m):
    ab.append(list(map(int,input().split())))

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


adlist_ab=[ [i+1] for i in range(n)]#交流のあるやつ同士の隣接リスト
for i in range(m):#1から順に見ていく
    x=ab[i][0]
    y=ab[i][1]
    adlist_ab[x-1].append(y)
    adlist_ab[y-1].append(x)

for i in range(m):
   # print("gn")
    a=ab[i][0]
    b=ab[i][1]
    if uff.same(a,b)==False:
        uff.union(a,b)
friend=[]
block=[]
for i in range(1,n+1):
    friend.append(uff.size(i))

ufb=UnionFind(n+1)

for i in range(k):
   # print("gn")
    a=cd[i][0]
    b=cd[i][1]
    if ufb.same(a,b)==False:
        ufb.union(a,b)

for i in range(1,n+1):
    block.append(ufb.size(i)-1)
#print(friend)
#print(block)

for i in range(n):
#    print(len(adlist_ab[i]),end=" ")
#print()


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

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m,k=map(int, input().split())
friend=[[] for i in range(n+1)]
block_count=[0]*(n+1)
uf=UnionFind(n+1)
for i in range(1,n+1):
    a,b=map(int, input().split())
    friend[a].append(b)
    uf.union(a,b)

for i in range(1,k+1):
    a,b=map(int, input().split())
    if uf.sama(a,b)==True:
        block_count[i]+=1

answer=[0]*(n)
for i in range(1,n+1):
    answer[i-1]==uf.size(i)-len(friend[i])-block_count[i]-1

print(answer)

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m,k=map(int, input().split())
friend=[[] for i in range(n+1)]
block_count=[0]*(n+1)
uf=UnionFind(n+1)
for i in range(1,n+1):
    a,b=map(int, input().split())
    friend[a].append(b)
    uf.union(a,b)

for i in range(1,k+1):
    a,b=map(int, input().split())
    if uf.sama(a,b)==True:
        block_count[i]+=1

answer=[0]*(n)
for i in range(1,n+1):
    answer[i-1]==uf.size(i)-len(friend[i])-block_count[i]-1

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

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m,k=map(int, input().split())
friend=[[] for i in range(n+1)]
block_count=[0]*(n+1)
uf=UnionFind(n+1)
for i in range(1,n+1):
    a,b=map(int, input().split())
    friend[a].append(b)
    uf.union(a,b)

for i in range(1,k+1):
    a,b=map(int, input().split())
    if uf.sama(a,b)==True:
        block_count[i]+=1

answer=[0]*(n+1)
for i in range(1,n+1):
    answer[i]==uf.size(i)-len(friend[i])-block_count[i]-1

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

Submission status: Runtime Error

Solution code:
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 main(): 
  n, m, k = map(int, input().split())
  uf = UnionFind(n)
  ans = [0] * n
  deg = [0] * n
  for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.union(a,b)
    deg[a] += 1
    deg[b] += 1
  for _ in range(k):
    c,d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c,d):
      deg[c] += 1
      deg[d] += 1
  for i in range(n):
    ans[i] = uf.size(i) - deg[i] - 1
  print(' '.join(map(str,ans)))

main()

Submission status: Runtime Error

Solution code:
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 main(): 
  n, m, k = map(int, input().split())
  uf = UnionFind(n)
  ans = [0] * n
  deg = [0] * n
  for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.union(a,b)
    deg[a] += 1
    deg[b] += 1
  for _ in range(k):
    c,d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c,d):
      deg[c] += 1
      deg[d] += 1
  for i in range(n):
    ans[i] = uf.size(i) - deg[i] - 1
  print(' '.join(map(str,ans)))

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
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(roots())

def main(): 
  n, m, k = map(int, input().split())
  uf = UnionFind(n)
  ans = [0] * n
  deg = [0] * n
  for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.union(a,b)
    deg[a] += 1
    deg[b] += 1
  for _ in range(k):
    c,d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c,d):
      deg[c] += 1
      deg[d] += 1
  for i in range(n):
    ans[i] = uf.size(i) - deg[i] - 1
  print(' '.join(map(str,ans)))

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
import networkx as nx

Submission status: Runtime Error

Solution code:
nmk_list = input().split(" ")
N = int(nmk_list[0])
M = int(nmk_list[1])
K = int(nmk_list[2])

n_list =[[0 for j in range(N)] for i in range(N)]

for m in range(M):
    ab = input().split(" ")
    a = int(ab[0])-1
    b = int(ab[1])-1
    n_list[a][b] = 1
    n_list[b][a] = 1
for k in range(K):
    cd = input().split(" ")
    c = int(cd[0])-1
    d = int(cd[1])-1
    n_list[c][d] = -1
    n_list[d][c] = -1

for i in range(N):
    queue = []
    visit = [0 for num in range(N)]
    fdbk = 0
    for j in range(N):
        if n_list[i][j] == 1:
            queue.append(j)
            visit[j] = 1
            fdbk += 1
    q = 0
    while True:
        pop = queue[q]
        for j in range(N):
            if n_list[pop][j] == 1 and visit[j] == 0:
                queue.append(j)
                visit[j] = 1
                if n_list[i][j] != 0:
                    fdbk += 1
        q += 1
        if len(queue) == q:
            break
    print(q - fdbk -1, end = " ")

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().strip().split())
# friend = [list(map(int, input().split())) for _ in range(m)]
friend=[[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().strip().split())
    a-=1; b-=1
    friend[a].append(b)
    friend[b].append(a)

block=[[] for _ in range(n)]
for i in range(k):
    a, b = map(int, input().strip().split())
    a-=1; b-=1
    block[a].append(b)
    block[b].append(a)

def dfs(i):
    global cnt
    visited[i]=True
    if i!=root and i not in friend[root] and i not in block[root]:
        cnt+=1
    for child in friend[i]:
        if visited[child]==False:
            dfs(child)

for i in range(n):
    # stack=0
    root=i
    cnt=0
    visited=[False]*n
    dfs(i)#-len(friend[i])
    print(cnt)

Submission status: Runtime Error

Solution code:
S = str(input())
Q = int(input())

qs = [list(map(str, input().split())) for _ in range(Q)]

def addFirst(base, s):
    return s + base

def addLast(base, s):
    return base + s

def reverse(base):
    return ''.join(list(reversed(base)))

for ls in qs:
    if ls[0] == "1":
        S = reverse(S)
    else:
        if ls[1] == "1":
            S = addFirst(S, ls[2])
        else:
            S = addLast(S, ls[2])

print(S)

Submission status: Runtime Error

Solution code:
#深さ優先探索

import collections

n, m ,k= map(int, input().split())
# 入力値をzero-basedにしつつ格納する
pairs = [tuple(map(lambda x: int(x) - 1, input().split()))
         for _ in range(m)]
node=[[] for _ in range(n)]
block=[[] for _ in range(n)]
for p in pairs:
  node[p[0]].append(p[1])
  node[p[1]].append(p[0])
s=0
seen=[None]*n

sys.setrecursionlimit(10**9)
def dfs(v,c):
  seen[v]=c
  for next_v in node[v]:
    if seen[next_v]!=None:
      continue
    else:
      dfs(next_v,c)
      
for i in range(n):
  if seen[i]!=None:
    continue
  else:
    dfs(i,s)
    s+=1

#ブロックについて
for i in range(k):
  c,d=map(lambda x: int(x) - 1, input().split())
  if seen[c]==seen[d]:
    block[c].append(d)
    block[d].append(c)
  
count=collections.Counter(seen)
for i in range(n):
  print(count[seen[i]]-len(node[i])-1-len(block[i]))
  
print(block)

Submission status: Runtime Error

Solution code:
#深さ優先探索

import collections

n, m ,k= map(int, input().split())
# 入力値をzero-basedにしつつ格納する
pairs = [tuple(map(lambda x: int(x) - 1, input().split()))
         for _ in range(m)]
node=[[] for _ in range(n)]
block=[[] for _ in range(n)]
for p in pairs:
  node[p[0]].append(p[1])
  node[p[1]].append(p[0])
s=0
seen=[None]*n
def dfs(v,c):
  seen[v]=c
  for next_v in node[v]:
    if seen[next_v]!=None:
      continue
    else:
      dfs(next_v,c)
      
for i in range(n):
  if seen[i]!=None:
    continue
  else:
    dfs(i,s)
    s+=1

#ブロックについて
for i in range(k):
  c,d=map(lambda x: int(x) - 1, input().split())
  if seen[c]==seen[d]:
    block[c].append(d)
    block[d].append(c)
  
count=collections.Counter(seen)
for i in range(n):
  print(count[seen[i]]-len(node[i])-1-len(block[i]))

Submission status: Runtime Error

Solution code:
#Union Findデータ構造
class UnionFind:
    def __init__(self, n):
        #Data: 正:親要素のノード番号, 負:サイズ
        self.D = [-1 for i in range(n)]
    
    def find(self, x:int)->int:
        if self.D[x] < 0:
            return x
        else:
            self.D[x] = self.find(self.D[x])
            return self.D[x]

    
    def unite(self, x:int, y:int)->bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        else:
            if self.D[x] > self.D[y]:
                self.D[x], self.D[y] = self.D[y], self.D[x]
            else:
                pass
            self.D[x] += self.D[y]
            self.D[y] = x
            return True

    def same(self, x:int, y:int)->bool:
        return self.find(x) == self.find(y)

    def size(self, x:int)->int:
        return -self.D[self.find(x)]

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

uf = UnionFind(n)  

CF = [0] * n #Count Friend
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    CF[a] += 1
    CF[b] += 1
    uf.unite(a, b)

CBinG = [0] * n #Count Block in Group
for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c, d) == True:
        CBinG[c] += 1
        CBinG[d] += 1
    else:
        pass

for i in range(n):
    ans = uf.size(i) - 1 - CF[i] - CBinG[i]
    print(ans, end=' ')

Submission status: Runtime Error

Solution code:
#Union Findデータ構造
class UnionFind:
    def __init__(self, n):
        #Data: 正:親要素のノード番号, 負:サイズ
        self.D = [-1 for i in range(n)]
    
    def find(self, x:int)->int:
        if self.D[x] < 0:
            return x
        else:
            self.D[x] = self.find(self.D[x])
            return self.D[x]
    
    def unite(self, x:int, y:int)->bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        else:
            if self.D[x] > self.D[y]:
                self.D[x], self.D[y] = self.D[y], self.D[x]
            else:
                pass
            self.D[x] += self.D[y]
            self.D[y] = x
            return True

    def same(self, x:int, y:int)->bool:
        return self.find(x) == self.find(y)

    def size(self, x:int)->int:
        return -self.D[self.find(x)]

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

uf = UnionFind(n)  

CF = [0] * n #Count Friend
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    CF[a] += 1
    CF[b] += 1
    uf.unite(a, b)

CBinG = [0] * n #Count Block in Group
for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c, d) == True:
        CBinG[c] += 1
        CBinG[d] += 1

for i in range(n):
    ans = uf.size(i) - 1 - CF[i] - CBinG[i]
    print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

# 入力はstringで入る．
# intにしたければ int(input())
# floatで受け取ると 1.0 になる．

import numpy as np
#from scipy.sparse.csgraph import dijkstra
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import connected_components

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

if M == 0:
    for i in range(N):
        print(0,end=" ")

elif K == 0:
    AB = np.array([list(map(int,input().split())) for i in range(M)])
    AB = AB-1

    # 行列の作成
    dataAB = [1]*M

    Friend_Mat = coo_matrix((dataAB,(AB[:,0],AB[:,1])), shape=(N,N)).toarray()

    Friend_Mat += Friend_Mat.T

    # 連結成分のラベル付け
    Num, labels = connected_components(Friend_Mat)
    L = np.array(labels)

    for i in range(N):
        print(np.count_nonzero(L==L[i]) -1 - sum(Friend_Mat[i,:]),end=" ")

else:

    AB = np.array([list(map(int,input().split())) for i in range(M)])
    AB = AB-1

    # 行列の作成
    dataAB = [1]*M

    Friend_Mat = coo_matrix((dataAB,(AB[:,0],AB[:,1])), shape=(N,N)).toarray()

    Friend_Mat += Friend_Mat.T

    F_Num = [sum(Friend_Mat[i,:]) for i in range(N)]

    # 連結成分のラベル付け
    Num, labels = connected_components(Friend_Mat)
    L = np.array(labels)

    CD = np.array([list(map(int,input().split())) for i in range(K)])
    CD = CD-1
    dataCD = [1]*K
    Friend_Mat = coo_matrix((dataCD,(CD[:,0],CD[:,1])), shape=(N,N)).toarray()
    Friend_Mat += Friend_Mat.T

    for i in range(N):
        print(np.count_nonzero(L==L[i]) -1 - F_Num[i] - np.dot(Friend_Mat[:,i],np.where(L==L[i],1,0)),end=" ")

Submission status: Runtime Error

Solution code:
import numpy as np
#from scipy.sparse.csgraph import dijkstra
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import connected_components

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

if M == 0:
    for i in range(N):
        print(0,end=" ")

elif K == 0:
    AB = np.array([list(map(int,input().split())) for i in range(M)])
    AB = AB-1

    # 行列の作成
    dataAB = [1]*M

    Friend_Mat = coo_matrix((dataAB,(AB[:,0],AB[:,1])), shape=(N,N)).toarray()

    Friend_Mat += Friend_Mat.T

    # 連結成分のラベル付け
    Num, labels = connected_components(Friend_Mat)
    L = np.array(labels)

    for i in range(N):
        print(np.count_nonzero(L==L[i]) -1 - sum(Friend_Mat[i,:]),end=" ")

else:

    AB = np.array([list(map(int,input().split())) for i in range(M)])
    CD = np.array([list(map(int,input().split())) for i in range(K)])
    AB = AB-1
    CD = CD-1

    # 行列の作成
    dataAB = [1]*M
    dataCD = [1]*K

    Friend_Mat = coo_matrix((dataAB,(AB[:,0],AB[:,1])), shape=(N,N)).toarray()
    Block_Mat = coo_matrix((dataCD,(CD[:,0],CD[:,1])), shape=(N,N)).toarray()

    Friend_Mat += Friend_Mat.T
    Block_Mat += Block_Mat.T

    # 連結成分のラベル付け
    Num, labels = connected_components(Friend_Mat)
    L = np.array(labels)

    for i in range(N):
        print(np.count_nonzero(L==L[i]) -1 - sum(Friend_Mat[i,:]) - np.dot(Block_Mat[:,i],np.where(L==L[i],1,0)),end=" ")

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

# 入力はstringで入る．
# intにしたければ int(input())
# floatで受け取ると 1.0 になる．

import numpy as np
#from scipy.sparse.csgraph import dijkstra
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import connected_components

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

AB = np.array([list(map(int,input().split())) for i in range(M)])
CD = np.array([list(map(int,input().split())) for i in range(K)])
AB = AB-1
CD = CD-1

# 行列の作成
dataAB = [1]*M
dataCD = [1]*K

Friend_Mat = coo_matrix((dataAB,(AB[:,0],AB[:,1])), shape=(N,N)).toarray()
Block_Mat = coo_matrix((dataCD,(CD[:,0],CD[:,1])), shape=(N,N)).toarray()

Friend_Mat += Friend_Mat.T
Block_Mat += Block_Mat.T

# 連結成分のラベル付け
Num, labels = connected_components(Friend_Mat)
L = np.array(labels)

for i in range(N):
    print(np.count_nonzero(L==L[i]) -1 - sum(Friend_Mat[i,:]) - np.dot(Block_Mat[:,i],np.where(L==L[i],1,0)),end=" ")

Submission status: Runtime Error

Solution code:
from collections import deque
n, m, k = map(int, input().split())
F = [deque([]) for i in range(n)] #Friend
B = [deque([]) for i in range(n)] #Block
#友達関係
for i in range(m):
    a, b = map(int, input().split())
    F[a-1].append(b)
    F[b-1].append(a)

#ブロック関係
for i in range(k):
    c, d = map(int, input().split())
    B[c-1].append(d)
    B[d-1].append(c)
#print('F=',F)
#print('B=',B)

def using_DFS(p):
    if G[p] == 0:
        G[p] = num
        for j in F[p]:
            using_DFS(j-1)
    else:
        pass

#DFSで連結部分ごとのグループに分ける
G = [0] * n #Group
S = deque([])   #Size
num = 0
for i in range(n):
    if G[i] == 0:
        num += 1
        t = 0
        using_DFS(i)
        S.append(G.count(num))
    else:
        pass
#print('G=',G)
#print('S=',S)

#答えの計算
for i in range(n):
    ans = S[G[i]-1] - 1
    #ブロック関係がこの中で何人いるか
    for j in B[i]:
        if G[j-1] == G[i]:
            ans -= 1
        else:
            pass
    #直接の友達関係がこの中で何人いるか
    for k in F[i]:
        if G[k-1] == G[i]:
            ans -= 1
        else:
            pass
    print(ans)

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
tree = [[] for i in range(N)]
block  = [[] for i in range(N)]
frends_cand = [set() for i in range(N)]

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

not_visited = set([i for i in range(N)])

visited = set()
def dfs(now):
    global visited
    visited.add(now)
    if  len(tree[now]) ==0:
        return print(now)
    else:
        next_tree  = set(tree[now]) - visited#有向であればtree[now]でok
        for i in next_tree:
            dfs(i)

while len(not_visited) !=0:
    visited = set()
    next_start = not_visited.pop()
    dfs(next_start)
    not_visited = not_visited - visited
    for i in visited:
        frends_cand[i] = visited

ans = ""        
for index, cand in enumerate(frends_cand):
    friend_cand = cand - set(block[index]) - set(tree[index])
    ans +=str(len(friend_cand)-1) + ' '
print(ans.strip())

Submission status: Runtime Error

Solution code:
N, M ,K = map(int, input().split())
graph = {}
for m in range(M):
    p,q = map(int, input().split())
    if p-1 in graph.keys():
        graph[p-1].append(q-1)
    else:
        graph[p-1] = [q-1]
    if q-1 in graph.keys():
        graph[q-1].append(p-1)
    else:
        graph[q-1] = [p-1]
bgraph = {}
for k in range(K):
    p,q = map(int, input().split())
    if p-1 in bgraph.keys():
        bgraph[p-1].append(q-1)
    else:
        bgraph[p-1] = [q-1]
    if q-1 in bgraph.keys():
        bgraph[q-1].append(p-1)
    else:
        bgraph[q-1] = [p-1]
output = []
fin_list = [0]*N
for n, i in enumerate(fin_list):
    if i == 1:
        pass
    else:
        seen = [0]*N
        seen[n]=1
        fin_list[n] = 1
        todo =  graph[n].copy()
        while todo != []:
            for j in todo:
                if seen[j] == 1:
#                     print("pass!! seen=={}, j == {}".format(seen, j))
                    todo.remove(j)
                else:
                    todo.extend(graph[j])
                    todo.remove(j)
#                     print("todo=={}___seen=={}___ j=={}".format(todo, seen, j))
                    seen[j] = 1
                    fin_list[j]=1
        smallout = []
        for q, s in enumerate(seen):
            if s == 1:
                smallout.append(q)
        output.append(smallout)
final = []
for n in range(N):
    for w in output:
        if n in w:
            bcount=0
            if n in bgraph.keys():
                for b in bgraph[n]:
                    if b in w:
                        bcount+=1
            final.append(str(len(w)-1-len(graph[n])-bcount))
print(" ".join(final))

Submission status: Runtime Error

Solution code:
N, M ,K = map(int, input().split())
graph = {}
for m in range(M):
    p,q = map(int, input().split())
    if p-1 in graph.keys():
        graph[p-1].append(q-1)
    else:
        graph[p-1] = [q-1]
    if q-1 in graph.keys():
        graph[q-1].append(p-1)
    else:
        graph[q-1] = [p-1]
bgraph = {}
for k in range(K):
    p,q = map(int, input().split())
    if p-1 in bgraph.keys():
        bgraph[p-1].append(q-1)
    else:
        bgraph[p-1] = [q-1]
    if q-1 in bgraph.keys():
        bgraph[q-1].append(p-1)
    else:
        bgraph[q-1] = [p-1]

output = []
fin_list = [0]*N
for n, i in enumerate(fin_list):
    if i == 1:
        pass
    else:
        seen = [0]*N
        seen[n]=1
        fin_list[n] = 1
        todo =  graph[n].copy()
        while todo != []:
            for j in todo:
                if seen[j] == 1:
#                     print("pass!! seen=={}, j == {}".format(seen, j))
                    todo.remove(j)
                else:
                    todo.extend(graph[j])
                    todo.remove(j)
#                     print("todo=={}___seen=={}___ j=={}".format(todo, seen, j))
                    seen[j] = 1
                    fin_list[j]=1
        smallout = []
        for q, s in enumerate(seen):
            if s == 1:
                smallout.append(q)
        output.append(smallout)

        print("n=={}_____seen{}".format(n, seen))
for n in range(N):
    for w in output:
        if n in w:
            bcount=0
            if n in bgraph.keys():
                for b in bgraph[n]:
                    if b in w:
                        bcount+=1
            print(len(w)-1-len(graph[n])-bcount)

Submission status: Runtime Error

Solution code:
n,m,k = [int(v) for v in input().split()]

friend = [[] for _ in range(n+1)]
block = [[] for _ in range(n+1)]

for _ in range(m):
    l,r = [int(v) for v in input().split()]
    friend[l].append(r)
    friend[r].append(l)

for _ in range(k):
    l,r = [int(v) for v in input().split()]
    block[l].append(r)
    block[r].append(l)

comb = [{"g":-1,"sum":0} for _ in range(n+1)]
visited = [False for _ in range(n+1)]

def dfs(node,depth,g):
    if visited[node]:
        return depth - 1
    visited[node] = True
    for next_node in friend[node]:
        depth = dfs(next_node,depth+1,g)
    comb[node] = {
            "g":g,
            "sum":max(comb[node]["sum"],depth)
            }
    return depth

g = 0
for i in range(n):
    dfs(i+1,1,g)
    g += 1

for i in range(n):
    ans = comb[i+1]["sum"] - 1 - len(friend[i+1])
    for to in block[i+1]:
        if comb[i+1]["g"] == comb[to]["g"]:
            ans -= 1

    print(ans,end=' ')

Submission status: Runtime Error

Solution code:
used = [];
w = [];

def dfs(v, num):
    used[v] = num;
    for x in w[v]:
        if used[x] == 0:
            dfs(x, num);


n, m, k = (int(i) for i in input().split());

for i in range(n):
    w.append([]);

for j in range(m):
    u, v = (int(i) for i in input().split());
    u -= 1;
    v -= 1;
    w[u].append(v);
    w[v].append(u);

block = [];
for j in range(k):
    u, v = (int(i) for i in input().split());
    u -= 1;
    v -= 1;
    block.append([u, v]);

for i in range(n):
    used.append(0);

cnt_comp = 0;
for i in range(n):
    if used[i] == 0:
        cnt_comp += 1;
        dfs(i, cnt_comp);

# cnt = [0 for i in range(cnt_comp)];
# 
# for i in range(n):
#     cnt[used[i] - 1] += 1;
# 
# res = [0 for i in range(n)];
# for i in range(n):
#     res[i] = cnt[used[i] - 1] - 1;
# #print(res);
# for x in block:
#     if used[x[0]] == used[x[1]]:
#         res[x[0]] -= 1;
#         res[x[1]] -= 1;
# #print(res);
# for i in range(n):
#     for v in w[i]:
#         if used[v] == used[i]:
#             res[i] -= 1;
# 
# #print(cnt);
# 
# for i in res:
#     print(i, end=" ");