Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

a \neq b.

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

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

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

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

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

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

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

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the answers in order, with space in between.

Sample Input 1

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

Sample Output 1

0 1 0 1

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

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

Sample Input 2

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

Sample Output 2

0 0 0 0 0

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

Sample Input 3

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

Sample Output 3

1 3 5 4 3 3 3 3 1 0



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


Sample output:
0 1 0 1

Submission status: Runtime Error

Solution code:
input = 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)


not_uses = [True] * (n+1)
def get_same_nodes(in_node, gid):
    kids = graphs[in_node]
    rets = []
    for kid in kids:
        if not_uses[kid] is True:
            not_uses[kid] = gid
            rets.append(kid)
            cur_rets = get_same_nodes(kid, gid)
            rets += cur_rets
        else:
            continue
    return rets

def get_graph(start_node, gid):
    not_uses[start_node] = gid
    same_nodes = get_same_nodes(start_node, gid)
    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

graph_i = not_uses

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

    same_nodes, cur_kouhos = get_graph(start_node, gid) 
    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 = [int(x) for x in input().split(" ")]


class Account:
    def __init__(self, id):
        self.id = id
        self.friends = set()
        self.blocks = set()

    def add_friend(self, id):
        self.friends.add(id)

    def add_block(self, id):
        self.blocks.add(id)


nodes = [Account(id=i) for i in range(N)]
for _ in range(M):
    a, b = [int(x) for x in input().split(" ")]
    nodes[a-1].add_friend(b-1)
    nodes[b-1].add_friend(a-1)

for _ in range(K):
    c, d = [int(x) for x in input().split(" ")]
    nodes[c-1].add_block(d-1)
    nodes[d-1].add_block(c-1)


searched = [False for i in range(N)]
def search(node, cluster):
    cluster.add(node.id)
    searched[node.id] = True
    for next_id in node.friends:
        if not searched[next_id]:
            search(nodes[next_id], cluster)

i = 0
blocks = []
while i < N:
    cluster = set()
    search(nodes[i], cluster)
    blocks.append(cluster)
    while True:
        i += 1
        if i >= N:
            break
        if not searched[i]:
            break

result = dict()
for block in blocks:
    for idx in block:
        num = len(block - (nodes[idx].friends | nodes[idx].blocks)) -1  # -1 で自分を除く
        result[idx] = num


answer = " ".join(str(val) for key, val in sorted(result.items()))
print(answer)

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = map(int,input().split())
friends = np.array([list(map(int,input().split())) for i in range(M)])
blocks = np.array([list(map(int,input().split())) for i in range(K)])
friends.sort(axis = 1)
friends -= 1#0始まり
blocks -= 1

# ラベリング
labels = np.zeros(N, dtype=int)
reps = []
maxlabel = 0
for i, j in friends:
    if labels[i] == 0 and labels[j] == 0:#どちらもカラ
        maxlabel += 1
        labels[i] = labels[j] = maxlabel
    elif labels[i] == 0:#iだけカラ
        labels[i] = labels[j]
    elif labels[j] == 0:#jだけカラ
        labels[j] = labels[i]
    elif labels[i] == labels[j]:#スルー
        continue
    else:#衝突
        reps += [[labels[i], labels[j]]]

if len(reps) > 0:
    reps = np.array(reps)
    reps.sort(axis=1)
    ireps = reps[::-1, ::-1]
    for lab1, lab2 in ireps:
        labels[labels == lab1] = lab2

# 集計(blocks)
blist = [[] for _ in range(N)]
for i, j in blocks:
    blist[i] += [j]
    blist[j] += [i]

# 集計(friends)
flist = [[] for _ in range(N)]
for i, j in friends:
    flist[i] += [j]
    flist[j] += [i]

# 集計(cluster)
clist = [[] for _ in range(maxlabel+1)]
for p, lab in enumerate(labels):
    clist[lab] += [p]

# フレンド提案
res = []
for p in range(N):
    lab = labels[p]
    kouhos = clist[lab]
    s = -1
    for kouho in kouhos:
        if kouho not in flist[p] and kouho not in blist[p]:
            s += 1
    res += [s]

# 出力
print(" ".join(list(map(str, res))))

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 = [0] * n
while True:
    visited = [start]
    def deep_first(node):
        temp = []
        for one in node.linked:
            if not nodes[one].visited:
                visited.append(one)
                nodes[one].visited = True 
                temp.append(one)
        for one in temp:
            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 not nodes[i].visited:
            start = i
            break
    if start == -1:
        break

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

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(2147483647)

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.int32)
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:
n, m, k = map(int, input().split())
a_list, b_list, c_list, d_list = [], [], [], []
for _ in range(m):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
for _ in range(k):
    c, d = map(int, input().split())
    c_list.append(c)
    d_list.append(d)

friend_dict = {}
for a, b in zip(a_list, b_list):
    if not(a in friend_dict):
        friend_dict[a] = []
    if not(b in friend_dict):
        friend_dict[b] = []

    friend_dict[a].append(b)
    friend_dict[b].append(a)

friend_dict = dict(sorted(friend_dict.items(), key=lambda x: x[0]))

ans_list = []
for key, value in friend_dict.items():
    ans_list.append(n - len(value) - 1)

for c, d in zip(c_list, d_list):
    ans_list[c-1] -= 1
    ans_list[d-1] -= 1
print(' '.join(map(str, ans_list)))

Submission status: Runtime Error

Solution code:
import sys
N,M,K=map(int,input().split())
s=[[]for i in range(N)]
tn=[0]*N
sys.setrecursionlimit(2000000)
for i in range(M):
    a,b=map(int,input().split())
    s[a-1].append(b)
    s[b-1].append(a)
    tn[a-1]+=1
    tn[b-1]+=1
l=[None]*N
def hu(n,t):
    for i in s[n]:
        if l[i-1]==None:
            l[i-1]=t
            hu(i-1,t)
t=0
for i in range(N):
    if l[i]==None:
        hu(i,t)
        t+=1
c=[0]*t
for i in l:
    c[i]+=1
for i in range(K):
    a,b=map(int,input().split())
    if l[a-1]==l[b-1]:
        tn[a-1]+=1
        tn[b-1]+=1
for i in range(N):
    print(c[l[i]]-tn[i]-1,end=" ")

Submission status: Runtime Error

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

block = [[] for _ in range(N)]
friend = [[] for _ in range(N)]

for i in range(M):
	a_temp,b_temp = list(map(int,input().split()))
	friend[a_temp-1].append(b_temp-1)
	friend[b_temp-1].append(a_temp-1)

for i in range(K):
	a_temp,b_temp = list(map(int,input().split()))
	block[a_temp-1].append(b_temp-1)
	block[b_temp-1].append(a_temp-1)

class graph():
	def __init__(self,friend,block):
		self.friend = friend
		self.block = block
		self.seen = [0]*len(self.friend)
		self.clusters = 0
	
	def dfs(self,i):
		self.seen[i] = self.clusters
		for j in self.friend[i]:
			if self.seen[j] == 0:
				self.dfs(j)
				
	def clustering(self):
		for i in range(len(self.friend)):
			if self.seen[i] == 0:
				self.clusters += 1
				self.dfs(i)

network = graph(friend,block)
network.clustering()

clusters = [[] for _ in range(max(network.seen))]
for i in range(N):
	clusters[network.seen[i]-1].append(i)


ans = 0
for i in range(N):
	ans_temp = len(clusters[network.seen[i]-1])-len(friend[i])
	for j in block[i]:
		if j in clusters[network.seen[i]-1]:
			ans_temp -= 1
	print(ans_temp-1,end = " ")

Submission status: Runtime Error

Solution code:
import collections
import sys
input = sys.stdin.readline
print = sys.stdout.writelines


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

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

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


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

CD = [tuple(map(int, input().split())) for i in range(K)]

tableF = collections.defaultdict(set)
tableB = collections.defaultdict(set)


for c, d in CD:
    tableB[c].add(d)
    tableB[d].add(c)

G = unionFind(N)
for a, b in AB:
    G.unite(a, b)
    tableF[a].add(b)
    tableF[b].add(a)

for i in range(N):
    tableF[i+1].add(i+1)


F = collections.defaultdict(set)
ans = [0]*(N+1)
for i in range(N):
    F[G.root(i)].add(i+1)

for i in range(N):
    ans[i] = len(F[G.root(i)] - tableB[i+1] - tableF[i+1])
ans[-1] = "\n"
print(" ".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(int(1e7))
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:
n, m, k = map(int, input().split())
a_list, b_list, c_list, d_list = [], [], [], []
for _ in range(m):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
for _ in range(k):
    c, d = map(int, input().split())
    c_list.append(c)
    d_list.append(d)

friend_dict = {}
for a, b in zip(a_list, b_list):
    if not(a in friend_dict):
        friend_dict[a] = []
    if not(b in friend_dict):
        friend_dict[b] = []

    friend_dict[a].append(b)
    friend_dict[b].append(a)

friend_dict = dict(sorted(friend_dict.items(), key=lambda x: x[0]))

ans_list = []
for key, value in friend_dict.items():
    ans_list.append(n - len(value) - 1)

for c, d in zip(c_list, d_list):
    ans_list[c-1] -= 1
    ans_list[d-1] -= 1
print(ans_list)

Submission status: Runtime Error

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

am = []
bm = []
ck = []
dk = []
for i in range(m):
    a, b = list(map(int, input().split()))
    am.append(a)
    bm.append(b)
for i in range(k):
    c, d = list(map(int, input().split()))
    ck.append(c)
    dk.append(d)
route = {}
for i in range(n):
    route[i+1] = []
for i in range(m):
    a, b = am[i], bm[i]
    if a not in route:
        route[a] = [b]
    else:
        route[a] = route[a] + [b]
    if b not in route:
        route[b] = [a]
    else:
        route[b] = route[b] + [a]
block = {}

for i in range(n):
    block[i+1] = []


for i in range(k):
    a, b = ck[i], dk[i]
    if a not in block:
        block[a] = [b]
    else:
        block[a] = block[a] + [b]
    if b not in block:
        block[b] = [a]
    else:
        block[b] = block[b] + [a]
buff = {}
for i in range(n):
    friends = []
    def dfs(parent, point):
        if point in parent:
            return
        if point in friends:
            return
        friends.append(point)
        for item in route[point]:
            dfs(parent+[point], item)
    dfs([], i+1)
    buff[i+1] = friends
for i in range(n):
    point = i + 1
    friends = buff[point]
    ans = 0
    for item in friends:
        if item == point:
            continue
        if item in block[point]:
            continue
        if item in route[point]:
            continue
        ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
import networkx as nx


ichi = list(map(int,input().split()))
n = ichi[0]
m = ichi[1]
k = ichi[2]

G = nx.Graph()
for i in range(n):
    G.add_node(i+1)

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

G.add_edges_from(ab)

cd = []
for i in range(k):
    c, d = [int(i) for i in input().split()]
    cd.append((c, d))

ans = [0] * n
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if G.has_edge(i+1, j+1) == False and nx.has_path(G, i+1, j+1) == True:
            if (i+1, j+1) not in cd and (j+1, i+1) not in cd:
                print(i+1, j+1)
                ans[i] += 1

for s in ans:
  print(s, end=" ")
print("")

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = map(int,input().split())
friends = np.array([list(map(int,input().split())) for i in range(M)])
blocks = np.array([list(map(int,input().split())) for i in range(K)])
friends.sort(axis = 1)
friends -= 1#0始まり
blocks -= 1

# ラベリング
labels = np.zeros(N, dtype=int)
reps = []
maxlabel = 0
for i, j in friends:
    if labels[i] == 0 and labels[j] == 0:#どちらもカラ
        maxlabel += 1
        labels[i] = labels[j] = maxlabel
    elif labels[i] == 0:#iだけカラ
        labels[i] = labels[j]
    elif labels[j] == 0:#jだけカラ
        labels[j] = labels[i]
    elif labels[i] == labels[j]:#スルー
        continue
    else:#衝突
        reps += [[labels[i], labels[j]]]

reps = np.array(reps)
reps.sort(axis=1)
ireps = reps[::-1, ::-1]
for lab1, lab2 in ireps:
    labels[labels == lab1] = lab2

# 集計(blocks)
blist = [[] for _ in range(N)]
for i, j in blocks:
    blist[i] += [j]
    blist[j] += [i]

# 集計(friends)
flist = [[] for _ in range(N)]
for i, j in friends:
    flist[i] += [j]
    flist[j] += [i]

# 集計(cluster)
clist = [[] for _ in range(maxlabel+1)]
for p, lab in enumerate(labels):
    clist[lab] += [p]

# フレンド提案
res = []
for p in range(N):
    lab = labels[p]
    kouhos = clist[lab]
    s = -1
    for kouho in kouhos:
        if kouho not in flist[p] and kouho not in blist[p]:
            s += 1
    res += [s]

# 出力
print(" ".join(list(map(str, res))))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(int(1e10))
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:

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 = {}
for g in group.values():
    if not g:
        continue
    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
        ret[node - 1] = size - exclude - 1

for i in range(N):
    print(ret.get(i, 0), end='')
    if i != N - 1:
        print(' ', end='')

Submission status: Runtime Error

Solution code:
N,M,K = map(int,input().split())
AB = []
for _ in range(M):
    AB.append([int(i) for i in input().split()])
CD = []
for _ in range(K):
    CD.append([int(i) for i in input().split()])
from collections import defaultdict as ddict
friend = ddict(list)
for ab in AB:
    friend[ab[0]].append(ab[1])
    friend[ab[1]].append(ab[0])
block = ddict(list)
for cd in CD:
    block[cd[0]].append(cd[1])
    block[cd[1]].append(cd[0])
from collections import deque
group = []
done = set()
for n in range(1,N):
    if n in done:
        pass
    else:
        group.append([])
        q = deque([n])
        while q:
            target = q.pop()
            for f in friend[target]:
                if f not in group[-1]:
                    q.append(f)
                    group[-1].append(f)
                    done.add(f)
group_fix = []
for g in group:
    group_fix.append(set(g))
ans = []
for n in range(1,N+1):
    for g in group_fix:
        if n in g:
            temp = g - (set(block[n]) + set(friend[n]) + set([n]))
            ans.append(len(temp))
            break
        else:
            pass
print(*ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N,M,K = MI()
	frend = [[] for _ in range(N)]
	block = [[] for _ in range(N)]
	for _ in range(M):
		A,B = map(int1, sys.stdin.readline().split())
		frend[A].append(B)
		frend[B].append(A)
	group = []
	que = deque()
	cnt = 0
	N_ch = [-1]*N
	g = -1
	while cnt < N:
		que.append(N_ch.index(-1))
		g+=1
		N_ch[i]=g
		group.append(0)
		while len(que)>0:
			i = que[-1]
			cnt += 1
			que.pop()
			group[g]+=1
			fr = frend[i]
			for f in fr:
				if(N_ch[f]==-1):
					que.appendleft(f)
					N_ch[f]=g

	for _ in range(K):
		C,D = map(int1, sys.stdin.readline().split())
		if(N_ch[C]==N_ch[D]):
			block[C].append(D)
			block[D].append(C)

	ans_v = []
	for i in range(N):
		ans = group[N_ch[i]]-len(frend[i])-len(block[i])
		ans_v.append(ans-1)
	printH(ans_v)

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)

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 UnionFind(object):
    def __init__(self, n=1):
        self.root = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.root[y] = x

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


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

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

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

for i in range(N):
    uf1.find(i)  # 一周findすることによって接続漏れをなくす

group = [None] * N
done_member = set()
for i in range(N):
    if i in done_member:
        break
    else:
        done_member.add(i)
    same_group_set = set([i])
    for j in range(N):
        if uf1.is_same_root(i,j):
            same_group_set.add(j)
            done_member.add(j)
    for k in same_group_set:
        group[k] = same_group_set

ans = [(len(group[i] - set(friend[i]) - set(block[i])) - 1) for i in range(N)]
print(*ans)

Submission status: Runtime Error

Solution code:
N, M, K = [int(x) for x in input().split(" ")]


class Account:
    def __init__(self, id):
        self.id = id
        self.friends = set()
        self.blocks = set()

    def add_friend(self, id):
        self.friends.add(id)

    def add_block(self, id):
        self.blocks.add(id)


nodes = [Account(id=i) for i in range(N)]
for _ in range(M):
    a, b = [int(x) for x in input().split(" ")]
    nodes[a-1].add_friend(b-1)
    nodes[b-1].add_friend(a-1)

for _ in range(K):
    c, d = [int(x) for x in input().split(" ")]
    nodes[c-1].add_block(d-1)
    nodes[d-1].add_block(c-1)


searched = [False for i in range(N)]
def search(node, cluster):
    cluster.add(node.id)
    searched[node.id] = True
    for next_id in node.friends:
        if not searched[next_id]:
            search(nodes[next_id], cluster)

i = 0
blocks = []
while i < N:
    cluster = set()
    search(nodes[i], cluster)
    blocks.append(cluster)
    while True:
        if i >= N:
            break
        if not searched[i]:
            break
        i += 1

result = dict()
for block in blocks:
    for idx in block:
        num = len(block - (nodes[idx].friends | nodes[idx].blocks)) -1  # -1 で自分を除く
        result[idx] = num


answer = " ".join(str(val) for key, val in sorted(result.items()))
print(answer)

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 = [0] * 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 
                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 not nodes[i].visited:
            start = i
            break
    if start == -1:
        break

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