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:
def dfs(F, seen, v):
    seen[v] = True

    for e in F[v]:
        if seen[e]:
            continue
        dfs(F, seen, e)


def solve():
    N, M, K = list(map(int, input(). split()))
    F = [[] for i in range(N)]
    Connections = []
    for i in range(M):
        c = [int(x) - 1 for x in input().split()]
        F[c[0]].append(c[1])
        F[c[1]].append(c[0])
        Connections.append(c)
    B = [[] for i in range(N)]
    for i in range(K):
        b = [int(x)-1 for x in input().split()]
        B[b[0]].append(b[1])
        B[b[1]].append(b[0])

    result = []
    for i in range(N):
        candidates = set([x for x in range(
            N) if x not in F[i] and x not in B[i] and x != i])
        seen = [False] * (N)
        for v in F[i]:
            dfs(F, seen, v)

        want = [candidate for candidate in candidates if seen[candidate]]
        result.append(str(len(want)))

    print(' '.join(result))


if __name__ == "__main__":
    solve()

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]=len(tmp)

"""
ans=" ".join(map(str,ans))
print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

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

    def union(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.par[y] = x

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

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


uf = UnionFind(N)
fr = {}
for _ in range(M):
    a, b = map(int, input().split(" "))
    a -= 1
    b -= 1
    uf.union(a, b)
    if fr.get(a) is not None:
        fr[a] += 1
    else:
        fr[a] = 1

    if fr.get(b) is not None:
        fr[b] += 1
    else:
        fr[b] = 1

bl = {}
for _ in range(K):
    c, d = map(int, input().split(" "))
    c -= 1
    d -= 1
    if not uf.is_same(c, d):
        continue

    if bl.get(c) is not None:
        bl[c] += 1
    else:
        bl[c] = 1

    if bl.get(d) is not None:
        bl[d] += 1
    else:
        bl[d] = 1


for i in range(N):
    s = uf.get_size(i) - 1
    s -= bl.get(i, 0)
    s -= fr.get(i, 0)
    print(s)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, m, k = map(int, input().split())
friend_dict = {}
kouho_list = [[0] * n for i in range(n)]
syuugou = []
for i in range(0, m):
    n1, n2 = map(int, input().split())
    n1 -= 1
    n2 -= 1
    kouho_list[n1][n2] = -1
    kouho_list[n2][n1] = -1
    if n1 in friend_dict:
        friend_dict[n1].append(n2)
    else:
        friend_dict[n1] = [n2]
    if n2 in friend_dict:
        friend_dict[n2].append(n1)
    else:
        friend_dict[n2] = [n1]
for i in range(0, k):
    n1, n2 = map(int, input().split())
    n1 -= 1
    n2 -= 1
    kouho_list[n1][n2] = -1
    kouho_list[n2][n1] = -1
count_list = [0] * n
for i in range(0, n):
    for j in range(i + 1, n):
        if kouho_list[i][j] == -1:
            continue
        if len(set(friend_dict[i]) & set(friend_dict[j])) > 0:
            count_list[i] += 1
            count_list[j] += 1
print(' '.join(map(str, count_list)))

Submission status: Runtime Error

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

n, m, k = (int(i) for i in input().split())
f = np.zeros((n, n))
b = np.zeros((n, n))

for u in range(m):
    x, y = (int(i)-1 for i in input().split())
    f[x, y] = 1
    f[y, x] = 1

for u in range(k):
    x, y = (int(i)-1 for i in input().split())
    b[x, y] = 1
    b[y, x] = 1

cn, cl = connected_components(f)
fb = f + b
result = np.zeros(n)
for i in range(cn):
    size = np.sum([cl == i])
    result[cl == i] = size - 1  - np.sum(fb[cl == i][:, cl == i], axis=1)
result = result.astype(np.int32)
print(*list(result))

Submission status: Runtime Error

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
import numpy as np
def resolve():
    N, M, K = map(int, input().split())
    fri = np.zeros((N, N), np.int64)
    for i in range(M):
        a, b = map(int, input().split())
        fri[a-1][b-1] = 1
        fri[b-1][a-1] = 1
    blo = np.zeros((N, N), np.int64)
    for i in range(K):
        c, d = map(int, input().split())
        blo[c-1][d-1] = 1
        blo[d-1][c-1] = 1

    can = np.zeros((N, N), np.int64)
    for i in range(N):
        vis = [False for _ in range(N)]
        s = [i]
        while len(s) > 0:
            v = s.pop()
            vis[v] = True
            for j, k in enumerate(fri[v]):
                if vis[j] or k == 0:
                    continue
                s.append(j)
                if fri[i][j] != 1 and blo[i][j] != 1 and can[i][j] == 0:
                    can[i][j] = 1
    ans = []
    for i in range(N):
        ans.append(can[i].sum())
    print(*ans, sep=' ')
resolve()

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
friend_list = []
for n in range(0, M):
  friend_list.append(list(map(lambda x: int(x), input().split())))

block_list = []
for n in range(0, K):
  block_list.append(list(map(lambda x: int(x), input().split())))

user = [[0 for i in range(N)] for j in range(N)]
for li in friend_list:
  user[li[0]-1][li[1]-1] = 1
  user[li[1]-1][li[0]-1] = 1

for li in block_list:
  user[li[0]-1][li[1]-1] = -1
  user[li[1]-1][li[0]-1] = -1

for num in range(0, len(user)):
  for n in range(0, len(user[num])):
    if num != n:
      if user[num][n] == 0:
        x = user[num]
        y = user[n]
        for a in range(0, len(x)):
          if x[a] == 1 and y[a] == 1:
            user[num][n] = 10
            user[n][num] = 10

recommend = [0 for i in range(N)]
for num in range(0, len(user)):
  for n in range(0, len(user[num])):
    if user[num][n] == 10:
      recommend[num] += 1

ans = ""
for r in recommend:
  ans += r + " "
print(ans.strip())

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)
        if point in buff:
            for item in buff[point]:
                if item not in friends:
                    friends.append(item)
            return
        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:
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)
        if point in buff:
            for item in buff[point]:
                if item not in friends:
                    friends.append(item)
            return
        for item in route[point]:
            dfs(parent+[point], item)
    dfs([], i+1)
    print(friends)
    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:
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]=len(tmp)
ans=" ".join(map(str,ans))
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
N, M, K = map(int, input().rstrip().split(' '))
friend = {}
block = {}

for i in range(M):
    A, B = map(int, input().rstrip().split(' '))
    try:
        friend[A].append(B)
    except:
        friend[A] = [B]
    try:
        friend[B].append(A)
    except:
        friend[B] = [A]

for i in range(K):
    C, D = map(int, input().rstrip().split(' '))
    try:
        block[C].append(D)
    except:
        block[C] = [D]
    try:
        block[D].append(C)
    except:
        block[D] = [C]

candidates = {}
for i in range(1,N+1):
    cnt = 0
    for j in range(1,N+1):
        if i == j:
            continue
        try:
            if j in block[i]:
                continue
        except:
            pass
        try:
            if j in friend[i]:
                continue
        except:
            pass
        temp = list(range(1,N+1))
        temp.remove(i)
        temp.remove(j)
        iter_tmp = itertools.permutations((temp))
        for tmp in iter_tmp:
            tmp = list(tmp)
            tmp.insert(0,i)
            tmp.append(j)
            flag = 0
            for k in range(len(temp)-1):
                if tmp[k+1] not in friend[tmp[k]]:
                    flag = 1
                    break
            if flag == 0:
                cnt += 1
                break
    candidates[i] = cnt

for i in range(len(candidates)):
    print(candidates[i+1], end='')
    print(' ', end='')

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])
	
	frSingle=np.zeros((n,n),np.bool)
	for i in range(m):
		a=int(inputs[i+1][0])-1
		b=int(inputs[i+1][1])-1
		frSingle[a,b]=True
		frSingle[b,a]=True
		
	bl=np.zeros((n,n),np.bool)
	for i in range(k):
		a=int(inputs[i+1+m][0])-1
		b=int(inputs[i+1+m][1])-1
		bl[a,b]=True
		bl[b,a]=True
	
# 	print(frSingle)
# 	print(bl)
# 	print()
	
	groups=np.arange(n)
	members=np.identity(n, np.bool)
	members=members|frSingle
	for i0 in range(n):
		if frSingle[i0].sum()==0: continue
		i1First=np.where(frSingle[i0])[0][0]
		mm=members[i0]
		if i1First<i0: #into this group
			g=groups[i1First]
			groups[mm]=g
			members[g]=members[g]|mm
			groups[mm]=i0
			members[mm]=members[mm]|mm
		else:
			groups[mm]=i0
			members[mm]=members[mm]|mm
			
	
# 	print(groups)
# 	print(members)
	
# 	print()
	for i0 in range(n):
		g=groups[i0]
		mm=members[g].copy()
		mm[i0]=False
		mm=mm&(~frSingle[i0])
		mm=mm&(~bl[i0])
		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:
import sys
input = sys.stdin.readline

n,m,k= map(int, input().split())
a= [list(map(int, input().split())) for i in range(m)]
c= [list(map(int, input().split())) for i in range(k)]

x= [[] for i in range(n)] # 友達関係のグラフ
y= [[] for i in range(n)] # ブロック関係のグラフ


for i in range(m):
    x[a[i][0]-1].append(a[i][1]-1)
    x[a[i][1]-1].append(a[i][0]-1)

for i in range(k):
    x[a[i][0]-1].append(a[i][1]-1)
    x[a[i][1]-1].append(a[i][0]-1)




# ユニオンファインド
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())

uf=UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1,a[i][1]-1)

ans=[]
for i in range(n):
    ans.append(uf.size(i)-len(x[i])-1)

print(*ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = 10**6


N, M, K = map(int, input().split())
graph = np.zeros((N, N), np.int32)
for _ in range(M):
    A, B = map(int, input().split())
    graph[A-1][B-1] = 1
    graph[B-1][A-1] = 1
for _ in range(K):
    C, D = map(int, input().split())
    graph[C-1][D-1] = inf
    graph[D-1][C-1] = inf


csgraph = csr_matrix(graph)
shortest_paths = shortest_path(csgraph, directed=False, method="BF")


ok = sorted(list(zip(*np.where(graph < inf))))
now = 0
ans = 0
for x, y in ok:
    if x == now:
        if shortest_paths[x][y] > 1:
            ans += 1
    else:
        print(ans, end=" ")
        ans = 0
        now += 1
        while now < x:
            if now != N - 1:
                print(0, end=" ")
            else:
                print(0, end="")
            now += 1
        if shortest_paths[x][y] != 1:
            ans += 1

while now <= N-1:
    if ans != 0:
        print(ans , end=" ")
        continue
    if now != N-1:
        print(0, end=" ")
    else:
        print(0, end="")
    now += 1
print()

Submission status: Runtime Error

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

def dfs(i,now, prev = -1,friend):
	if friends[now] == []:
		return friend
    for next in friends[now]:
        if next == prev:
            continue
		if next not in block[i] and next not in friends[i]:
			friend += 1
        dfs(i,next, now,friend)
for _ in range(m) :
	a,b = map(int,input().split())
	friends[a-1].append(b-1)
	friends[b-1].append(a-1)
for _ in range(k):
	a,b = map(int,input().split())
	block[a-1].append(b-1)
	block[b-1].append(a-1)

sm =[]
for i in range(n):
	sm.append(dfs(i,i,-1,0))

print(*sm)

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)


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 sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N, M, K  = (int(i) for i in input().split())
graph = np.zeros((N+1, N+1))
graph2 = [[0] * (N+1) for i in range(N+1)]

#ABC = [[int(i) for i in input().split()] for i in range(N)]
for i in range(M):
    A, B =  (int(i) for i in input().split())
    graph[A][B] = 1
    graph[B][A] = 1
    graph2[A][B] = 1
    graph2[B][A] = 1

for j in range(K):
    A, B =  (int(i) for i in input().split())
    graph2[A][B] = -1
    graph2[B][A] = -1

#graph = np.array(graph)
#print(graph)
#print(graph2)
n, labels = connected_components(graph)

#print(n)
# 2
#print(labels)

for i in range(1, N+1):
    count = 0
    for j in range(1,N+1):
        if i == j:
            continue
        if graph2[i][j] == 0 and labels[i] == labels[j]:
            #print(i, j)
            count += 1
    print(count)

Submission status: Runtime Error

Solution code:
def dfs(F, seen, v):
    seen[v] = True

    for e in F[v]:
        if e in seen:
            continue
        dfs(F, seen, e)


def solve():
    N, M, K = list(map(int, input(). split()))
    F = [[] for i in range(N)]
    Connections = []
    for i in range(M):
        c = [int(x) - 1 for x in input().split()]
        F[c[0]].append(c[1])
        F[c[1]].append(c[0])
        Connections.append(c)
    B = [[] for i in range(N)]
    for i in range(K):
        b = [int(x)-1 for x in input().split()]
        B[b[0]].append(b[1])
        B[b[1]].append(b[0])

    result = 0
    for i in range(N):
        candidates = set([x for x in range(
            N) if x not in F[i] and x not in B[i] and x != i])
        seen = [False] * (N)
        print(seen)
        for v in F[i]:
            dfs(F, seen, v)

        want = [candidate for candidate in candidates if seen[candidate]]
        result += len(want)

    print(result)


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
friendly = list()
no_friendly = list()
for i in range(M):
    friendly.append(list(map(int, input().split())))
for i in range(K):
    no_friendly.append(list(map(int, input().split())))
  
friendly_dict = dict()
no_friendly_dict = dict()
for i in range(M):
    a = friendly[i][0]
    b = friendly[i][1]
    if a not in friendly_dict.keys():
        friendly_dict[a] = [b]
    else:
        friendly_dict[a].append(b)
    if b not in friendly_dict.keys():
        friendly_dict[b] = [a]
    else:
        friendly_dict[b].append(a)
no_friendly_dict = dict()
for i in range(K):
    a = no_friendly[i][0]
    b = no_friendly[i][1]
    if a not in no_friendly_dict.keys():
        no_friendly_dict[a] = [b]
    else:
        no_friendly_dict[a].append(b)
    if b not in no_friendly_dict.keys():
        no_friendly_dict[b] = [a]
    else:
        no_friendly_dict[b].append(a)
tomodati = [0 for _ in range(N+1)]
for i in range(1,N+1):
    if tomodati[i] == 0:
        tomodati[i] = i
    for k in friendly_dict[i]:
        tomodati[k] = tomodati[i]
from collections import Counter
a = Counter(tomodati)
tomodati_count = [ 0 for i in range(N+1)]
for i in range(1,N+1):
  for k in no_friendly_dict[i]:
    if tomodati[k] == tomodati[i]:
      tomodati_count[i] -= 1
  

for i in range(1, N+1):
    tomodati_count[i] = a[tomodati[i]] - len(friendly_dict[i])

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)
        if point in buff:
            for item in buff[point]:
                if item not in friends:
                    friends += item
            return
        for item in route[point]:
            dfs(parent+[point], item)
    dfs([], i+1)
    print(friends)
    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 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 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:
from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1]*(n+1)

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

    def union(self, x, y):
        if not self.same_check(x, y):
            x = self.find(x)
            y = self.find(y)
            self.size[x] += self.size[y]
            self.size[y] += self.size[x]

        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))


N, M, K = l_in()

uni = UnionFind(N)

friends = defaultdict(set)

for _ in range(N):
    a,b = l_in()
    uni.union(a-1, b-1)
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

blocks = defaultdict(set)

for _ in range(K):
    c,d = l_in()
    blocks[c-1].add(d-1)
    blocks[d-1].add(c-1)



res = []

for i in range(N):
    uni.find(i)
    n = uni.size[i]-1
    for f in friends[i]:
        if uni.same_check(i, f):
            n-=1

    for f in blocks[i]:
        if uni.same_check(i, f):
            n-=1


    res.append(n)

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

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(200000)
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:
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+1 for i in range(N)]
li2 = [i+1 for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(min(a-1,b-1),max(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:
n,m,k=map(int,input().split())
f={i:set([]) for i in range(n)}
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  f[a].add(b)
  f[b].add(a)
b={i:set([]) for i in range(n)}
for _ in range(k):
  c,d=map(int,input().split())
  c-=1
  d-=1
  b[c].add(d)
  b[d].add(c)
joined=set([])
def append_friends(j):
  if j in friends:
    return
  friends.add(j)
  s=f[j]
  for a in s:
    append_friends(a)
  return 
dp=[]
result=[]
for i in range(n):
  if i in joined:
    for j in dp:
      if i in j:
        result.append(j)
        break
    continue
  friends=set([])
  append_friends(i)
  dp.append(friends)
  result.append(friends)
  joined=joined|friends
ans=[0]*n
for i in range(n):
  ans[i]=str(len(result[i]-b[i]-f[i]-{i}))
print(" ".join(ans))