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:
n,m,k = map(int,input().split())
import sys
rks = [None] *n
sys.setrecursionlimit(10**9)
fgraph = [list() for i in range(n)]
bgraph = [list() for i in range(n)]
cgraph = [list() for i in range(n)]
for i in range(m):
        a,b = map(int, input().split())
        fgraph[a-1].append(b)
        fgraph[b-1].append(a)
def dfs(graph,s,r):
    if rks[s] is None:
        rks[s] = r
    for i in range(len(graph[s])):
        if rks[graph[s][i]-1] is not None:
            continue
        dfs(graph, graph[s][i]-1,r)
c = -1
for i in range(n):
    if rks[i] is None:
        c += 1
        dfs(fgraph, i, c)
for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)
s = []
for i in range(c+1):
    s.append(rks.count(i))
for i in range(n):
        print(s[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

Submission status: Runtime Error

Solution code:
n,m,k = map(int,input().split())
import sys
rks = [None] *n
sys.setrecursionlimit(10**9)
fgraph = [list() for i in range(n)]
bgraph = [list() for i in range(n)]
cgraph = [list() for i in range(n)]
for i in range(m):
        a,b = map(int, input().split())
        fgraph[a-1].append(b)
        fgraph[b-1].append(a)
def dfs(graph,s,r):
    if rks[s] is None:
        rks[s] = r
    for i in range(len(graph[s])):
        if rks[graph[s][i]-1] is not None:
            continue
        dfs(graph, graph[s][i]-1,r)
c = -1
for i in range(n):
    if rks[i] is None:
        c += 1
        dfs(fgraph, i, c)
for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)
for i in range(c+1):
    s[i] = rks.count(i)
for i in range(n):
        print(rks.count(rks[i]) - len(fgraph[i]) - len(bgraph[i]) - 1)

Submission status: Runtime Error

Solution code:
n,m,k = map(int,input().split())
rks = [None] *n
fgraph = [list() for i in range(n)]
bgraph = [list() for i in range(n)]
cgraph = [list() for i in range(n)]
for i in range(m):
        a,b = map(int, input().split())
        fgraph[a-1].append(b)
        fgraph[b-1].append(a)
def dfs(graph,s,r):
    if rks[s] is None:
        rks[s] = r
    for i in range(len(graph[s])):
        if rks[graph[s][i]-1] is not None:
            continue
        dfs(graph, graph[s][i]-1,r)
c = -1
for i in range(n):
    if rks[i] is None:
        c += 1
        dfs(fgraph, i, c)
for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)
for i in range(n):
        print(rks.count(rks[i]) - len(fgraph[i]) - len(bgraph[i]) - 1)

Submission status: Runtime Error

Solution code:

def tramp(gen):
    stack = [gen]
    val = None
    while stack:
        try:
            stack.append(stack[-1].send(val))
            val = None
        except StopIteration as e:
            stack.pop()
            val = e.value # e.args
    return val
    
N, M, K = map(int, input().split())
adj = [[] for _ in range(N)]
blks = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)
for _ in range(K):
    a, b = map(int, input().split())
    blks[a - 1].add(b - 1)
    blks[b - 1].add(a - 1)
vis = [False] * N
def go(curr):
    if vis[curr]:
        return
    vis[curr] = True
    comp.add(curr)
    for n in adj[curr]:
        yield go(n)
ans = [0] * N
for i in range(N):
    comp = set()
    if vis[i]:
        continue
    tramp(go(i))
    for i in comp:
        x = len(comp) - 1 - len(adj[i])
        for k in blks[i]:
            if k in comp:
                x -= 1
        ans[i] = x
print(*ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n_nodes):
        self.parent = [i for i in range(n_nodes)]
        self.rank = [0] * n_nodes
        self.size = [1] * n_nodes

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

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

        if x == y:
            return

        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
            self.size[x] += self.size[y]
        else:
            self.parent[x] = y
            self.size[y] += self.size[x]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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


N, M, K = map(int, input().split())
tree = UnionFind(N)
exclusion = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree.unite(a, b)
    exclusion[a].append(b)
    exclusion[b].append(a)

for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if not tree.check(c, d):
        continue
    exclusion[c].append(d)
    exclusion[d].append(c)

for i in range(N):
    # 同一グループで自分以外の人数
    n = tree.get_size(i) - 1
    ans = n - len(exclusion[i])
    print(ans, end=" ")

Submission status: Runtime Error

Solution code:
n, m, k = map(int,input().split())
friends = [[] for i in range(n)]
brock = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int,input().split())
    friends[a-1].append(b-1)
    friends[b-1].append(a-1)
for i in range(k):
    c, d = map(int,input().split())
    brock[c-1].append(d-1)
    brock[d-1].append(c-1)

group = []

def dfs(x):
    if not x in g:
        g.append(x)
        for l in friends[x]:
            dfs(l)

for i in range(n):
    flag = True
    for j in group:
        if i in j:
            flag = False
    if flag:
        g = [i]
        for j in friends[i]:
            dfs(j)
        group.append(g)

print(group)
'''
ans = [-1 for i in range(n)]
for i in range(n):
    for j in group:
        if i in j:
            ans[i] += len(j)
            break
    ans[i] -= len(friends[i])+len(brock[i])

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

Submission status: Runtime Error

Solution code:
n, m, k = map(int,input().split())
friends = [[] for i in range(n)]
brock = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int,input().split())
    friends[a-1].append(b-1)
    friends[b-1].append(a-1)
for i in range(k):
    c, d = map(int,input().split())
    brock[c-1].append(d-1)
    brock[d-1].append(c-1)

group = []

def dfs(x):
    if not x in g:
        g.append(x)
        for l in friends[x]:
            dfs(l)

for i in range(n):
    flag = True
    for j in group:
        if i in j:
            flag = False
    if flag:
        g = [i]
        for j in friends[i]:
            dfs(j)
        group.append(g)

ans = [-1 for i in range(n)]
for i in range(n):
    for j in group:
        if i in j:
            ans[i] += len(j)
            break
    ans[i] -= len(friends[i])+len(brock[i])

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

Submission status: Runtime Error

Solution code:
from collections import deque
N, M, K = map(int, input().split())
if M != 0:
  F = [[] for _ in range(N)]
  for _ in range(M):
    a, b = map(int, input().split())
    F[a-1].append(b - 1)
    F[b-1].append(a - 1)

if K != 0:
  B = [[] for _ in range(N)]
  for _ in range(K):
    c, d = map(int, input().split())
    B[c-1].append(d - 1)
    B[d-1].append(c - 1)

for i in range(N):
  to_see = deque()
  to_see.append(i)
  costs = [-1] * N
  costs[i] = 0

  count = 0

  while to_see:
    cur = to_see.popleft()
    for np in F[cur]:
      if costs[np] == -1:
        costs[np] = costs[cur] + 1
        to_see.append(np)
        if costs[np] != 1 and (np not in B[i]):
          count += 1
  if (i != N - 1):
    print(count, end=" ")
  else:
    print(count)

Submission status: Runtime Error

Solution code:
  from collections import deque
  N, M, K = map(int, input().split())
  if M != 0:
    F = [[] for _ in range(N)]
    for _ in range(M):
      a, b = map(int, input().split())
      F[a-1].append(b - 1)
      F[b-1].append(a - 1)
  
  if K != 0:
    B = [[] for _ in range(N)]
    for _ in range(K):
      c, d = map(int, input().split())
      B[c-1].append(d - 1)
      B[d-1].append(c - 1)
  
  for i in range(N):
    to_see = deque()
    to_see.append(i)
    costs = [-1] * N
    costs[i] = 0

    count = 0

    while to_see:
      cur = to_see.popleft()
      for np in F[cur]:
        if costs[np] == -1:
          costs[np] = costs[cur] + 1
          to_see.append(np)
          if costs[np] != 1 and (np not in B[i]):
            count += 1
    if (i != N - 1):
      print(count, end=" ")
    else:
      print(count)

Submission status: Runtime Error

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

#[index,parent]
unionfind=[[i,-1] for i in range(n)]
friendlist=[set() for _ in range(n)]
blocklist=[set() for _ in range(n)]

def findroot(ind):
    if(unionfind[ind][1]==-1):
        return unionfind[ind][0]
    else:
        return findroot(unionfind[ind][1])

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

    if(findroot(a) != findroot(b)):
        unionfind[findroot(b)][1]=unionfind[findroot(a)][0]

for i in range(k):
    c,d=map(int,input().split())
    c-=1
    d-=1
    blocklist[c].add(d)
    blocklist[d].add(c)

grouplist={}
for i in range(n):
    rooti=findroot(i)
    groupi=grouplist.get(rooti, set())
    groupi.add(i)
    grouplist[rooti]=groupi

# print(unionfind)
# print(friendlist)
# print(blocklist)
# print(grouplist)

ans=[]
for i in range(n):
    ans.append(len(grouplist[findroot(i)] - friendlist[i] - blocklist[i] ) - 1)
print(*ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.size = [1]*n

    def find(self,a):
        if self.parent[a] == a:
            return a
        else:
            return self.find(self.parent[a])

    def unite(self,a,b):
        a_parent = self.parent[a]
        b_parent = self.parent[b]
        if a_parent == b_parent:
            return
        else:
            if self.size_of(b_parent) > self.size_of(a_parent): 
                self.parent[a_parent] = self.parent[b_parent]
                self.size[b_parent] += self.size[a_parent]
            else:
                self.parent[b_parent] = self.parent[a_parent]
                self.size[a_parent] += self.size[b_parent]
                
    def size_of(self,a):
        return self.size[self.find(a)]
    
    def is_same(self,a,b):
        return self.parent(a) == self.parent(b)


N,M,K = map(int, input().split())
uf = UnionFind(N+1)
friends = []
blocks = []
for i in range(N+1):
    blocks.append([])
    friends.append(0)

for i in range(M):
    a,b = map(int, input().split())
    friends[a] += 1
    friends[b] += 1
    uf.unite(a,b)
    
for j in range(K):
    x,y = map(int, input().split())
    blocks[x].append(y)
    blocks[y].append(x)

for i in range(1,N+1):
    print(uf.size_of(i) - friends[i] - len([x for x in range(1,N+1) if i in blocks[x] and uf.find(i) == uf.find(x)])-1)

Submission status: Runtime Error

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

#[index,parent]
unionfind=[[i,-1] for i in range(n)]
friendlist=[[] for _ in range(n)]
blocklist=[[] for _ in range(n)]

def findroot(ind):
    if(unionfind[ind][1]==-1):
        return unionfind[ind][0]
    else:
        return findroot(unionfind[ind][1])

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

    if(findroot(a) != findroot(b)):
        unionfind[findroot(b)][1]=unionfind[findroot(a)][0]

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

grouplist={}
for i in range(n):
    rooti=findroot(i)
    groupi=grouplist.get(rooti, [])
    groupi.append(i)
    grouplist[rooti]=groupi

ans=[]
for i in range(n):
    ans.append(len(set(grouplist[findroot(i)]) - set(friendlist[i]) - set(blocklist[i]) ) - 1)
print(*ans)

Submission status: Runtime Error

Solution code:
import sys
from copy import copy, deepcopy
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for CASES in range(int(input())):
'''
inf = 100000000000000000  # 1e17
mod = 998244353

'''
# example input
4 4 1
2 1
1 3
3 2
3 4
4 1

'''


def find(x):
    if fa[x] == x:
        return x
    fa[x] = find(fa[x])
    return fa[x]


def union(x, y):
    if find(x) != find(y):
        fa[find(x)] = find(y)


n, m, k = map(int, input().split())
FRIEND = []
BLOCK = []
A = [[] for i in range(n)]
fa = [i for i in range(n)]
ru = [0] * (n)
for i in range(m):
    FRIEND.append(list(map(int, input().split())))
    FRIEND[i][0] -= 1
    FRIEND[i][1] -= 1
    union(FRIEND[i][0], FRIEND[i][1])
    ru[FRIEND[i][0]] += 1
    ru[FRIEND[i][1]] += 1
for i in range(k):
    BLOCK.append(list(map(int, input().split())))
    BLOCK[i][0] -= 1
    BLOCK[i][1] -= 1
    A[BLOCK[i][0]].append(BLOCK[i][1])
    A[BLOCK[i][1]].append(BLOCK[i][0])

SET = [0] * (n)
for i in range(n):
    SET[find(i)] += 1

for i in range(n):
    number_set = SET[fa[i]]
    number_direct = ru[i]
    number_block = 0
    for a in A[i]:
        if find(a) == find(i):
            number_block += 1
    # print(number_direct,number_block)
    print(number_set - number_direct - number_block - 1, end=" ")

Submission status: Runtime Error

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

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)

def dfs(now):
    global group
    for next in friend[now]:
        if visited[next]==False:
            visited[next]=True
            group.append(next)
            dfs(next)
            
    return group
group=[]
visited=[False]*n
for i in range(n):
        visited=[False]*(n)
        visited[i]=True
        G.append(dfs(i))
        group=[]
for i in range(n):
    ans=set(G[i])-set(friend[i])-set(block[i])
    print(len(ans))

Submission status: Runtime Error

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

fa = [x for x in range (n + 1)]
cnt = [1 for i in range (n + 1)]
e = [1 for i in range (n + 1)]

def find (x) :
    if (fa[x] == x) :
        return x
    fa[x] = find (fa[x])
    cnt[x] = cnt[fa[x]]
    return fa[x]

def uni (x, y) :
    u, v = find (x), find (y)
    if (u != v) :
        fa[u] = v
        cnt[u] += cnt[v]
        cnt[v] = cnt[u]

for i in range (m) :
    a, b = list (map (int, input ().split ()))
    uni (a, b)
    e[a] += 1
    e[b] += 1

for i in range (1, n + 1) :
    tmp = find (i)

for i in range (k) :
    c, d = list (map (int, input ().split ()))
    if (find (c) == find (d)) :
        cnt[c] -= 1
        cnt[d] -= 1

cnt = [cnt[i] - e[i] for i in range (1, n + 1)]

print (' '.join (list (map (str, cnt))))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import copy

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

#cf atc001b UnionFind, union find ,グループ化 ##################################
friend_connection_dict = {i:i for i in range(1,N+1)} #直接も含んだ友達関係 ex. A-B-CでA-Cの関係を含む

#接続追加
def add_connect(A,B):
    A_parent = get_parent(A)
    B_parent = get_parent(B)
    
    if A_parent != B_parent:
        friend_connection_dict[B_parent] = A_parent

#親の取得
def get_parent(child):
    if child not in friend_connection_dict: #初出なら自分自身を親として追加
        friend_connection_dict[child] = child
    
    parent = friend_connection_dict[child]
    
    if parent == child: 
        return parent
    else: #最上位の親なら上の等式が成り立つ。不成立ならさらに上位の親を辿る。
        friend_connection_dict[child] = get_parent(parent) 
        return friend_connection_dict[child]
###############################################################################

#友達関係
direct_friend_dict = {i:set() for i in range(1,N+1)} #直接のみの友達関係

for i in range(M):
    A,B = map(int, input().split())
    direct_friend_dict[A].add(B)
    direct_friend_dict[B].add(A)
    add_connect(A,B)

#友達関係を扱いやすいように親毎にまとめる
group_dict = defaultdict(set)
for i in range(1,N+1):
    #print(i,friend_connection_dict[i])
    group_id = get_parent(i)
    group_dict[group_id].add(i)

#ブロック関係
block_dict = {i:set() for i in range(1,N+1)}

for i in range(K):
    C,D = map(int, input().split())
    block_dict[C].add(D)
    block_dict[D].add(C)
    
#print(friend_connection_dict)
#print(block_dict)

ans = list()

for i in range(1,N+1):
    group_id = friend_connection_dict[i]
    
    #print("person             :",i)
    #print("group_id           :",group_id)
    #print("group_member       :",group_dict[group_id])
    #print("direct_friend      :",direct_friend_dict[i])
    #print("blocked            :",block_dict[i])
    
    suggestioned_friend = copy.copy(group_dict[group_id]) #1以上 N 以下の整数から成るある数列 c0,c1,c2,⋯,cL が存在し、c0=a であり、 cL=b であり、 i=0,1,⋯,L−1 について、人 ci と人 ci+1 は友達関係にある。
    #suggestioned_friend -= direct_friend_dict[i] #人 aと人 bは友達関係に無い。
    suggestioned_friend = suggestioned_friend.difference(direct_friend_dict[i])
    #suggestioned_friend -= block_dict[i] #人 a と人 bはブロック関係に無い。
    suggestioned_friend = suggestioned_friend.difference(block_dict[i])
    #print("suggestioned_friend:",suggestioned_friend)
    ans.append(len(suggestioned_friend)-1)
    
print(' '.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import copy

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

#cf atc001b UnionFind, union find ,グループ化 ##################################
friend_connection_dict = {i:i for i in range(1,N+1)} #直接も含んだ友達関係 ex. A-B-CでA-Cの関係を含む

#接続追加
def add_connect(A,B):
    A_parent = get_parent(A)
    B_parent = get_parent(B)
    
    if A_parent != B_parent:
        friend_connection_dict[B_parent] = A_parent

#親の取得
def get_parent(child):
    if child not in friend_connection_dict: #初出なら自分自身を親として追加
        friend_connection_dict[child] = child
    
    parent = friend_connection_dict[child]
    
    if parent == child: 
        return parent
    else: #最上位の親なら上の等式が成り立つ。不成立ならさらに上位の親を辿る。
        friend_connection_dict[child] = get_parent(parent) 
        return friend_connection_dict[child]
###############################################################################

#友達関係
direct_friend_dict = {i:set() for i in range(1,N+1)} #直接のみの友達関係

for i in range(M):
    A,B = map(int, input().split())
    direct_friend_dict[A].add(B)
    direct_friend_dict[B].add(A)
    add_connect(A,B)

#友達関係を扱いやすいように親毎にまとめる
group_dict = defaultdict(set)
for i in range(1,N+1):
    #print(i,friend_connection_dict[i])
    group_id = get_parent(i)
    group_dict[group_id].add(i)

#ブロック関係
block_dict = {i:set() for i in range(1,N+1)}

for i in range(K):
    C,D = map(int, input().split())
    block_dict[C].add(D)
    block_dict[D].add(C)
    
#print(friend_connection_dict)
#print(block_dict)

ans = list()

for i in range(1,N+1):
    group_id = friend_connection_dict[i]
    
    #print("person             :",i)
    #print("group_id           :",group_id)
    #print("group_member       :",group_dict[group_id])
    #print("direct_friend      :",direct_friend_dict[i])
    #print("blocked            :",block_dict[i])
    
    suggestioned_friend = copy.copy(group_dict[group_id]) #1以上 N 以下の整数から成るある数列 c0,c1,c2,⋯,cL が存在し、c0=a であり、 cL=b であり、 i=0,1,⋯,L−1 について、人 ci と人 ci+1 は友達関係にある。
    suggestioned_friend -= direct_friend_dict[i] #人 aと人 bは友達関係に無い。
    suggestioned_friend -= block_dict[i] #人 a と人 bはブロック関係に無い。

    #print("suggestioned_friend:",suggestioned_friend)
    ans.append(len(suggestioned_friend)-1)
    
print(' '.join(map(str, ans)))

Submission status: Runtime Error

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

F = [[] for i in range(n)]   #Friend list
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    F[a].append(b)
    F[b].append(a)


gnum = 1    #group number
#DFS
def DFS_func(a:int, gnum:int):   #Target, Data
        if G[a] == 0:
            G[a] = gnum
            for i in range(len(F[a])):
                DFS_func(F[a][i], gnum)
        else:
            pass
G = [0 for i in range(n)]   #it has Group numbers       
for i in range(n):
    if G[i] == 0:
        DFS_func(i, gnum)
        gnum += 1
    else:
        pass

B = [0 for i in range(n)]   #How many Blocks in the same Group
for i in range(k):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    if G[c] == G[d]:
        B[c] , B[d] = B[c]+1, B[d]+1
    else:
        pass

GS = [0 for i in range(gnum)]   #Group Size
for i in range(n):
    GS[G[i]] += 1

for i in range(n):
    if G[i] == 0:
        ans = 0
    else:
        ans = GS[G[i]]-len(F[i])-B[i]-1
    print(ans, end = ' ')

Submission status: Runtime Error

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

s = [0]*n

for i in range(m):
    keta, num = map(int,input().split())
    if s[keta-1] == 0 or s[keta-1] == num:
        s[keta-1] = num
    else:
        print(-1)
        exit()

if s[0] != 0:
    print(*s, sep ="")
elif s[0] == 0 and n == 1:
    print(0)
elif s[0] == 0 and n != 1:
    s[0] = 1
    print(*s, sep ="")
else:
    print(-1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    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 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)


n, m, k = list(map(int, input().split()))
a = [0]*(n+1)
b = [0]*(n+1)
c = [0]*(k+1)
d = [0]*(k+1)
union_find = UnionFind(n)
num_friends = [0]*(n+1)
for i in range(m):
    a[i], b[i] = map(int, input().split())
    num_friends[a[i]] += 1
    num_friends[b[i]] += 1
    union_find.union(a[i], b[i])
for i in range(k):
    c[i], d[i] = map(int, input().split())

# frinds_mat = np.zeros([n, n])
# for i in range(m):
#     # a[i]とb[i]は友達
#     frinds_mat[a[i]-1, b[i]-1] = 1
#     frinds_mat[b[i]-1, a[i]-1] = 1
num_suggest_friend = [-1]*(n+1)  # 自分自身を引いておくので-1で初期化
for i in range(1, n+1):
    for j in range(1, n+1):
        if (union_find.same_check(i, j)):
            num_suggest_friend[i] += 1
# print(*num_suggest_friend[1:], sep=' ')


for i in range(1, n+1):
    num_suggest_friend[i] -= num_friends[i]
# print(*num_suggest_friend[1:], sep=' ')
for c_, d_ in zip(c, d):
    if union_find.same_check(c_, d_):
        num_suggest_friend[c_] -= 1
        num_suggest_friend[d_] -= 1

print(*num_suggest_friend[1:], sep=' ')

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

# 友達関係をUFで用意
uf = UnionFind(N)

# 直接の友達のリスト
friend = [[] for i in range(N)]
# 直接のブロックのリスト
block = [[] for i in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    uf.union(A-1, B-1)
    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)

ans = [0 for i in range(N)]

# 友達関係のグループの要素数ーグループ内の直接の友達の数ーグループ内の直接のブロックの数ー自分自身
for i in range(N):
    ans[i] += uf.size(i) -1
    for j in friend[i]:
        if uf.same(i,j):
            ans[i] -= 1
    for j in block[i]:
        if uf.same(i,j):
            ans[j] -= 1

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

Submission status: Runtime Error

Solution code:
if __name__ == "__main__":
    resolve()

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



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

    # 友達関係をUFで用意
    uf = UnionFind(N)

    # 直接の友達のリスト
    friend = [[]for i in range(N)]
    # 直接のブロックのリスト
    block = [[] for i in range(N)]

    for i in range(M):
        A, B = map(int, input().split())
        uf.union(A-1,B-1)
        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)

    ans = [0 for i in range(N)]

    # 友達関係のグループの要素数ーグループ内の直接の友達の数ーグループ内の直接のブロックの数ー自分自身
    for i in range(N):
        X = set(uf.members(i))
        Y = set(friend[i])
        Z = set(block[i])
        ans[i] = len(X) - len(X & Y) - len(X & Z) - 1

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

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())
uf = UnionFind(n)
E = [[] for i in range(n)]
num_E = [0]*n
E_d = [[] for i in range(n)]

import sys
input = sys.stdin.readline

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

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

num_men = [0]*n
for i in range(n):
  num_men[i] = uf.size(i) - 1
  for dn in E_d[i]:
    if uf.same(i, dn):
      num_men[i] -= 1
  num_men[i] -= E[i]
      
print(*num_men)

Submission status: Runtime Error

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

def dfs(v):
    size = 1
    for w in fr[v]:
        if ~roots[w]: continue
        roots[w] = roots[v]
        size += dfs(w)
    return size

fr = defaultdict(set)
for _ in range(M):
    a, b = [int(x) -1 for x in input().split()]
    fr[a].add(b)
    fr[b].add(a)
bl = defaultdict(set)
for _ in range(K):
    a, b = [int(x) - 1 for x in input().split()]
    bl[a].add(b)
    bl[b].add(a)

roots = [-1] * N
sizes = [-1] * N

for v in range(N):
    if ~roots[v]: continue
    roots[v] = v
    sizes[v] = dfs(v)

ans = []
for v in range(N):
    w = roots[v]
    res = sizes[w] - len(fr[v]) - sum(1 for u in bl[v] if roots[u] == w) -1
    ans.append(res)

print(*ans)