Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
import sys
sys.setrecursionlimit(10**9)
n,m,k=[int(i) for i in input().split()]

frends=np.zeros(shape=(n,n))
blocks=np.zeros(shape=(n,n))
for i in range(m):
    a,b=[int(j)-1 for j in input().split()]
    frends[a][b]=1
    frends[b][a]=1

for i in range(k):
    a,b=[int(j)-1 for j in input().split()]
    blocks[a][b]=1
    blocks[b][a]=1

l,labels=connected_components(frends)
labels
group=[np.array([0]*n) for i in range(l)]

group
labels=list(labels)
for i in range(n):
    group[labels[i]][i]=1

group_num=[0 for i in range(l)]
for i in range(n):
    group_num[labels[i]]+=1
group_num

def get_group_num(i):
    return group_num[labels[i]]

frends=np.ones((n,n))-frends
blocks=np.ones((n,n))-blocks

def get_frend_num(i):
    check=frends[i]*group[labels[i]]
    return int(sum(check)-1)
def get_block_num(i):
    check=blocks[i]*group[labels[i]]
    return int(sum(check)-1)


for i in range(n):
    frend_group_num=get_group_num(i)-1
    frend_num=get_frend_num(i)
    block_num=get_block_num(i)
    print(abs(frend_group_num-frend_num-block_num))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
sys.setrecursionlimit(10**9)
n,m,k=[int(i) for i in input().split()]

frends=np.zeros(shape=(n,n))
blocks=np.zeros(shape=(n,n))
for i in range(m):
    a,b=[int(j)-1 for j in input().split()]
    frends[a][b]=1
    frends[b][a]=1

for i in range(k):
    a,b=[int(j)-1 for j in input().split()]
    blocks[a][b]=1
    blocks[b][a]=1

l,labels=connected_components(frends)
labels
group=[np.array([0]*n) for i in range(l)]

group
labels=list(labels)
for i in range(n):
    group[labels[i]][i]=1

group_num=[0 for i in range(l)]
for i in range(n):
    group_num[labels[i]]+=1
group_num

def get_group_num(i):
    return group_num[labels[i]]

frends=np.ones((n,n))-frends
blocks=np.ones((n,n))-blocks

def get_frend_num(i):
    check=frends[i]*group[labels[i]]
    return int(sum(check)-1)
def get_block_num(i):
    check=blocks[i]*group[labels[i]]
    return int(sum(check)-1)


for i in range(n):
    frend_group_num=get_group_num(i)-1
    frend_num=get_frend_num(i)
    block_num=get_block_num(i)
    print(abs(frend_group_num-frend_num-block_num))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
n,m,k=[int(i) for i in input().split()]

frends=np.zeros(shape=(n,n))
blocks=np.zeros(shape=(n,n))
for i in range(m):
    a,b=[int(j)-1 for j in input().split()]
    frends[a][b]=1
    frends[b][a]=1

for i in range(k):
    a,b=[int(j)-1 for j in input().split()]
    blocks[a][b]=1
    blocks[b][a]=1

l,labels=connected_components(frends)
labels
group=[np.array([0]*n) for i in range(l)]

group
labels=list(labels)
for i in range(n):
    group[labels[i]][i]=1

group_num=[0 for i in range(l)]
for i in range(n):
    group_num[labels[i]]+=1
group_num

def get_group_num(i):
    return group_num[labels[i]]

frends=np.ones((n,n))-frends
blocks=np.ones((n,n))-blocks

def get_frend_num(i):
    check=frends[i]*group[labels[i]]
    return int(sum(check)-1)
def get_block_num(i):
    check=blocks[i]*group[labels[i]]
    return int(sum(check)-1)


for i in range(n):
    frend_group_num=get_group_num(i)-1
    frend_num=get_frend_num(i)
    block_num=get_block_num(i)
    print(abs(frend_group_num-frend_num-block_num))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
n,m,k=[int(i) for i in input().split()]

frends=np.zeros(shape=(n,n))
blocks=np.zeros(shape=(n,n))
frends=np.zeros(shape=(10**4,10**4))
for i in range(m):
    a,b=[int(j)-1 for j in input().split()]
    frends[a][b]=1
    frends[b][a]=1

for i in range(k):
    a,b=[int(j)-1 for j in input().split()]
    blocks[a][b]=1
    blocks[b][a]=1

l,labels=connected_components(frends)
labels
group=[np.array([0]*n) for i in range(l)]

group
labels=list(labels)
for i in range(n):
    group[labels[i]][i]=1

group_num=[0 for i in range(l)]
for i in range(n):
    group_num[labels[i]]+=1
group_num

def get_group_num(i):
    return group_num[labels[i]]

frends=np.ones((n,n))-frends
blocks=np.ones((n,n))-blocks

def get_frend_num(i):
    check=frends[i]*group[labels[i]]
    return int(sum(check)-1)
def get_block_num(i):
    check=blocks[i]*group[labels[i]]
    return int(sum(check)-1)


for i in range(n):
    frend_group_num=get_group_num(i)-1
    frend_num=get_frend_num(i)
    block_num=get_block_num(i)
    print(abs(frend_group_num-frend_num-block_num))

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
n,m,k=[int(i) for i in input().split()]

frends=np.zeros(shape=(n,n))
blocks=np.zeros(shape=(n,n))

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

for i in range(k):
    a,b=[int(j)-1 for j in input().split()]
    blocks[a][b]=1
    blocks[b][a]=1

l,labels=connected_components(frends)
labels
group=[np.array([0]*n) for i in range(l)]

group
labels=list(labels)
for i in range(n):
    group[labels[i]][i]=1

group_num=[0 for i in range(l)]
for i in range(n):
    group_num[labels[i]]+=1
group_num

def get_group_num(i):
    return group_num[labels[i]]

frends=np.ones((n,n))-frends
blocks=np.ones((n,n))-blocks

def get_frend_num(i):
    check=frends[i]*group[labels[i]]
    return int(sum(check)-1)
def get_block_num(i):
    check=blocks[i]*group[labels[i]]
    return int(sum(check)-1)


for i in range(n):
    frend_group_num=get_group_num(i)-1
    frend_num=get_frend_num(i)
    block_num=get_block_num(i)
    print(abs(frend_group_num-frend_num-block_num))

Submission status: Runtime Error

Solution code:
labels
group=[np.array([0]*n) for i in range(l)]

group
labels=list(labels)
for i in range(n):
    group[labels[i]][i]=1

group_num=[0 for i in range(l)]
for i in range(n):
    group_num[labels[i]]+=1
group_num

def get_group_num(i):
    return group_num[labels[i]]

frends=np.ones((n,n))-frends
blocks=np.ones((n,n))-blocks

def get_frend_num(i):
    check=frends[i]*group[labels[i]]
    return int(sum(check)-1)
def get_block_num(i):
    check=blocks[i]*group[labels[i]]
    return int(sum(check)-1)


for i in range(n):
    frend_group_num=get_group_num(i)-1
    frend_num=get_frend_num(i)
    block_num=get_block_num(i)
    print(abs(frend_group_num-frend_num-block_num))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import Counter

def dfs(nw):
    for nx in B[nw]:
        if V[nx]==-1:
            V[nx] = cnt
            dfs(nx)

F = [[] for _ in range(n)]
B = [[] for _ in range(n)]
n, m, k = list(map(int, sys.stdin.readaline().split()))
for i in range(m):
    a,b = map(lambda x: int(x)-1, map(int, sys.stdin.readline().split()))
    F[a].append(b)
    F[b].append(a)
for i in range(k):
    c,d = map(lambda x: int(x)-1, map(int, sys.stdin.readline().split()))
    F[c].append(d)
    F[d].append(c)

V = [-1]*n
cnt = 1
for i in range(n):
    if V[i]==-1:
        V[i] = cnt
        dfs(i)
        cnt += 1
cV = Counter(V)
ans = []
for i in range(n):
    ans.append(cV[V[i]]-1 - len(F[i]) - sum([V[b]==V[i] for b in B[i]]))

print(*ans)

Submission status: Runtime Error

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

connection={i:set() for i in range(1,N+1)}

for i in range(M):
    array=list(map(int,input().split()))
    connection[array[0]].add(array[1])
    connection[array[1]].add(array[0])

disconnection={i:set() for i in range(1,N+1)}
for j in range(K):
    array=list(map(int,input().split()))
    disconnection[array[0]].add(array[1])
    disconnection[array[1]].add(array[0])

Label={i:0 for i in range(1,N+1)}
group=dict()

def dfs(next,lab):
    if Label[next]>0:
        return
    Label[next]=lab
    if lab in group:
        group[lab]+=1
    else:
        group[lab]=1
    for i in connection[next]:
        dfs(i,lab)

for i in range(1,N+1):
    dfs(i,i)

ans=[]
for i in range(1,N+1):
    eliminate_num=0
    for j in disconnection[i]:
        if Label[i]==Label[j]:
            eliminate_num+=1
    ans.append(str(group[Label[i]]-len(connection[i])-eliminate_num-1))

print(" ".join(ans))

Submission status: Runtime Error

Solution code:
n,m,k = map(int,input().split())
f = [[] for _ in range(n)]
g = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    f[a].append(b)
    f[b].append(a)
for _ in range(k):
    c,d = map(int,input().split())
    c,d = c-1,d-1
    g[c].append(d)
    g[d].append(c)
d = {}
parent = [-1]*n
seen = [False]*n
from collections import deque
for i in range(n):
    if seen[i]: continue
    stack = deque()
    d[i] = set([i])
    stack = [i]
    while stack:
        v = stack.pop()
        seen[v] = True
        parent[v]=i
        for nv in f[v]:
            if seen[nv]: continue
            d[i].add(nv)
            stack.append(nv)
ans = [0]*n
for i in range(n):
    group = d[parent[i]]
    sum = len(d[i]) -len(f[i]) - len(set(g[i])&group) -1
    ans[i]=sum
print(*ans)

Submission status: Runtime Error

Solution code:
class UnionFind():
    
    # 要素数を指定して作成 はじめは全ての要素が別グループに属し、親はいない
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    # xの根を返す
    def find(self, x):
        if self.parents[x] < 0:  return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    # xとyが属するグループを併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:  return
        if self.parents[x] > self.parents[y]:  x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    # xが属するグループの要素数
    def size(self, x):  return -self.parents[self.find(x)]
    
    # ｘとyが同じグループか否か
    def same(self, x, y):  return self.find(x) == self.find(y)
    
    # xと同じメンバーの要素
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    # 根の一覧
    def roots(self):  return [i for i, x in enumerate(self.parents) if x < 0]
    
    # グループ数
    def group_count(self):  return len(self.roots())
    
    # 可視化 [print(uf)]
    def __str__(self):  return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

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

G2 = [[] for _ in range(N)]
for i in range(K):
    a, b = map(int, input().split())
    G2[a - 1].append(b - 1)
    G2[b - 1].append(a - 1)
    
uf = UnionFind(N)
for i in range(M):
    for j in G1[i]:
        uf.union(i, j)
    
for i in range(N):
    ans = uf.size(i)  - len(G1[i]) - 1
    for j in G2[i]:
        if uf.same(i, j):  ans -= 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)


N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ in range(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)


friendnetwork = []
sgn = [0 for _ in range(N)]
groupnum = 0

def makenetwork(n, groupnum):
  for item in friend[n]:
    if sgn[item] > 0:
      continue
    else:
      sgn[item] = groupnum
      makenetwork(item, groupnum)

for k in range(N):
  if sgn[k] == 0:
    groupnum += 1
    sgn[k] = groupnum
    makenetwork(k, groupnum)


friends = [[] for _ in range(groupnum)]
for k in range(N):
  friends[sgn[k]-1].append(k)

ans = []
for k in range(N):
  num = len(friends[sgn[k]-1])-1  - len(friend[k])
  for item in block[k]:
    if sgn[item] == sgn[k]:
      num -= 1
  ans.append(num)

a = str(ans[0])
for j in range(1, len(ans)):
  a += ' '+ str(ans[j])
print(a)

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ in range(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)


friendnetwork = []
sgn = [0 for _ in range(N)]
groupnum = 0

def makenetwork(n, groupnum):
  for item in friend[n]:
    if sgn[item] > 0:
      continue
    else:
      sgn[item] = groupnum
      makenetwork(item, groupnum)

for k in range(N):
  if sgn[k] == 0:
    groupnum += 1
    sgn[k] = groupnum
    makenetwork(k, groupnum)


friends = [[] for _ in range(groupnum)]
for k in range(N):
  friends[sgn[k]-1].append(k)

ans = []
for k in range(N):
  num = len(friends[sgn[k]-1])-1  - len(friend[k])
  for item in block[k]:
    if sgn[item] == sgn[k]:
      num -= 1
  ans.append(num)

a = str(ans[0])
for j in range(1, len(ans)):
  a += ' '+ str(ans[j])
print(a)

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ in range(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)


friendnetwork = []
sgn = [0 for _ in range(N)] #networkに属したら1
groupnum = 0

def makenetwork(n, groupnum):
  for item in friend[n]:
    if sgn[item] > 0:
      continue
    else:
      sgn[item] = groupnum
      makenetwork(item, groupnum)

for k in range(N):
  if sgn[k] == 0:
    groupnum += 1
    makenetwork(k, groupnum)

friends = [[] for _ in range(groupnum)]
for k in range(N):
  friends[sgn[k]-1].append(k)

ans = []
for k in range(N):
  num = len(friends[sgn[k]-1])-1  - len(friend[k])
  for item in block[k]:
    if sgn[item] == sgn[k]:
      num -= 1
  ans.append(num)

a = str(ans[0])
for j in range(1, len(ans)):
  a += ' '+ str(ans[j])
print(a)

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
stock=[set() for i in range(n)]
ter=[0]*n
ans=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    stock[a-1].append(b-1)
    stock[b-1].append(a-1)
    ans[a-1]-=1
    ans[b-1]-=1
def dfs(j,k):
    size[k]+=1
    for next_j in stock[j]:
        if ter[next_j]==0:
            ter[next_j]=k
            dfs(next_j,k)
total=0
size=[0]*(n+1)
for i in range(n):
    if ter[i]==0:
        total+=1
        ter[i]=total
        dfs(i,total)

for i in range(n):
    ans[i]+=size[ter[i]]-1
for i in range(k):
    c, d = map(int, input().split())
    if ter[c-1]==ter[d-1]:
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)
n,m,k=map(int,input().split())
stock=[set() for i in range(n)]
ter=[0]*n
ans=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    stock[a-1].append(b-1)
    stock[b-1].append(a-1)
    ans[a-1]-=1
    ans[b-1]-=1
def dfs(j,k):
    size[k]+=1
    for next_j in stock[j]:
        if ter[next_j]==0:
            ter[next_j]=k
            dfs(next_j,k)
total=0
size=[0]*(n+1)
for i in range(n):
    if ter[i]==0:
        total+=1
        ter[i]=total
        dfs(i,total)

for i in range(n):
    ans[i]+=size[ter[i]]-1
for i in range(k):
    c, d = map(int, input().split())
    if ter[c-1]==ter[d-1]:
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m,k=map(int,input().split())
stock=[set() for i in range(n)]
ter=[0]*n
ans=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    stock[a-1].append(b-1)
    stock[b-1].append(a-1)
    ans[a-1]-=1
    ans[b-1]-=1
def dfs(j,k):
    size[k]+=1
    for next_j in stock[j]:
        if ter[next_j]==0:
            ter[next_j]=k
            dfs(next_j,k)
total=0
size=[0]*(n+1)
for i in range(n):
    if ter[i]==0:
        total+=1
        ter[i]=total
        dfs(i,total)

for i in range(n):
    ans[i]+=size[ter[i]]-1
for i in range(k):
    c, d = map(int, input().split())
    if ter[c-1]==ter[d-1]:
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
stock=[[] for i in range(n)]
ter=[0]*n
ans=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    stock[a-1].append(b-1)
    stock[b-1].append(a-1)
    ans[a-1]-=1
    ans[b-1]-=1
def dfs(i,k):
    size[k]+=1
    for next_i in stock[i]:
        if ter[next_i]==0:
            ter[next_i]=k
            dfs(next_i,k)
total=0
size=[0]*(n+1)
for i in range(n):
    if ter[i]==0:
        total+=1
        ter[i]=total
        dfs(i,total)

for i in range(n):
    ans[i]+=size[ter[i]]-1
for i in range(k):
    c,d=map(int,input().split())
    if ter[c-1]==ter[d-1]:
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
friend=[0]*n
stock=[[] for i in range(n)]
ter=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    stock[a-1].append(b-1)
    stock[b-1].append(a-1)
    friend[a-1]+=1
    friend[b-1]+=1
def dfs(i,k):
    size[k]+=1
    for next_i in stock[i]:
        if ter[next_i]==0:
            ter[next_i]=k
            dfs(next_i,k)
total=0
size=[0]*(n+1)
for i in range(n):
    if ter[i]==0:
        total+=1
        ter[i]=total
        dfs(i,total)
ans=[0]*n
for i in range(n):
    ans[i]=size[ter[i]]-friend[i]-1
for i in range(k):
    c,d=map(int,input().split())
    if ter[c-1]==ter[d-1]:
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
friend=[0]*n
stock=[[] for i in range(n)]
ter=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    stock[a-1].append(b-1)
    stock[b-1].append(a-1)
    friend[a-1]+=1
    friend[b-1]+=1
def dfs(i,k):
    for next_i in stock[i]:
        if ter[next_i]==0:
            ter[next_i]=k
            dfs(next_i,k)
total=0
for i in range(n):
    if ter[i]==0:
        total+=1
        dfs(i,total)
ans=[0]*n
size=[0]*(total+1)
for i in range(1,total+1):
    size[i]=ter.count(i)
for i in range(n):
    ans[i]=size[ter[i]]-friend[i]-1
for i in range(k):
    c,d=map(int,input().split())
    if ter[c-1]==ter[d-1]:
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

input = sys.stdin.readline
N, M, K = map(int, input().split())
ABs = [tuple(map(int, input().split())) for _ in range(M)]
CDs = [tuple(map(int, input().split())) for _ in range(K)]

X = np.eye(N, dtype=bool)
for a, b in ABs:
    X[a-1] += X[b-1]
    X[b-1] += X[a-1]
    X[:, a-1] = X[a-1]
    X[:, b-1] = X[b-1]
for a, b in ABs:
    X[a-1, b-1] = 0
    X[b-1, a-1] = 0
for c, d in CDs:
    X[c-1, d-1] = 0
    X[d-1, c-1] = 0
for i in range(N):
    X[i, i] = 0
for i in range(N):
    print(sum(X[i]), end=' ')

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
G = [[] for _ in range(N)]
AB = []
for _ in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    AB.append((a-1, b-1))

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

seen = [0]*N
def dfs(v):
    seen[v] = 1
    ret = [v]
    for u in G[v]:
        if seen[u] == 1: continue
        ret += dfs(u)
    return ret

num = [0]*N
for v in range(N):
    if seen[v] == 1: continue
    new = dfs(v)
    size = len(new)
    for n in new:
        num[n] = len(set(new) - set(H[n]) - set(G[n])) - 1
    
print(' '.join(map(str, num)))

Submission status: Runtime Error

Solution code:
# dfs
import collections
n,m,k = map(int, input().split())

friend = [[]*(n+1) for _ in range(n+1)]
block = [[]*(n+1) for _ in range(n+1)]
teams = [0]*(n+1)
for _ in range(m):
  a,b = map(int, input().split())
  friend[a].append(b)
  friend[b].append(a)
for _ in range(k):
  c,d = map(int, input().split())
  block[c].append(d)
  block[d].append(c)
  
def dfs(i):
  teams[i] = team
  for j in friend[i]:
    if teams[j] != 0:
      continue
    dfs(j)

team=1
for i in range(1,n+1):
  if teams[i] != 0:
    continue
  dfs(i)
  team+=1

c = collections.Counter(teams)

for i in range(1,n+1):
  temp = c[teams[i]]-len(friend[i])-1
  for j in block[i]:
    if teams[j] == teams[i]:
      temp -= 1
  print(temp, end='')
  if i != n:
    print(" ", end='')

Submission status: Runtime Error

Solution code:
# D - Friend Suggestions

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

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

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

        if x == y:
            return

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def same(self, x, y):
        return self.root(x) == self.root(y)

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

N,M,K = map(int,input().split())
friend = UnionFind(N+1)
block = [1]*(N+1)
for _ in range(M):
    x,y = map(int,input().split())
    block[x] += 1
    block[y] += 1
    friend.union(x,y)
for _ in range(K):
    x,y = map(int,input().split())
    if friend.same(x,y):
        block[x] += 1
        block[y] += 1
ans = [friend.size(i)-block[i] for i in range(1,N+1)]
print(*ans)

Submission status: Runtime Error

Solution code:
f=lambda x:int(x)-1
n,m,k=map(int,input().split())
par=[i for i in range(n)]
size=[1]*n
 
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
 
def union(x,y):
  fx=find(x)
  fy=find(y)
  if fx!=fy:
    par[fx]=fy
    size[fy]+=size[fx]
    size[fx]=0              
 
l=[[] for _ in range(n)]
b=[[] for _ in range(n)]
for mm in range(m):
  x,y=map(f,input().split())
  l[x].append(y)
  l[y].append(x)
  union(x,y)

for k in range(k):
  x,y=map(f,input().split())
  b[x].append(y)
  b[y].append(x)
 
ans=[]
for i in range(n):
  h=find(i)
  cnt=0
  for bb in b[i]:
    if find(bb)==h:
      cnt+=1
  ans.append(size[h]-1-len(l[i])-cnt)
print(*ans)

Submission status: Runtime Error

Solution code:
f=lambda x:int(x)-1
n,m,k=map(int,input().split())
par=[i for i in range(n)]
size=[1]*n
 
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
 
def union(x,y):
  fx=find(x)
  fy=find(y)
  if fx!=fy:
    par[fx]=fy
    size[fy]+=size[fx]
    size[x]=0              
 
l=[[] for _ in range(n)]
for mm in range(m):
  x,y=map(f,input().split())
  l[x].append(y)
  l[y].append(x)
  union(x,y)

for k in range(k):
  x,y=map(f,input().split())
  l[x].append(y)
  l[y].append(x)
 
ans=[]
for i in range(n):
  h=find(i)
  ans.append(size[h]-1-len(l[i]))
print(*ans)

Submission status: Runtime Error

Solution code:
f=lambda x:int(x)-1
n,m,k=map(f,input().split())
par=[i for i in range(n)]
size=[1]*n

def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]

def union(x,y):
  fx=find(x)
  fy=find(y)
  if fx!=fy:
    par[fx]=fy
    size[fy]+=size[fx]
    size[x]=0              

l=[[] for _ in range(n)]
for mm in range(m):
  x,y=map(f,input().split())
  l[x-1].append(y-1)
  l[y-1].append(x-1)
  union(x,y)

for kk in range(k):
  x,y=map(f,input().split())
  l[x-1].append(y-1)
  l[y-1].append(x-1)

ans=[]
for i in range(n):
  h=find(i)
  ans.append(size[h]-1-len(l[i]))
print(*ans)

Submission status: Runtime Error

Solution code:
#create date: 2020-07-03 14:00

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]

    def unite(x, y):
        x = find(x); y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def same(x, y):
        return find(x) == find(y)
    
    n, m, k = na()
    par = [-1] * n
    fb = [[0] * n for i in range(n)]
    for i in range(m):
        a, b = na()
        a -= 1; b -= 1
        unite(a, b)
        fb[a][b] = 1
        fb[b][a] = 1
    for i in range(k):
        c, d = na()
        c -= 1; d -= 1
        fb[c][d] = 1
        fb[d][c] = 1
    #print(par, fb)
    for i in range(n):
        ans = 0
        for j in range(n):
            if same(i, j) and fb[i][j]==0 and i != j:
                ans += 1
        print(ans, end=" ")
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# 1457e

from sys import stdin

#stdin = open("test/abc157_d_sample-1.in")

N, M, K = map(int, stdin.readline().strip().split())

f = [set(map(int, stdin.readline().strip().split())) for _ in range(M)]
b = [set(map(int, stdin.readline().strip().split())) for _ in range(K)]

#print(f)
#print(b)

Gf = {i+1: [] for i in range(N)}
for f1, f2 in f:
    Gf[f1] += [f2]
    Gf[f2] += [f1]

Gb = {i+1: [] for i in range(N)}
for b1, b2 in b:
    Gb[b1] += [b2]
    Gb[b2] += [b1]

def dfs(G, i):
    seen[i] = 1
    for j in G[i]:
        if seen[j]: continue
        dfs(G, j)

cand = []

for i in Gf.keys():
    #print(i)
    
    seen = {i+1: 0 for i in range(N)}
    dfs(Gf, i)
    fi = Gf[i]
    bi = Gb[i]
    #print(seen)
    #print(i, fi, bi)
    
    n = 0
    for j, s in seen.items():
        if j in fi or j in bi: continue
        n += s
    
    if n>0: n=n-1
    
    cand += [str(n)]

print(" ".join(cand))

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
ab = [[] for i in range(n)]

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

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

ans = [0 for i in range(n)]

def dfs(s):
  vis[s] = True
  ary.append(s)
  for i in ab[s]:
    if vis[i] == False:
      dfs(i)

for i in range(n):
  vis = [False for i in range(n)]
  vis[i] = True
  x = ab[i]
  for j in x:
    vis[j] = True
  c = 0
  for j in x:
    ary = []
    dfs(j)
    ary.pop(0)
    blo = set(block[i])
    cnt = set(ary) - blo
    c += len(cnt)
  ans[i] = c
print (*ans)

Submission status: Runtime Error

Solution code:
import itertools
import functools
import math
from collections import Counter
from itertools import combinations
import re
from collections import defaultdict


def chk_main():
    N,M,K=map(int,input().split())
    d = defaultdict(list)
    for i in range(M):
        F=list(map(str,input().split()))
        d[F[0]].append(F[1])
        d[F[1]].append(F[0])
    for i in range(K):
        F=list(map(str,input().split()))
        d[F[0]].append(F[1])
        d[F[1]].append(F[0])
    chk=Counter(d)

    ans =[]
    for i in range(1,N+1):
        a = ( N - 1 ) - len(chk[str(i)])
        ans.append(a)
    print(*ans)

chk_main()

Submission status: Runtime Error

Solution code:
import sys
import math
import numpy as np
import copy

def dfs(now, group, groups, edges):
    if groups[now] != -1:
        return 0
    groups[now] = group
    cnt = 1
    for to in edges[now]:
        cnt += dfs(to, group, groups, edges)
    return cnt

def main():
    n, m, k = map(int, input().split())
    edges = [list() for i in range(n)]
    ngs = [list() for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        edges[a].append(b)
        edges[b].append(a)
    for i in range(k):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        ngs[c].append(d)
        ngs[d].append(c)


    cnt = 0
    groups = [-1 for i in range(n)]
    nodes_cnt = list()

    ans = [0 for i in range(n)]
    
    for i in range(n):
        if groups[i] == -1:
            nodes_cnt.append(dfs(i, cnt, groups, edges))
            cnt += 1
        ans[i] = nodes_cnt[groups[i]] - len(edges[i]) - 1
        for ng in ngs[i]:
            if groups[i] == groups[ng]:
                ans[i] -= 1

    print(*ans, sep=" ")


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