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(cur_node, candidates, visited, level, cnt):

  while len(candidates) > 0:
    node, level = candidates.pop(0)

    if visited[node]: continue
    visited[node] = True

    if level > 0: cnt += 1

    for n in adj_list[node][FRIEND]:
      if n in adj_list[cur_node][BLOCK]:
        candidates.append((n, 0))
      if visited[n] == False:
        candidates.append((n, level+1))

  return cnt

# -----------------------------------------

FRIEND, BLOCK = 0, 1

N, F, B = list(map(int, input().split()))
adj_list = defaultdict(dict)
for i in range(1, N+1):
  adj_list[i][0] = set()
  adj_list[i][1] = set()

for _ in range(F):
  u, v = list(map(int, input().split()))
  adj_list[u][FRIEND].add(v)
  adj_list[v][FRIEND].add(u)

for _ in range(B):
  u, v = list(map(int, input().split()))
  adj_list[u][BLOCK].add(v)
  adj_list[v][BLOCK].add(u)

ans = []

for i in range(1, N+1):
  visited = [False] * (N+1)
  visited[i] = True
  candidates = []
  for node in adj_list[i][FRIEND]:
    # if status == FRIEND:
    # node, level
    candidates.append((node, 0))

  cnt = 0
  cnt = dfs(i, candidates, visited, 0, 0)
  ans.append(cnt)

print(" ".join([str(i) for i in ans]))

Submission status: Runtime Error

Solution code:
def dfs(cur_node, candidates, visited, level, cnt):

  while len(candidates) > 0:
    node, level = candidates.pop(0)

    if visited[node]: continue
    visited[node] = True

    if level > 0: cnt += 1

    for n in adj_list[node][FRIEND]:
      if n in adj_list[cur_node][BLOCK]:
        candidates.append((n, 0))
      if visited[n] == False:
        candidates.append((n, level+1))

  return cnt

# -----------------------------------------

FRIEND, BLOCK = 0, 1

N, F, B = list(map(int, input().split()))
adj_list = defaultdict(dict)
for i in range(1, N+1):
  adj_list[i][0] = set()
  adj_list[i][1] = set()

for _ in range(F):
  u, v = list(map(int, input().split()))
  adj_list[u][FRIEND].add(v)
  adj_list[v][FRIEND].add(u)

for _ in range(B):
  u, v = list(map(int, input().split()))
  adj_list[u][BLOCK].add(v)
  adj_list[v][BLOCK].add(u)

ans = []

for i in range(1, N+1):
  visited = [False] * (N+1)
  visited[i] = True
  candidates = []
  for node in adj_list[i][FRIEND]:
    # if status == FRIEND:
    # node, level
    candidates.append((node, 0))

  cnt = 0
  cnt = dfs(i, candidates, visited, 0, 0)
  ans.append(cnt)

print(ans)

Submission status: Runtime Error

Solution code:
def dfs(cur_node, candidates, visited, level, cnt):

  while len(candidates) > 0:
    node, level = candidates.pop(0)

    if visited[node]: continue
    visited[node] = True

    if level > 0: cnt += 1
    print(cur_node, node, cnt)

    for n in adj_list[node][FRIEND]:
      if n in adj_list[cur_node][BLOCK]:
        candidates.append((n, 0))
      if visited[n] == False:
        candidates.append((n, level+1))

  return cnt

# -----------------------------------------

FRIEND, BLOCK = 0, 1

N, F, B = list(map(int, input().split()))
adj_list = defaultdict(dict)
for i in range(1, N+1):
  adj_list[i][0] = set()
  adj_list[i][1] = set()

for _ in range(F):
  u, v = list(map(int, input().split()))
  adj_list[u][FRIEND].add(v)
  adj_list[v][FRIEND].add(u)

for _ in range(B):
  u, v = list(map(int, input().split()))
  adj_list[u][BLOCK].add(v)
  adj_list[v][BLOCK].add(u)

print(adj_list)
ans = []

for i in range(1, N+1):
  visited = [False] * (N+1)
  visited[i] = True
  candidates = []
  for node in adj_list[i][FRIEND]:
    # node, level
    candidates.append((node, 0))

  cnt = 0
  cnt = dfs(i, candidates, visited, 0, 0)
  ans.append(cnt)

print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
N,M,K = map(int,input().split())
f = [[] for _ in range(N+1)]
b = [[] for _ in range(N+1)]
for i in range(M):
    x,y = map(int,input().split())
    f[x].append(y)
    f[y].append(x)

d = [None]*(N+1)

def dfs(f,s,id):
    if(d[s] is None):
        d[s] = id
    for i in f[s]:
        if(d[i] is not None):
            continue
        dfs(f,i,id)
         
cnt = -1
for j in range(1,N+1):
    if(d[j] == None):
        cnt += 1
        dfs(f,j,cnt)
    
for i in range(K):
    x,y = map(int,input().split())
    if(d[x] == d[y]):
        b[x].append(y)
        b[y].append(x)

c = Counter(d)
for i in range(1,N+1):
    print(c[d[i]] - len(f[i]) - len(b[i])-1)

Submission status: Runtime Error

Solution code:
from collections import Counter
N,M,K = map(int,input().split())
f = [[] for _ in range(N+1)]
b = [[] for _ in range(N+1)]
for i in range(M):
    x,y = map(int,input().split())
    f[x].append(y)
    f[y].append(x)

d = [None]*(N+1)

def dfs(f,s,id):
    if(d[s] is None):
        d[s] = id
    for i in f[s]:
        if(d[i] is not None):
            continue
        dfs(f,i,id)
         
cnt = -1
for j in range(1,N):
    if(d[j] == None):
        cnt += 1
        dfs(f,j,cnt)
    
for i in range(K):
    x,y = map(int,input().split())
    if(d[x] == d[y]):
        b[x].append(y)
        b[y].append(x)
    
c = Counter(d)
for i in range(1,N+1):
    print(c[d[i]] - len(f[i]) - len(b[i])-1)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [-1] * n
        # rank
        #self.rank = [0] * n
        self.size = [1] * n

    def find(self, x):
        # 根の番号を返す(所属する集合を確認する)
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def check(self, x, y):
        # x,yが同じ集合に属するかどうか調べる
        return self.find(x) == self.find(y)


    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        self.par[y]=x
        self.size[x]+=self.size[y]

import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
uf=UnionFind(n)
out=[[] for i in range(n)]

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

for i in range(k):
    c,d=map(int,input().split())
    if uf.check(c-1,d-1):
        out[c-1].append(d-1)
        out[d-1].append(c-1)

for i in range(n):
    ans=uf.size[uf.find(i)]-1-len(out[i])
    print(ans,end=' ')

Submission status: Runtime Error

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

H = [[] for i in range(N + 1)]
count = [0] * (N)

# 友達マップ
for i in range(M):
  A, B = map(int, input().split())
  H[A].append(B)
  H[B].append(A)
  
# ブロックマップ
for i in range(K):
  C, D = map(int, input().split())
  H[C].append(-D)
  H[D].append(-C)

# 友達候補探索
def get_friend(parent, target):
  if target in checked or target == parent:
    return
  checked.append(target)
  
  for s in H[target]:
    if s > 0 and (s == parent or s in counted or s in H[parent] or -s in H[parent]) == False:
      count[parent - 1] += 1
      counted.append(s)
    if s > 0 and (s == parent or s in checked) == False:
      get_friend(parent, s)

for i in range(1, N + 1):
  checked = []
  counted = []
  for j in H[i]:
    if j > 0:
      get_friend(i, j)

print (str(count).replace(',', '').replace('[', '').replace(']', ''))

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(1000000)
input = lambda: sys.stdin.readline().rstrip()


class UnionFind:
    def __init__(self, size):
        self.par = [i for i in range(size)]
        self.rk = [0] * size

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rk[x] < self.rk[y]:
            self.par[x] = y
        elif self.rk[x] > self.rk[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            self.rk[y] += 1


N, M, K = map(int, input().split())
uf = UnionFind(N)
friend = defaultdict(set)
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    uf.unite(a, b)
    friend[a].add(b)
    friend[b].add(a)

block = defaultdict(set)
for _ in range(K):
    c, d = map(lambda x: int(x) - 1, input().split())
    block[c].add(d)
    block[d].add(c)

group = defaultdict(set)
for i in range(N):
    group[uf.find(i)].add(i)

ans = [0] * N
for people in group.values():
    for p in people:
        ans[p] = len(people) - 1 - sum(1 if i in people else 0 for i in friend[p]) - sum(1 if i in people else 0 for i in block[p])

print(' '.join(ans))

Submission status: Runtime Error

Solution code:
import sys
from collections import deque,defaultdict
N,M,K=map(int,input().split())
good=defaultdict(list)
bad=defaultdict(list)
for i in range(M):
  a,b=map(int,input().split())
  good[a].append(b)
  good[b].append(a)
for i in range(K):
  a,b=map(int,input().split())
  bad[a].append(b)
  bad[b].append(a)
  
unvisited=[i for i in range(1,N+1)]
partial_graph=defaultdict(int)      # 各頂点が属する連結成分に添字を振って保持
graph_size=defaultdict(int)         # 上のindexと連結成分のサイズを対応づける
index=0
def connected(unvisited,partial_graph,graph_size,index):
  if len(unvisited)==0:
    return [partial_graph,graph_size]
  s=unvisited.pop(0)
  stack=deque()
  seen=[]
  stack.append(s)
  seen.append(s)
  while len(stack)!=0:
    u=stack.pop()
    for v in good[u]:
      if v not in seen:
        seen.append(v)
        stack.append(v)
        if v in unvisited:
           unvisited.remove(v)
  for v in seen:
    partial_graph[v]=index
    graph_size[index]=len(seen)
  index+=1
  return connected(unvisited,partial_graph,graph_size,index)
w=connected(unvisited,partial_graph,graph_size,index)
partial_graph,graph_size=w[0],w[1]
ans='' 
for u in range(1,N+1):
  cnt=0
  for v in good[u]:
    if partial_graph[u]==partial_graph[v]:
      cnt+=1
  for v in bad[u]:
    if partial_graph[u]==partial_graph[v]:
      cnt+=1
  index=partial_graph[u]
  size=graph_size[index]
  ans+=' '+str(size-cnt-1)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque,defaultdict
N,M,K=map(int,input().split())
good=defaultdict(list)
bad=defaultdict(list)
for i in range(M):
  a,b=map(int,input().split())
  good[a].append(b)
  good[b].append(a)
for i in range(K):
  a,b=map(int,input().split())
  bad[a].append(b)
  bad[b].append(a)
  
unvisited=[i for i in range(1,N+1)]
partial_graph=defaultdict(int)      # 各頂点が属する連結成分に添字を振って保持
graph_size=defaultdict(int)         # 上のindexと連結成分のサイズを対応づける
index=0
def connected(unvisited,partial_graph,graph_size,index):
  if len(unvisited)==0:
    return [partial_graph,graph_size]
  s=unvisited.pop(0)
  stack=deque()
  seen=[]
  stack.append(s)
  seen.append(s)
  while len(stack)!=0:
    u=stack.pop()
    for v in good[u]:
      if v not in seen:
        seen.append(v)
        stack.append(v)
        if v in unvisited:
           unvisited.remove(v)
  for v in seen:
    partial_graph[v]=index
    graph_size[index]=len(seen)
  index+=1
  return connected(unvisited,partial_graph,graph_size,index)
w=connected(unvisited,partial_graph,graph_size,index)
partial_graph,graph_size=w[0],w[1]
ans='' 
exclude=defaultdict(int)
for u in range(1,N+1):
  cnt=0
  for v in good[u]:
    if partial_graph[u]==partial_graph[v]:
      cnt+=1
  for v in bad[u]:
    if partial_graph[u]==partial_graph[v]:
      cnt+=1
  exclude[u]=cnt
for i in range(1,N+1):
  index=partial_graph[i]
  size=graph_size[index]
  ans+=' '+str(size-exclude[i]-1)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

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


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

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

    def root_and_depth(self, x, i=0):
        if self.parent[x] == x:
            return x, i
        return self.root(self.parent[x]), i + 1

    def unite(self, x, y):
        rx, ix = self.root_and_depth(x)
        ry, iy = self.root_and_depth(y)
        if rx != ry:
            if ix < iy:
                self.parent[rx] = ry
            else:
                self.parent[ry] = rx


uf = UnionFind(N)

for a, b in AB:
    uf.unite(a - 1, b - 1)

roots = [uf.root(i) for i in range(N)]
counter_roots = Counter(roots)

ans = [counter_roots[roots[i]] - 1 for i in range(N)]

for a, b in AB:
    if roots[a - 1] == roots[b - 1]:
        ans[a - 1] -= 1
        ans[b - 1] -= 1
for a, b in CD:
    if roots[a - 1] == roots[b - 1]:
        ans[a - 1] -= 1
        ans[b - 1] -= 1

print(*ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

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


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.parent[rx] = ry


uf = UnionFind(N)

for a, b in AB:
    uf.unite(a - 1, b - 1)

roots = [uf.root(i) for i in range(N)]
counter_roots = Counter(roots)

ans = [counter_roots[roots[i]] - 1 for i in range(N)]

for a, b in AB:
    if roots[a - 1] == roots[b - 1]:
        ans[a - 1] -= 1
        ans[b - 1] -= 1
for a, b in CD:
    if roots[a - 1] == roots[b - 1]:
        ans[a - 1] -= 1
        ans[b - 1] -= 1

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

Submission status: Runtime Error

Solution code:
from collections import Counter

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


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.parent[rx] = ry


uf = UnionFind(N)

for a, b in AB:
    uf.unite(a - 1, b - 1)

roots = [uf.root(i) for i in range(N)]
counter_roots = Counter(roots)

ans = [counter_roots[roots[i]] - 1 for i in range(N)]

for a, b in AB:
    if roots[a - 1] == roots[b - 1]:
        ans[a - 1] -= 1
        ans[b - 1] -= 1
for a, b in CD:
    if roots[a - 1] == roots[b - 1]:
        ans[a - 1] -= 1
        ans[b - 1] -= 1

print(*ans)

Submission status: Runtime Error

Solution code:
s = list(map(int,input().split()))
n=s[0]
m=s[1]
k=s[2]
par={}
brock={}
friend={}
group={}
be_friend=[]
for i in range(1,n+1):
    par[i]=[i,0]
    brock[i]=[]
    friend[i]=[]
    group[i]=[]

def root(x,depth):
    if par[x][0]==x:
        return [x,depth]
    else:
        depth+=1
        par[x]=root(par[x][0],depth)
        return root(par[x][0],depth)

for i in range(m):
    s = list(map(int, input().split()))
    # 根と根をくっ付ける
    a=s[0]
    b=s[1]
    ra,_=root(a,0)
    rb,db=root(b,0)
    par[rb]=[ra,db]
    friend[a].append(b)
    friend[b].append(a)

for i in range(k):
    s = list(map(int, input().split()))
    a = s[0]
    b = s[1]
    brock[a].append(b)
    brock[b].append(a)

for i in range(1,n+1):
    group[par[i][0]].append(i)

# 答え出力
for i in range(1,n+1):
    b=len(brock[i])
    f = len(friend[i])
    g=len(group[par[i][0]])
    be_friend.append(g-f-b-1)
for i in range(n):
    print(be_friend[i],end=' ')

Submission status: Runtime Error

Solution code:
import queue
 
N,M,K=map(int,input().split())
friend=[[] for i in range(N)]
block=[[] for i in range(N)]
color=[-1]*N
c=0
for i in range(M):
    a,b=map(int,input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
for i in range(K):
    c,d=map(int,input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)
 
q=queue.Queue()
count=[0]*N
 
for i in range(N):
    if color[i]==-1:
        q.put(i)
        color[i]=c
        count[c]+=1
        while not q.empty():
            s=q.get()
            for t in friend[s]:
                if color[t]==-1:
                    color[t]=c
                    count[c]+=1
                    q.put(t)
        c+=1
 
for i in range(N):
    block_in_color=0
    for t in block[i]:
        if color[i]==color[t]:
            block_in_color+=1
    print(count[color[i]]-len(friend[i])-block_in_color-1)

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for i in range(N)]
 
    def merge(self, a, b):
        if self.issame(a,b):
            return
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
        self.size[pb] += self.size[pa]
    
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
    def issame(self, x, y):
        return self.root(x) == self.root(y)
    def getsize(self, x):
        return self.size[self.root(x)]
uf=UnionFind(n)
ans=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    uf.merge(a-1,b-1)
    ans[a-1]-=1;ans[b-1]-=1
for i in range(k):
    c,d=map(int,input().split())
    if uf.issame(c-1,d-1):
        ans[c-1]-=1;ans[d-1]-=1
for i in range(n):
    ans[i]=uf.getsize(i)+ans[i]-1
print(*ans)

Submission status: Runtime Error

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

#print(AB)

def dfs(relation, start):
  visited = []
  stack = []
  stack.append(start)
  result = []
  while len(stack) > 0:
    next_node = stack.pop()
    if next_node in visited:
      continue
    result.append(next_node)
    visited.append(next_node)
    for nei in relation[np.any(relation==next_node, axis=1), :]:
      if nei[0]!=next_node:
        stack.append(nei[0])
      elif nei[1]!=next_node:
        stack.append(nei[1])
  return np.array(result)

def connected_components(relation, N):
    visited = []
    result = []
    for node in range(1, N+1):
        if node in visited:
            continue
        component = dfs(relation, node)
        result.append(component)
        for node2 in component:
            visited.append(node2)
    return np.array(result)

#res = dfs(AB, 1)
#print(res)

#res2 = connected_components(AB, N)
#print(res2)

visited = []
result = []
for node in range(1, N+1):
    if node in visited:
      for comp in result:
        if node in comp:
          component = comp 
          break
    else:
      component = dfs(AB, node)
    #print(component)
    fb_counts = 0
    for j in component:
      if j==node:
        continue
      friend = [np.all([node,j]==z)|np.all([j,node]==z) for z in AB]
      block = [np.all([node,j]==z)|np.all([j,node]==z) for z in CD]
      if any(friend) or any(block):
        fb_counts += 1
    ans = len(component) - fb_counts - 1 
    print(ans, end=' ')
    result.append(component)
    for node2 in component:
        visited.append(node2)

Submission status: Runtime Error

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

#print(AB)

def dfs(relation, start):
  visited = []
  stack = []
  stack.append(start)
  result = []
  while len(stack) > 0:
    next_node = stack.pop()
    if next_node in visited:
      continue
    result.append(next_node)
    visited.append(next_node)
    for nei in relation[np.any(relation==next_node, axis=1), :]:
      if nei[0]!=next_node:
        stack.append(nei[0])
      elif nei[1]!=next_node:
        stack.append(nei[1])
  return np.array(result)

def connected_components(relation, N):
    visited = []
    result = []
    for node in range(1, N+1):
        if node in visited:
            continue
        component = dfs(relation, node)
        result.append(component)
        for node2 in component:
            visited.append(node2)
    return np.array(result)

#visited = []
#result = []
for node in range(1, N+1):
    #if node in visited:
        #continue
    component = dfs(AB, node)
    #print(component)
    fb_counts = 0
    for j in component:
      if j==node:
        continue
      friend = [np.all([node,j]==z)|np.all([j,node]==z) for z in AB]
      block = [np.all([node,j]==z)|np.all([j,node]==z) for z in CD]
      if any(friend) or any(block):
        fb_counts += 1
    ans = len(component) - fb_counts - 1 
    print(ans, end=' ')

Submission status: Runtime Error

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

def dfs(relation, start):
  visited = []
  stack = []
  stack.append(start)
  result = []
  while len(stack) > 0:
    next_node = stack.pop()
    if next_node in visited:
      continue
    result.append(next_node)
    visited.append(next_node)
    for nei in relation[np.any(relation==next_node, axis=1), :]:
      if nei[0]!=next_node:
        stack.append(nei[0])
      elif nei[1]!=next_node:
        stack.append(nei[1])
  return np.array(result)

def connected_components(relation, N):
    visited = []
    result = []
    for node in range(1, N+1):
        if node in visited:
            continue
        component = dfs(relation, node)
        result.append(component)
        for node2 in component:
            visited.append(node2)
    return np.array(result)


cc = connected_components(AB, N)

for i in range(1, N+1):
  for k in cc:
    if i in k:
      x = k
      break
      
  fb_counts = 0
  for j in x:
    if j==i:
      continue
    friend = [np.all([i,j]==z)|np.all([j,i]==z) for z in AB]
    block = [np.all([i,j]==z)|np.all([j,i]==z) for z in CD]
    if any(friend) or any(block):
      fb_counts += 1
      
  ans = len(x) - fb_counts - 1 
  print(ans, end=' ')

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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

    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)

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)]
uf = UnionFind(N)
fblist = [0] * (N+1)

for i in range(M):
    A, B =  (int(i) for i in input().split())
    uf.union(A, B)
    fblist[A] += 1
    fblist[B] += 1
 
for j in range(K):
    A, B =  (int(i) for i in input().split())
    fblist[A] += 1
    fblist[B] += 1

for i in range(1, N+1):
    print(uf.size(i) - fblist[i] - 1, end=" ")

print()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

n, m, k = input().strip().split()
n, m, k = int(n), int(m), int(k)
friends = [0] + [[] for _ in range(n)]
blocks = [0] + [[] for _ in range(n)]

for _ in range(m):
    p1, p2 = input().strip().split()
    p1, p2 = int(p1), int(p2)
    friends[p1].append(p2)
    friends[p2].append(p1)
for _ in range(k):
    p1, p2 = input().strip().split()
    p1, p2 = int(p1), int(p2)
    blocks[p1].append(p2)
    blocks[p2].append(p1)

connected_num = 0
def dfs(graph, current, seen, connected_id):
    global connected_num
    seen[current] = connected_id
    connected_num += 1

    children = graph[current]
    for c in children:
        if seen[c] != -1:
            continue
        dfs(graph, c, seen, connected_id)

seen = [-1] * (n + 1)
connected_id = 0
connected = []
for i in range(1, n + 1):
    if seen[i] != -1:
        continue
    dfs(friends, i, seen, connected_id)
    connected.append(connected_num)
    connected_num = 0
    connected_id += 1

ans = []
for i in range(1, n + 1):
    i_connected_id = seen[i]
    exclude = 0
    for f in friends[i]:
        f_connected_id = seen[f]
        if i_connected_id == f_connected_id:
            exclude += 1
    for b in blocks[i]:
        b_connected_id = seen[b]
        if i_connected_id == b_connected_id:
            exclude += 1
    ans.append(str(connected[i_connected_id] - exclude - 1))

print(' '.join(ans))

Submission status: Runtime Error

Solution code:

n,m,k=map(int,input().split())
friend=[(0,0) for _ in range(2*m)]
blockd=[(0,0) for _ in range(2*k)]
for idx in range(m):
  i,j=(map(int,input().split()))
  friend[2*idx  ]=(i-1,j-1)
  friend[2*idx+1]=(j-1,i-1)
for idx in range(k):
  i,j=(map(int,input().split()))
  blockd_r[2*idx  ]=(i-1,j-1)
  blockd_r[2*idx+1]=(j-1,i-1)
print(friend,n,labels,np.unique(labels,return_counts=True),friend.sum(axis=0)+blockd.sum(axis=0))
for i in range(1,n+1):
  pass

Submission status: Runtime Error

Solution code:
import sys
sys.getrecursionlimit(10**6)

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

par = [i for i in range(N+1)]

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

# xとyが同じ集合に属するか否か
def bool_same(x,y):
    return root(x) == root(y)

# xとyの属する集合を併合
def unite(x,y):
    x = root(x)
    y = root(y)
    if x != y:
        par[x] = y

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

for i in range(M):
    a,b = AB[i]
    unite(a,b)

member = [0 for i in range(N+1)]

for i in range(1,N+1):
    member[root(i)] += 1

ans = [member[par[i]]-1 for i in range(N+1)]

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

for i in range(K):
    c,d = CD[i]
    if bool_same(c,d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans[1:])

Submission status: Runtime Error

Solution code:
from collections import deque
n,m,k = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]

f1 = [set() for _ in range(0, n+1)]
b1 = [set() for _ in range(0, n+1)]
fb1 = [set() for _ in range(0, n+1)]
ans = [0]*(n+1)

for x,y in ab:
    f1[x].add(y)
    f1[y].add(x)
    fb1[x].add(y)
    fb1[y].add(x)

for x,y in cd:
    b1[x].add(y)
    b1[y].add(x)
    fb1[x].add(y)
    fb1[y].add(x)

stack = deque()
visited = [0]*(n+1)
links = []

for i in range(1, n+1):
    if visited[i]: continue
    link = {i}
    visited[i] = 1
    stack.append(i)
    while stack:
        n1 = stack.pop()
        for j in f1[n1]:
            if visited[j] == 0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    links.append(link)

for i in v0:
    leni = len(i)
    for j in i:
        ans[j] = leni - len(i & fb1[j]) - 1

print(*ans[1:])

Submission status: Runtime Error

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

par = [i for i in range(N+1)]

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

# xとyが同じ集合に属するか否か
def bool_same(x,y):
    return root(x) == root(y)

# xとyの属する集合を併合
def unite(x,y):
    x = root(x)
    y = root(y)
    if x != y:
        par[x] = y

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

for i in range(M):
    a,b = AB[i]
    unite(a,b)

for i in range(N+1):
    root(i)

member = [0 for i in range(N+1)]

for i in range(1,N+1):
    member[par[i]] += 1

ans = [member[par[i]]-1 for i in range(N+1)]

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

for i in range(K):
    c,d = CD[i]
    if bool_same(c,d):
        ans[c] -= 1
        ans[d] -= 1

print(' '.join(list(map(str,ans[1:]))))

Submission status: Runtime Error

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

par = [i for i in range(N+1)]

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

# xとyが同じ集合に属するか否か
def bool_same(x,y):
    return root(x) == root(y)

# xとyの属する集合を併合
def unite(x,y):
    x = root(x)
    y = root(y)
    if x != y:
        par[x] = y

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

for i in range(M):
    a,b = AB[i]
    unite(a,b)

for i in range(N+1):
    root(i)

member = [0 for i in range(N+1)]

for p in par:
    member[p] += 1

ans = [member[par[i]]-1 for i in range(N+1)]

for i in range(M):
    a,b = AB[i]
    if bool_same(a,b):
        ans[a] -= 1
        ans[b] -= 1
for i in range(K):
    c,d = CD[i]
    if bool_same(c,d):
        ans[c] -= 1
        ans[d] -= 1
print(' '.join(map(str,ans[1:])))