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:
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
import numpy as np

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

friend = np.zeros(shape=(N,N))
num_friend = np.zeros(N)
for i in range(M):
    A, B = map(int, raw_input().split())
    friend[A-1, B-1] = 1
    friend[B-1, A-1] = 1
    num_friend[A-1] = num_friend[A-1] + 1
    num_friend[B-1] = num_friend[B-1] + 1
#    print "hey:", A, B                                                                                                                     

num, labels = connected_components(friend)
labels = list(labels)

#print "--labels--"                                                                                                                         
#print labels                                                                                                                               

#print "--friend--"                                                                                                                         
#print friend                                                                                                                               

num_block = np.zeros(N)
for i in range(K):
    C, D = map(int, raw_input().split())
    if labels[C-1] == labels[D-1]:
        num_block[C-1] = num_block[C-1] + 1
        num_block[D-1] = num_block[D-1] + 1

#print "--ans---"                                                                                                                           
answers = []
for i in range(N):
    label = labels[i]
    num_group = labels.count(label)
    num_f = num_friend[i]
    num_b = num_block[i]

    ans = (num_group - 1) - num_f - num_b
    answers.append(int(ans))

#    print i, num_group, int(num_f), int(num_b), int(ans)                                                                                   
print(' '.join(map(str, answers)))

Submission status: Runtime Error

Solution code:
friend_dic = {}
block_dic = {}

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

for i in range(N):
    friend_dic[i+1] = []
    block_dic[i+1] = []

for _ in range(M):
    a, b = map(int, input().split())
    friend_dic[a].append(b)
    friend_dic[b].append(a)

for _ in range(K):
    a, b = map(int, input().split())
    block_dic[a].append(b)
    block_dic[b].append(a)

def search_friends(n, friends):
    searched.append(n)
    for my_friend in friend_dic[n]:
        if my_friend not in friends:
            friends.append(my_friend)
            search_friends(my_friend, friends)

result = []
clusters = []
searched = []
for i in range(1, N+1):
    friends = []
    if i in searched:
        for cluster in clusters:
            if i in cluster:
                friends_set = cluster
                break
    else:
        search_friends(i, friends)
        friends_set = set(friends)
        clusters.append(friends_set)
    result.append(str(len(friends_set-set(friend_dic[i])-set(block_dic[i])-{i})))

print(" ".join(result))

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, K = map(int, input().split())

friends = {}
for _ in range(M):
    a, b = map(int, input().split())
    # a, b = a - 1, b - 1
    # a, b = min(a, b), max(a, b)
    if friends.get(a) is None:
        friends[a] = set([b])
    else:
        friends[a].add(b)
    if friends.get(b) is None:
        friends[b] = set([a])
    else:
        friends[b].add(a)
blocks = {}
for _ in range(K):
    a, b = map(int, input().split())
    # a, b = a - 1, b - 1
    # a, b = min(a, b), max(a, b)
    # blocks.append((a, b))
    if blocks.get(a) is None:
        blocks[a] = set([b])
    else:
        blocks[a].add(b)
    if blocks.get(b) is None:
        blocks[b] = set([a])
    else:
        blocks[b].add(a)
# print('friends', friends)
# print('blocks', blocks)


def f(c, d):
    l = friends[c]
    # print('c, d, l', c, d, l)
    if len(l) == 0:
        return 0
    while len(l) > 0:
        ll = set()
        for i in l:
            if d in friends[i]:
                return 1
            # print('friends[i]', friends[i])
            ll = ll | friends[i]
        if len(ll) == 0:
            return 0
        print('ll', ll)
        l = ll
    return 0


ans = [0] * (N + 1)
for i in range(1, N + 1):
    if friends.get(i) is None:
        continue
    for j in range(i + 1, N + 1):
        if friends.get(j) is None:
            continue
        if i in friends[j]:
            continue
        if i in blocks[j]:
            continue
        # print('i j', i, j)
        v = f(i, j)
        ans[i] += v
        ans[j] += v
for i in ans[1:]:
    print(i)

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(set)
for ab in AB:
    friend[ab[0]].append(ab[1])
    friend[ab[1]].append(ab[0])
block = ddict(set)
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])
            temp = g - set(friend[n])
            temp = g - set([n])
            ans.append(len(temp))
            break
        else:
            pass
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[i], end='')
    if i != N - 1:
        print(' ', end='')

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

N, M , K = [int(x) for x in input().split()]
AB = []
G_F = [deque([]) for _ in range(N)]
G_B = [deque([]) for _ in range(N)]
G_F_s = [set() for _ in range(N)]
G_B_s = [set() for _ in range(N)]
for _ in range(M):
    AB = [int(x) for x in input().split()]
    G_F[AB[0] - 1].append(AB[1] - 1)
    G_F[AB[1] - 1].append(AB[0] - 1)
    G_F_s[AB[0] - 1].add(AB[1] - 1)
    G_F_s[AB[1] - 1].add(AB[0] - 1)

CD = []
for _ in range(K):
    CD = [int(x) for x in input().split()]

    G_B[CD[0] - 1].append(CD[1] - 1)
    G_B[CD[1] - 1].append(CD[0] - 1)
    G_B_s[CD[0] - 1].add(CD[1] - 1)
    G_B_s[CD[1] - 1].add(CD[0] - 1)

ans = 0
from collections import deque
G_F = deque(G_F)
G_B = deque(G_B)

# グラフの作成(無向グラフでは#を消す)

time = 0
arrive_time = [-1] * (N) # 到着時刻

# 深さ優先探索
def dfs(v, graph):
    global time
    time += 1
    stack = [v]
    arrive_time[v] = time
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive_time[w] < 0:
                time += 1
                arrive_time[w] = time
                stack.append(w) 
        else:
            stack.pop()          
    return arrive_time
arrive_time = dfs(0, G)
if -1 in arrive_time:
    flag = 0
else:
    flag = 1
import copy
ans = [0] * N
for i in range(N - 1):
    for j in range(i + 1, N):
        if j in G_B_s[i] or j in G_F_s[i]:
            continue
        if flag:
            ans[i] += 1
            ans[j] += 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():
    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[i], end='')
    if i != N - 1:
        print(' ', end='')

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
import queue
import numpy as np
import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(b)
    dic[str(b)].append(a)
seen = set()
def BFS(dic,node):
    cc = set()
    q = queue.Queue()
    q.put(node)
    cc.add(node)
    while not q.empty():
        now_node = q.get()
        cc.add(now_node)
        target = set(dic[str(now_node)]) - cc
        for tgt in target:
            q.put(tgt)
    return cc
c_comp=np.zeros((N),dtype='int32')
len_ls = []
var = 1
for i in range(1,N+1):
    if c_comp[i-1] == 0:
        # 連結判定
        tmp = BFS(dic,i)
        c_comp[np.array(list(tmp))-1] = var
        len_ls.append(len(tmp)-1)
        var += 1

if N>=1000:
    assert()
for (a,b) in cd:
    if c_comp[a-1] == c_comp[b-1]:
        dic[str(a)].append(str(b))
        dic[str(b)].append(str(a))
res = [0]*N

for i in range(N):
    res[i] = len_ls[c_comp[i]-1] - len(dic[str(i+1)])
print(*res)

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] = root(y,li)

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:
friend_dic = {}
block_dic = {}

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

for i in range(N):
    friend_dic[i+1] = []
    block_dic[i+1] = []

for _ in range(M):
    a, b = map(int, input().split())
    friend_dic[a].append(b)
    friend_dic[b].append(a)

for _ in range(K):
    a, b = map(int, input().split())
    block_dic[a].append(b)
    block_dic[b].append(a)

def search_friends(n, friends):
    for my_friend in friend_dic[n]:
        if my_friend not in friends:
            friends.append(my_friend)
            search_friends(my_friend, friends)

result = []
clusters = []
for i in range(1, N+1):
    friends = []
    flag = False
    for cluster in clusters:
        if i in cluster:
            friends_set = cluster
            flag = True
            break
    if not flag:
        search_friends(i, friends)
        friends_set = set(friends)
        clusters.append(friends_set)
    result.append(str(len(friends_set-set(friend_dic[i])-set(block_dic[i])-{i})))

print(" ".join(result))

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
import queue
import numpy as np
import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(b)
    dic[str(b)].append(a)
seen = set()
def BFS(dic,node):
    cc = set()
    q = queue.Queue()
    q.put(node)
    cc.add(node)
    while not q.empty():
        now_node = q.get()
        cc.add(now_node)
        target = set(dic[str(now_node)]) - cc
        for tgt in target:
            q.put(tgt)
    return cc
c_comp=np.zeros((N),dtype='int32')
len_ls = []
var = 1
if N>=1000:
    assert()
for i in range(1,N+1):
    if c_comp[i-1] == 0:
        # 連結判定
        tmp = BFS(dic,i)
        c_comp[np.array(list(tmp))-1] = var
        len_ls.append(len(tmp)-1)
        var += 1

for (a,b) in cd:
    if c_comp[a-1] == c_comp[b-1]:
        dic[str(a)].append(str(b))
        dic[str(b)].append(str(a))
res = [0]*N

for i in range(N):
    res[i] = len_ls[c_comp[i]-1] - len(dic[str(i+1)])
print(*res)

Submission status: Runtime Error

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

N, M, K = map(int, input().split())
F = [input().split() for i in range(M)]
bdict = {}
for i in range(K):
  a,b = map(int,input().split())
  a = a - 1
  b = b - 1
  if a not in bdict:
    bdict[a] = set()
  if b not in bdict:
    bdict[b] = set()
  bdict[a].add(b)
  bdict[b].add(a)
u = UnionFind(N)

fdict = {}
for f in F:
  a = int(f[0])-1
  b = int(f[1])-1
  u.union(a, b)
  if a not in fdict:
    fdict[a] = set()
  if b not in fdict:
    fdict[b] = set()
  fdict[a].add(b)
  fdict[b].add(a)
ans = [0]*N
import copy
for r in u.roots():
  mems = set(u.members(r))
  for i in mems:
    memstmp = copy.deepcopy(mems)
    if i in bdict:
      memstmp = memstmp - bdict[i]
    ans[i] = len(memstmp)-1 - len(fdict[i])
fin = ""
for a in ans:
  fin += str(a) + " "
print(fin[:-1])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def root(uft, x):
    if uft[x] == x: return x
    uft[x] = root(uft, uft[x])
    return uft[x]

def union(uft, x, y):
    x = root(uft, x)
    y = root(uft, y)
    if x == y:
        return
    uft[x] = y

def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(set)
    block = defaultdict(set)
    group = defaultdict(set)
    uft = [i for i in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        friend[a].add(b)
        friend[b].add(a)
    for j in range(k):
        c, d = map(int, input().split())
        block[c].add(d)
        block[d].add(c)
    for i in range(1, n+1):
        for j in friend[i]:
            union(uft, j, i)
    for i in range(1, n+1):
        group[root(uft, i)].add(i)
    return ' '.join(str(len(group[uft[i]]-friend[i]-block[i])-1) for i in range(1, n+1))

print(answer())

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
friends = [[] * n for i in range(n)]
for _ in range(m):
    num_from, num_to = map(int, input().split())
    friends[num_from - 1].append(num_to - 1)
    friends[num_to - 1].append(num_from - 1)

blocks = [[] * n for i in range(n)]
for _ in range(k):
    num_from, num_to = map(int, input().split())
    blocks[num_from - 1].append(num_to - 1)
    blocks[num_to - 1].append(num_from - 1)

seen = [False] * n
global count

def dfs(me, now, prev):
    global count
    # vを訪問済にする
    seen[now] = True
    # vから行ける各頂点next_vについて
    for next in friends[now]:
        if next != prev:
            if seen[next]:
                # 探索済の場合はカウントしない
                continue
            # 再帰的に探索
            if next not in friends[me] and next not in blocks[me]:
                count += 1
            dfs(me, next, now)

ans = [0] * n
for i in range(n):
    seen = [False] * n
    count = 0
    dfs(i, i, -1)
    ans[i] = count

print(' '.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
from collections import deque, defaultdict
import bisect
from math import factorial


def update_cluster(cluster, cluster_index, a, b):
    remain_index = cluster[a]
    delete_index = cluster[b]
    if remain_index == delete_index:
        return

    if len(cluster_index[remain_index]) < len(cluster_index[delete_index]):
        remain_index, delete_index = delete_index, remain_index

    movers = cluster_index[delete_index]
    for mover in movers:
        cluster[mover] = remain_index
        cluster_index[remain_index].add(mover)

    del cluster_index[delete_index]


def find_connected(node, edges, visited):
    visited.add(node)

    connected = edges[node] - visited
    for c in connected:
        connected_nodes = find_connected(c, edges, visited)
        for n in connected_nodes:
            visited.add(n)
    return visited


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

    blocks = defaultdict(set)
    edges = defaultdict(set)

    for _ in range(M):
        a, b = map(int, input().split())
        edges[a].add(b)
        edges[b].add(a)
        blocks[a].add(b)
        blocks[b].add(a)

    cluster = {}
    cluster_index = {}
    nodes = set(edges)
    while nodes:
        node = nodes.pop()
        connected = find_connected(node, edges, set())
        index = len(cluster_index)
        for n in connected:
            cluster[n] = index
        cluster_index[index] = connected

        nodes = nodes - connected


    """
    cluster = {i+1: i+1 for i in range(N)}
    cluster_index = {i+1: set([i+1]) for i in range(N)}

    for _ in range(M):
        a, b = map(int, input().split())
        update_cluster(cluster, cluster_index, a, b)
        blocks[a].add(b)
        blocks[b].add(a)
    """

    for _ in range(K):
        c, d = map(int, input().split())
        blocks[c].add(d)
        blocks[d].add(c)

    friends = []
    for idx in range(N):
        p = idx + 1
        index = cluster[p]
        candidates = cluster_index[index]
        num = len(candidates - blocks[p]) - 1
        friends.append(str(num))

    print(" ".join(friends))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
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 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:
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)
sys.exit()
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:
[N,M,K] = list(map(int,input().split()))

F = [[] for i in range(N)]
B = [[] for i in range(N)]

for i in range(M):
    [A0,B0] = list(map(int,input().split()))
    F[A0-1].append(B0)
    F[B0-1].append(A0)
for i in range(K):
    [C0,D0] = list(map(int,input().split()))
    B[C0-1].append(D0)
    B[D0-1].append(C0)


def check(X,L):
    for i in F[X]:
        if ch[i-1]==0:
            ch[i-1]=1
            L.append(i)
            check(i-1,L)
X = []
ch = [0]*N
t = 0
while True:
    if t==N:
        break
    L0 = []
    L0.append(t+1)
    ch[t]=1
    check(t,L0)
    X.append(L0)
    while (t<N)and(ch[t]==1):
        t+=1
output = [0]*N
for i in range(len(X)):
    for j in X[i]:
        output[j-1] = len(X[i]) - len(F[j-1]) - len(set(B[j-1])&set(X[i]))-1

st = ""
for i in range(N-1):
    st += str(output[i]) + " "
st += str(output[N-1])
print(st)

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=np.zeros((n,n),np.bool)
	for i in range(m):
		a=int(inputs[i+1][0])
		b=int(inputs[i+1][1])
		fr.add(st(a,b))
		frSingle[a-1,b-1]=True
		frSingle[b-1,a-1]=True
		
	bl=np.zeros((n,n),np.bool)
	for i in range(k):
		a=int(inputs[i+1+m][0])
		b=int(inputs[i+1+m][1])
		bl[a-1,b-1]=True
		bl[b-1,a-1]=True
	
# 	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]
		mm=members[g-1].copy()
		mm[i0-1]=False
		mm=mm&(~frSingle[i0-1])
		mm=mm&(~bl[i0-1])
		num=mm.sum()
		print(num, end="")
		if i0<n: print(" ", end="")
	
	

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

Submission status: Runtime Error

Solution code:
def main():
    import sys
    from collections import defaultdict
    N, M, K = map(int, sys.stdin.readline().split())

    F = [set() for _ in range(N)]
    B = [set() for _ in range(N)]
    for m in range(M):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a - 1, b - 1
        F[a].add(b)
        F[b].add(a)

    for k in range(K):
        c, d = map(int, sys.stdin.readline().split())
        c, d = c - 1, d - 1
        B[c].add(d)
        B[d].add(c)

    D = defaultdict(set)
    parents = [-1] * N
    visited = set()
    for s in range(N):
        if s in visited:
            continue

        stack = [s]
        D[s].add(s)
        while stack:
            n = stack.pop()
            visited.add(n)
            parents[n] = s
            for to in F[n]:
                if to in visited:
                    continue
                D[s].add(to)
                stack.append(to)

    print(1 / 0)
    ans = [0] * N
    #print(D)
    for i in range(N):
        #print(D[parents[i]] - F[i] - B[i] - {i}, F[i], B[i])
        ans[i] = len(D[parents[i]] - F[i] - B[i] - {i})

    print(*ans, sep=' ')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
friends = [[] * n for i in range(n)]
for _ in range(m):
    num_from, num_to = map(int, input().split())
    friends[num_from - 1].append(num_to - 1)
    friends[num_to - 1].append(num_from - 1)

blocks = [[] * n for i in range(n)]
for _ in range(k):
    num_from, num_to = map(int, input().split())
    blocks[num_from - 1].append(num_to - 1)
    blocks[num_to - 1].append(num_from - 1)

seen = [False] * n
global count

def dfs(me, now, prev):
    global count
    # vを訪問済にする
    seen[now] = True
    # vから行ける各頂点next_vについて
    for next in friends[now]:
        if next != prev:
            if seen[next]:
                # 探索済の場合はカウントしない
                continue
            # 再帰的に探索
            if next not in friends[me] and next not in blocks[me]:
                count += 1
            dfs(me, next, now)

ans = [0] * n
for i in range(n):
    seen = [False] * n
    count = 0
    dfs(i, i, -1)
    ans[i] = count

print(count)