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
def main():
  N,M,K =map(int, input().split())
  A,B=[],[]
  C,D=[],[]
  for i in range(M):
    s,c = map(int, input().split())
    A.append(s)
    B.append(c)
  for i in range(K):
    s,c = map(int, input().split())
    C.append(s)
    D.append(c)
  
  # friend candidate=0
  # friend =1
  # block =-1
  f = np.eye(N)
  for a,b in zip(A,B):
    f[a-1][b-1] = 1
    f[b-1][a-1] = 1
  for c,d in zip(C,D):
    f[c-1][d-1]  =-1
    f[d-1][c-1]  =-1
  fc=[0]*N
  for i in range(N):
    fc[i] = str(np.sum(f[i]==0))
#  print(f)
#  print(fc)
  print(" ".join(fc))
  
  
  
    
if __name__=="__main__":
  main()

Submission status: Runtime Error

Solution code:
import sys

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


#xの木の根を求める
def root(x,li): 
    if li[x] == x:
        return x
    else:
        li[x] = root(li[x],li)
        return li[x]

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x] = y

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(a-1,b-1,li1)
# for i in range(K):
#     c = CD[i][0]
#     d = CD[i][1]
#     union(c-1,d-1,li2)

mm = [0 for i in range(max(li1))]
for i in range(N):
    m = root(i,li1)
    mm[m-1] += 1

# print(li1)
# print(mm)
ans = [mm[li1[i]-1]-1 for i in range(N)]
# print(ans)
sys.exit()
for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    ans[a-1] -= 1
    ans[b-1] -= 1


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

con = defaultdict(list)
block = defaultdict(set)
friend = defaultdict(set)
for _ in range(M):
    A, B = list(map(int, input().split()))
    con[A].append(B)
    con[B].append(A)
    friend[A].add(B)
    friend[B].add(A)
for _ in range(K):
    C, D = list(map(int, input().split()))
    block[C].add(D)
    block[D].add(C)

visited = set()
group = defaultdict(set)

def dfs(node, visited, key):
    if node in visited:
        return
    group[key].add(node)
    visited.add(node)
    for next in con[node]:
        if next not in visited:
            dfs(next, visited, key)


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

ret = [0] * N
for g in group.values():
    size = len(g)
    for node in g:
        exclude = 0
        for blocked in block[node]:
            if blocked in g:
                exclude += 1
        for friended in friend[node]:
            if friended in g:
                exclude += 1
        # print("node = " + str(node - 1) + " " + str(size - exclude - 1))
        ret[node - 1] = max(ret[node - 1], size - exclude - 1)

print(' '.join([str(s) for s in ret]))

Submission status: Runtime Error

Solution code:
def addfrends(friends):
    global ff
    if len(friends-ff) != 0:
        new = friends - ff
        #print(friends-ff)
        ff |= friends
        for person in new:
            addfrends(people[person][0])

n,m,k = map(int,input().split())
people = [[set(),set()] for _ in range(n+1)]
#print(people)
ans = []
for _ in range(m):
    a,b = map(int,input().split())
    people[a][0].add(b)
    people[b][0].add(a)
for _ in range(k):
    a,b = map(int,input().split())
    people[a][1].add(b)
    people[b][1].add(a)
for friends,blocked in people:
    ff = set()
    addfrends(friends)
    #print(ff - blocked - friends)
    ans.append(len(ff - blocked - friends)-1)
ans.pop(0)
print(*ans)

Submission status: Runtime Error

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

L=[[] for i in range(1+n)]
Ncnt=[0 for i in range(1+n)]
C=[0 for i in range(1+n)]

for inp in range(m):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)



def tansa(x,gone,color):
    C[x]=color
    for nex in L[x]:
        if nex in gone:
            continue
        else:
            tansa(nex,gone+(nex,),color)

now=1
for i in range(1,n):
    if C[i]==0:
        tansa(i,(i,),now)
        now+=1

CC=sorted(C)

cnt=0
ccres=[]
for i in range(now):
    ccres.append(CC.index(i))
ccres.append(n+1)
dic={i:ccres[i+1]-ccres[i] for i in range(1,now)}

#print(C)
#print(dic)

for inp in range(k):
    a,b=map(int,input().split())
    if C[a] == C[b]:
        Ncnt[a]+=1
        Ncnt[b]+=1

for i in range(1,n):
    print(dic[C[i]]-len(L[i])-Ncnt[i]-1,end=" ")
i=n
print(dic[C[i]]-len(L[i])-Ncnt[i]-1,end="")

Submission status: Runtime Error

Solution code:

import numpy as np

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

uf = UnionFind(n)

f = np.zeros((n,n),np.int64)
r = np.zeros((n,n),np.int64)

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

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

q = f + r

ans = np.zeros((n),np.int64)
for i in range(n):
    for j in range(n):
        if not i == j and q[i][j] == 0 and uf.same(i,j):
            ans[i] += 1
            
print(*ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
N,M,K = map(int,input().split())
follow = [[False for i in range(N)] for j in range(N)]
block = [[False for i in range(N)] for j in range(N)]
edges = [0 for i in range(N)]

for i in range(M):
    A,B = map(int,input().split())
    A = A-1
    B = B-1
    follow[A][B] = True
    follow[B][A] = True
    edges[A] = edges[A] + 1
    edges[B] = edges[B] + 1

n,labels = connected_components(np.array(follow))

groupV = [0]*n
for i in range(N):
    groupV[labels[i]] = groupV[labels[i]] + 1

for i in range(K):
    C,D = map(int,input().split())
    C = C-1
    D = D-1
    if (labels[C] != labels[D]) : continue
    block[C][D] = True
    block[D][C] = True
    edges[C] = edges[C] + 1
    edges[D] = edges[D] + 1

ans = ["0"]*N

for i in range(N):
    ans[i] = str(groupV[labels[i]] - 1 - edges[i])

print(" ".join(ans))

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque

n, m, k = [int(v) for v in input().split()]
friends = defaultdict(set)
for _ in range(m):
    a, b = tuple(int(v) for v in input().split())
    friends[a].add(b)
    friends[b].add(a)
blocks = defaultdict(set)
for _ in range(k):
    c, d = tuple(int(v) for v in input().split())
    blocks[c].add(d)
    blocks[d].add(c)

fnets = []
unused = set(range(1, n + 1))
while len(unused) > 0:
    root = unused.pop()
    fnet = {root}
    que = deque(friends[root])
    while len(que) > 0:
        p = que.pop()
        if p not in unused:
            continue
        fnet |= friends[p]
        que.extend(friends[p])
        unused.remove(p)
    fnets.append(fnet)

results = {}
for fnet in fnets:
    for p in fnet:
        results[p] = len(fnet - blocks[p] - friends[p]) - 1

print(" ".join(str(results[p]) for p in range(1, n + 1)))

Submission status: Runtime Error

Solution code:

import numpy as np

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

uf = UnionFind(n)

f = np.zeros((n,n),np.int32)
r = np.zeros((n,n),np.int32)

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

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

q = f + r

ans = np.zeros((n),np.int64)
for i in range(n):
    for j in range(n):
        if not i == j and q[i][j] == 0 and uf.same(i,j):
            ans[i] += 1
            
print(*ans)

Submission status: Runtime Error

Solution code:
import sys

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

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

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

start = 0
res = [-1] * n
while True:
    visited = [start]
    def deep_first(node):
        for one in node.linked:
            if not nodes[one].visited:
                visited.append(one)
                nodes[one].visited = True 
                #print(visited)
                deep_first(nodes[one])
    nodes[start].visited = True
    deep_first(nodes[start])           
    for one in visited:
        cands = 0
        for two in nodes[one].blocked:
            if two in visited:
                cands += 1
        res[one] = len(visited) - len(nodes[one].linked) - 1 - cands

    start = -1
    for i in range(1, n):
        if res[i] < 0:
            start = i
    if start == -1:
        break

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

Submission status: Runtime Error

Solution code:

#####

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

#####

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

from sys import stdin

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


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

def getGroup(groups, i):
	if i not in groups:
		groups[i]=i
	return groups[i]
		
def main(inputs):
	n=int(inputs[0][0])
	m=int(inputs[0][1])
	k=int(inputs[0][2])

	fr=set()
	frSingle=defaultdict(set)
	for i in range(m):
		a=int(inputs[i+1][0])
		b=int(inputs[i+1][1])
		fr.add(st(a,b))
		frSingle[a].add(b)
		frSingle[b].add(a)
		
	bl=defaultdict(set)
	for i in range(k):
		a=int(inputs[i+1+m][0])
		b=int(inputs[i+1+m][1])
		bl[a].add(b)
		bl[b].add(a)
	
# 	print(fr)
# 	print(bl)
# 	print()
	
	groups=np.arange(n)+1
	members=np.identity(n, np.bool)
	for i0,i1 in fr:
		g0=groups[i0-1]
		g1=groups[i1-1]
		if g0==g1:
			continue
		if g0<g1:
			mm=members[g1-1]
			groups[mm]=g0
			members[g0-1]=members[g0-1]|members[g1-1]
		else:
			mm=members[g0-1]
			groups[mm]=g1
			members[g1-1]=members[g1-1]|members[g0-1]
	
# 	print(groups)
# 	print(members)
	
# 	print()
	for i0 in range(1,n+1):
		g=groups[i0-1]
		i1s=set(np.where(members[g-1])[0]+1)
		i1s.remove(i0)
		i1s=i1s-frSingle[i0]
		i1s=i1s-bl[i0]
# 		print(i0,i1s)
		num=len(i1s)
		print(num, end="")
		if i0<n: print(" ", end="")
	
	

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

Submission status: Runtime Error

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


#xの木の根を求める
def root(x,li): 
    if li[x] == x:
        return x
    else:
        li[x] = root(li[x],li)
        return li[x]

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x] = y

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(a-1,b-1,li1)
# for i in range(K):
#     c = CD[i][0]
#     d = CD[i][1]
#     union(c-1,d-1,li2)

mm = [0 for i in range(max(li1))]
for i in range(N):
    m = root(i,li1)
    mm[m-1] += 1

# print(li1)
# print(mm)
ans = [mm[li1[i]-1]-1 for i in range(N)]
# print(ans)

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    ans[a-1] -= 1
    ans[b-1] -= 1


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)

Submission status: Runtime Error

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

graphs = {}
for i in range(1, n+1):
    graphs[i] = []

for _ in range(m):
    a, b = map(int, input().split(" "))
    graphs[a].append(b)
    graphs[b].append(a)


graph_i = [None] * (n+1)


def get_same_nodes(in_node, uses):
    kids = graphs[in_node]
    rets = []
    for kid in kids:
        if uses[kid]:
            continue
        else:
            uses[kid] = True
            rets.append(kid)
            cur_rets = get_same_nodes(kid, uses)
            rets += cur_rets
    return rets

def get_graph(start_node):
    uses = [False] * (n+1)
    uses[start_node] = True
    same_nodes = get_same_nodes(start_node, uses)
    same_nodes = [start_node] + same_nodes

    n_same_nodes = len(same_nodes)
    cur_kouhos = {}
    for node in same_nodes:
        friends = graphs[node]
        cur_n_friend = len(friends)
        kouho = n_same_nodes - 1 - cur_n_friend
        cur_kouhos[node] = kouho

    return same_nodes, cur_kouhos

gid = 1
kouhos = {}
for start_node in range(1, n+1):
    if graph_i[start_node] is not None:
        continue

    same_nodes, cur_kouhos = get_graph(start_node) 
    #print("same graph", same_nodes)
    kouhos.update(cur_kouhos)

    for node in same_nodes:
        graph_i[node] = gid
    gid += 1

#print("kouhos", kouhos)
for _ in range(k):
    c1, c2 = map(int, input().split(" "))
    g1 = graph_i[c1]
    g2 = graph_i[c2]
    if g1 != g2:
        continue

    kouhos[c1] -= 1
    kouhos[c2] -= 1

for node in range(1, n+1):
    print kouhos[node],
print

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)
  
groups = []
active = [True] * n
belong = [0] * n
g_index = 0
while any(active):
  idx = active.index(True)
  g.append([idx])
  active[idx] = False
  belong[idx] = g_index
  stack = [idx]
  while stack:
    v = stack.pop()
    for i in friend[v]:
      if active[i]:
        stack.append(i)
        active[i] = False
        belong[i] = g_index
        g.append(i)
  groups.append(g)
  g_index += 1
  
for i in range(n):
  size = len(groups[belong[i]]) - 1
  for j in groups[belong[i]]:
    if j in friend[i] or j in block[i]:
      size -= 1
  print(size, end=' ')

Submission status: Runtime Error

Solution code:
import sys

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

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

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

start = 0
res = [-1] * n
while True:
    visited = []
    def deep_first(node):
        for one in node.linked:
            if one not in visited:
                visited.append(one)
                #print(visited)
                deep_first(nodes[one])
    deep_first(nodes[start])           
    for one in visited:
        cands = 0
        for two in nodes[one].blocked:
            if two in visited:
                cands += 1
        res[one] = len(visited) - len(nodes[one].linked) - 1 - cands

    start = -1
    for i in range(1, n):
        if res[i] < 0:
            start = i
    if start == -1:
        break

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

f=np.full((n, n), 1,dtype=int)
f=f-np.eye(n,dtype=int)


for i in range(m):
    a,b = map(int, input().split())
    f[a-1][b-1]=0
    f[b-1][a-1]=0
    
for i in range(k):
    c,d = map(int, input().split())
    f[c-1][d-1]=0
    f[d-1][c-1]=0
    
print(*f.sum(axis=0))

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque

n, m, k = [int(v) for v in input().split()]
friends = defaultdict(set)
for _ in range(m):
    a, b = tuple(int(v) for v in input().split())
    friends[a].add(b)
    friends[b].add(a)
blocks = defaultdict(set)
for _ in range(k):
    c, d = tuple(int(v) for v in input().split())
    blocks[c].add(d)
    blocks[d].add(c)

fnets = []
used = set()
while len(unused) > 0:
    root = unused.pop()
    fnet = {root}
    que = deque(friends[root])
    while len(que) > 0:
        p = que.pop()
        if p in used:
            continue
        fnet |= friends[p]
        que.extend(friends[p])
        used.add(p)
    fnets.append(fnet)

results = {}
for fnet in fnets:
    for p in fnet:
        results[p] = len(fnet - blocks[p] - friends[p]) - 1

print(" ".join(str(results[p]) for p in range(1, n + 1)))

Submission status: Runtime Error

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


#xの木の根を求める
def root(x,li): 
    if li[x] == x:
        return x
    else:
        li[x] = root(li[x],li)
        return li[x]

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x] = y

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(a-1,b-1,li1)
# for i in range(K):
#     c = CD[i][0]
#     d = CD[i][1]
#     union(c-1,d-1,li2)

mm = [0 for i in range(max(li1))]
for i in range(N):
    m = root(i,li1)
    mm[m-1] += 1


ans = [mm[li1[i]-1]-1 for _ in range(N)]
# print(ans)

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    ans[a-1] -= 1
    ans[b-1] -= 1


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)

Submission status: Runtime Error

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


#xの木の根を求める
def root(x,li): 
    if li[x] == x:
        return x
    else:
        li[x] = root(li[x],li)
        return li[x]

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x] = y

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(a-1,b-1,li1)
# for i in range(K):
#     c = CD[i][0]
#     d = CD[i][1]
#     union(c-1,d-1,li2)

mm = [0 for i in range(max(li1))]
for i in range(N):
    m = root(i,li1)
    mm[m-1] += 1


ans = [mm[li1[i]-1]-1 for _ in range(N)]
# print(ans)

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    ans[a-1] -= 1
    ans[b-1] -= 1


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(ans)

Submission status: Runtime Error

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


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


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

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

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

    print(' '.join(result))


main()

Submission status: Runtime Error

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

L=[[] for i in range(1+n)]
N=[]
Ncnt=[0 for i in range(1+n)]
C=[0 for i in range(1+n)]

for inp in range(m):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)

for inp in range(k):
    a,b=map(int,input().split())
    N.append((a,b))

def tansa(x,gone,color):
    C[x]=color
    for nex in L[x]:
        if nex in gone:
            continue
        else:
            tansa(nex,gone+[nex],color)

now=1
for i in range(1,n):
    if C[i]==0:
        tansa(i,[i],now)
        now+=1

CC=sorted(C)

cnt=0
ccres=[]
for i in range(now):
    ccres.append(CC.index(i))
ccres.append(n+1)
dic={i:ccres[i+1]-ccres[i] for i in range(1,now)}

#print(C)
#print(dic)

for i in range(k):
    if C[N[i][1]] == C[N[i][0]]:
        Ncnt[N[i][1]]+=1
        Ncnt[N[i][0]]+=1

for i in range(1,n):
    print(dic[C[i]]-len(L[i])-Ncnt[i]-1,end=" ")
i=n
print(dic[C[i]]-len(L[i])-Ncnt[i]-1,end="")

Submission status: Runtime Error

Solution code:
def bfs(ind):
    kouho=friends[ind]
    for i in kouho:
        if sans[i]!=-1:
            continue
        sans[i]=sans[ind]
        l[sans[ind]].add(i)
        bfs(i)
n,m,k=list(map(int,input().split()))
f=[list(map(int,input().split())) for _ in range(m)]
friends=[set() for _ in range(n)]
friends_num=list(map(lambda x:len(x),friends))
bl=[list(map(int,input().split())) for _ in range(k)]
l=[{i} for i in range(n)]

for each in f:
    a,b=each
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

block=[set() for _ in range(n)]
for each in bl:
    a,b=each
    block[a-1].add(b-1)
    block[b-1].add(a-1)

sans=[-1 for _ in range(n)]
sans[0]=0
bfs(0)
for i in range(n):
    if sans[i]!=-1:
        continue
    sans[i]=i
    bfs(i)
ans=[0 for _ in range(n)]
for i in range(n):
    tmp=(l[sans[i]]-block[i])-friends[i]-{i}
    ans[i]=tmp
ans=" ".join(map(lambda x: str(len(x)),ans))
print(ans)

Submission status: Runtime Error

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

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

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

for i in range(K):
    a, b = map(int, input().split())
    block[a-1, b-1] = 1
    block[b-1, a-1] = 1
 
distance = shortest_path(friend_link)
friend_candidate = np.where((1e7 > distance) & (distance > 1), 1, 0)
friend_candidate *= 1 - block
friend_candidate_num = friend_candidate.sum(axis=1).astype(str).tolist()
print(" ".join(friend_candidate_num))

Submission status: Runtime Error

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

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

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def n_cc(self):  # 連結成分の数
        A = [i for i in self.parents if i < 0]
        return len(A)

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

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

Submission status: Runtime Error

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

L=[[] for i in range(1+n)]
N=[]
Ncnt=[0 for i in range(1+n)]
C=[0 for i in range(1+n)]

for inp in range(m):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)

for inp in range(k):
    a,b=map(int,input().split())
    N.append((a,b))

def tansa(x,gone,color):
    C[x]=color
    for nex in L[x]:
        if nex in gone:
            continue
        else:
            tansa(nex,gone+[nex],color)

now=1
for i in range(1,n):
    if C[i]==0:
        tansa(i,[i],now)
        now+=1

CC=sorted(C)

cnt=0
ccres=[]
for i in range(now):
    ccres.append(CC.index(i))
ccres.append(n+1)
dic={i:ccres[i+1]-ccres[i] for i in range(1,now)}

#print(C)
#print(dic)

for i in range(k):
    if C[N[i][1]] == C[N[i][0]]:
        Ncnt[N[i][1]]+=1
        Ncnt[N[i][0]]+=1

for i in range(1,n):
    print(dic[C[i]]-len(L[i])-Ncnt[i]-1,end=" ")
i=n
print(dic[C[i]]-len(L[i])-Ncnt[i]-1,end="")

Submission status: Runtime Error

Solution code:
, m, k = [int(x) for x in input().split()]
fr = [i for i in range(n)]
dfr = [[] for i in range(n)]
bl = [[] for i in range(n)]
def deref(a):
    s = []
    while True:
        next = fr[a]
        if next == a:
            break
        s.append(a)
        a = next
    for i in s:
        fr[i] = a
    return a

def merge(a, b):
    #print('merge(',a,b)                                                                
    ra, rb = deref(a), deref(b)
    fr[rb] = ra

for i in range(m):
    a, b = [int(x) - 1 for x in input().split()]
    dfr[a].append(b)
    dfr[b].append(a)
    a, b = min(a, b), max(a, b)
    merge(a, b)
for i in range(n):
    deref(i)
#print(dfr)                                                                             
#print(fr)                                                                              
ss = [[] for i in range(n)]
for i in range(n):
    ss[fr[i]].append(i)
for i in range(k):
    c, d = [int(x) - 1 for x in input().split()]
    bl[c].append(d)
    bl[d].append(c)
    for i in range(n):
    bl[i].sort()
r = []
for i in range(n):
    v = len(ss[fr[i]]) - len(dfr[i]) - 1
    v -= sum(fr[j] == fr[i] for j in bl[i])
    r.append(v)
print(' '.join(str(x) for x in r))