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:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
import bisect as bs
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

class unionfind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.size = [1 for i in range(n)]
    def find(self,a):
        if a == self.parent[a]: return a
        else: self.parent[a] = find(self,self.parent[a]); return self.parent[a]
    def unite(self,a,b):
        pa,pb = self.find(self,a), self.find(self,b)
        if pa == pb: return
        else: self.parent[pb] = pa; self.size[pa] += self.size[pb]
    def same(self,a,b): return find(self,a) == find(self,b)


n,m,k = imap()
ab = np.array([iarr() for i in range(n)]) -1
#a,b = ab.T[0], ab.T[1]
uf = unionfind(n)

f = iarr(n)
for a,b in ab:
    uf.unite(a,b)
    f[a] += 1; f[b] += 1

ng = iarr(n)
for i in range(k):
    c,d = imap()
    if uf.same(c,d): ng[c] += 1; ng[d] += 1

anss = []
for i in range(n):
    ans = uf.size(i) - f[i] - ng[i] - 1
    anss.append(ans)
print(*anss)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy


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


uf = UnionFind(n)

friends = [0] + (n + 1)
chain = [0] + (n + 1)

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

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if uf.find(i) == uf.find(j):
            chain[i] += 1

for _ in range(k):
    c, d = map(int, input().split())
    if uf.find(c) == uf.find(d):
        friends[c] += 1
        friends[d] += 1

ans = []
for i in range(1, n + 1):
    ans.append(chain[i] - friends[i] - 1)

print(*ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from numba import jit


class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy


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


@jit('void(i8, i8, i8)')
def solve(n, m, k):
    uf = UnionFind(n)

    friends = defaultdict(int)
    chain = defaultdict(int)

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

    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if uf.find(i) == uf.find(j):
                chain[i] += 1

    for _ in range(k):
        c, d = map(int, input().split())
        if uf.find(c) == uf.find(d):
            friends[c] += 1
            friends[d] += 1

    ans = []
    for i in range(1, n + 1):
        ans.append(chain[i] - friends[i] - 1)

    print(*ans)


solve(n, m, k)

Submission status: Runtime Error

Solution code:
from collections import defaultdict


class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy


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


uf = UnionFind(n)

friends = defaultdict(set)
block = defaultdict(set)
chain = defaultdict(set)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a].add(b)
    friends[b].add(a)
    uf.union(a, b)

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

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if uf.find(i) == uf.find(j):
            chain[i].add(j)
            chain[j].add(i)

ans = []
for i in range(1, n + 1):
    ans.append(len(chain[i] - friends[i] - block[i] - 1))

print(*ans)

Submission status: Runtime Error

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n,m,k=n1()
AB=n3(m)
CD=n3(k)

G=nx.Graph()

G.add_edges_from(AB)

friend={i:[] for i in range(1,n+1)}
for i,j in AB:
    friend[i].append(j)
    friend[j].append(i)

block={i:[] for i in range(1,n+1)}
for i,j in CD:
    block[i].append(j)
    block[j].append(i)

ans=[]
for i in range(1,n+1):
    g=nx.single_source_shortest_path(G, source=i)
    f_kouho=set(g.keys())
    tmp=-1
    for j in f_kouho:
        if (not j in friend[i]) and (not j in block[i]):
            tmp+=1
    ans.append(tmp)
print(*ans)

Submission status: Runtime Error

Solution code:
from collections import deque

n, m, k = map(int, input().split())
F = [[] for _ in range(n)] #友達関係
B = [[] 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)
#print(F)

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

#print(B)
ans = []
flag = [False]*n
w = [-1]*n
for i in range(n):
    if flag[i]:
        continue
    d = deque([[i]])
    l = []
    while d:
        for u in d[0]:
            if not flag[u]:
                d.append(F[u])
                flag[u] = True
                l+=[u]
                #print(d)
                w[u]= i
        d.popleft()


    ans.append(l)

#print(w)
answer = []
for j in range(n):
    num = w[j]
    total = len(ans[num]) - len(F[j]) - 1
    for s in B[j]:
        if s in ans[num]:
            total -= 1
    answer.append(total)

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

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
F = [[] for i in range(n)]
B = [set() for i in range(n)]
l = [0]*n

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

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

seen = [0]*n
cnt = 0
r = []

def dfs(x):
    if seen[x] == 0:
        r[cnt].add(x)
        seen[x] = 1
        for i in F[x]:
            dfs(i)

for i in range(n):
    if seen[i] == 0:
        r.append(set())
        dfs(i)
        cnt += 1

ans = [0]*n

for i in r:
    lr = len(i)
    for j in i:
        ans[j] = lr - len(F[j]) - len(i & B[j]) - 1

print(*ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


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

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(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.root(x)]

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


def solve():
    N, M, K = Scanner.map_int()
    uni = UnionFind(N)
    friends = [set() for _ in range(N)]
    for _ in range(M):
        a, b = Scanner.map_int()
        a -= 1
        b -= 1
        uni.unite(a, b)
        friends[a].add(b)
        friends[b].add(a)
    block = [set() for _ in range(N)]
    for _ in range(K):
        a, b = Scanner.map_int()
        a -= 1
        b -= 1
        block[a].add(b)
        block[b].add(a)
    ans = [0 for _ in range(N)]
    for i in range(N):
        size = uni.size(i)
        f = len(friends[i])
        bn = 0
        for b in block[i]:
            if uni.is_same(i, b):
                bn += 1
        ans[i] = size - 1 - f - bn
    print(*ans)


def main():
    sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
CD = [list(map(int, input().split())) for _ in range(k)]
group = []  # 連結成分ごとのサイズ
person_group = [-1] * n  # 人ごとの属するグループ
person_unable= [0] * n  # 人ごとの候補に入らない人の人数
graph = [[] for _ in range(n)]  # 連結リスト
for ab in AB:
    ab[0] -= 1
    ab[1] -= 1
    graph[ab[0]].append(ab[1])
    graph[ab[1]].append(ab[0])

seen = [False] * n
# その節の連結成分のサイズを返す
def dfs(n, group_id):
    global size
    seen[n] = True
    person_group[n] = group_id
    for v in graph[n]:
        if seen[v]:
            continue
        size = dfs(v, group_id)
    size += 1
    return size
    
    
group_id = 0
for i in range(n):
    if seen[i]:
        continue
    size = 0
    group.append(dfs(i, group_id))
    group_id += 1

# unable計算。まず友達の人
for i in range(n):
    person_unable[i] += len(graph[i])
# 次にブロックの人
for i in range(k):
    CD[i][0] -= 1
    CD[i][1] -= 1
    if person_group[CD[i][0]] == person_group[CD[i][1]]:
        person_unable[CD[i][0]] += 1
        person_unable[CD[i][1]] += 1

for i in range(n):
    print(group[person_group[i]] - person_unable[i] - 1, "", end="")

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
# 深さ優先探索
def dfs(x, seen):
  seen.add(x)
  for i in G[x]:
    if i in seen:
      continue
    dfs(i, seen)

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

# Graph構造を作らないといけない。
S = set()

G = [[] for i in range(N)]
#G = defaultdict(list)
for _ in range(M):
  A, B = map(int, input().split())
  G[A-1].append(B-1)
  G[B-1].append(A-1)
  S |= set([A-1, B-1])

#print(len(S))

#n_iter = 0
#R = defaultdict(set)
R = []
while len(S) != 0:
    seen = set()
    dfs(S.pop(), seen)
    #R[n_iter] = seen
    R.append(seen)
    S = S - seen
    #n_iter += 1

#print(R[0])

#Block = defaultdict(set)
Block = [set() for i in range(N)]
for _ in range(K):
  C, D = map(int, input().split())
  Block[C-1].add([D-1])
  Block[D-1].add([C-1])

seq = [0]*N

for r in R:
    for j in r:
        seq[j] = len(r) - len(G[j]) - len(r&Block[j]) - 1
#友達の距離はそのまま徐算して良い。
#ブロックリストは候補じゃないパターンが存在するので難しい。
print(*seq)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
# 深さ優先探索
def dfs(x, seen):
  seen.add(x)
  for i in G[x]:
    if i in seen:
      continue
    dfs(i, seen)

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

# Graph構造を作らないといけない。
G = defaultdict(list)
for _ in range(M):
  A, B = map(int, input().split())
  G[A-1].append(B-1)
  G[B-1].append(A-1)
#print(G)

R = defaultdict(set)
for i in range(N):
  seen = set()
  dfs(i, seen)
  # 友達候補リストの作成
  R[i] = seen - set(G[i]) - set([i])
  #探索の都合で自分自身も入る。
  #すでに友達の要素は除外する。
#print(R)

#ブロックリストの反映
for _ in range(K):
  C, D = map(int, input().split())
  R[C-1].discard(D-1)
  R[D-1].discard(C-1)

#要素数が友達候補になる。
s = ''
for i in range(N):
  s += '{} '.format(len(R[i]))
print(s[:-1])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
# 深さ優先探索
def dfs(x, seen):
  seen.add(x)
  for i in G[x]:
    if i in seen:
      continue
    dfs(i, seen)

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

# Graph構造を作らないといけない。
G = defaultdict(list)
for _ in range(M):
  A, B = map(int, input().split())
  G[A-1].append(B-1)
  G[B-1].append(A-1)
#print(G)

R = defaultdict(set)
for i in range(N):
  seen = set()
  dfs(i, seen)
  # 友達候補リストの作成
  R[i] = seen - set(G[i]) - set([i])
  #探索の都合で自分自身も入る。
  #すでに友達の要素は除外する。
#print(R)

#ブロックリストの反映
for _ in range(K):
  C, D = map(int, input().split())
  R[C-1].discard(D-1)
  R[D-1].discard(C-1)

#要素数が友達候補になる。
s = ''
for i in range(N):
  s += f'{len(R[i])} '
print(s[:-1])

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].append(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

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

fri=[[] for i in range(n)]
blk=[[] for i in range(n)]

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

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


seen=[0 for i in range(n)]

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append([])
        dfs(i)
        cnt+=1

seq=[0 for i in range(n)]

for unii in uni:
    for j in unii:
        cj=len(unii)-len(fri[j-1])-len(set(unii)&set(blk[j-1])-1
        seq[j-1]=cj

print(*seq)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np


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

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

    def is_same_group(self, x, y):
        return self.get_root(x) == self.get_root(y)

    def count(self, x):
        return -self.root[self.get_root(x)]

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

        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1


input = sys.stdin.buffer.readline
N, M, K = map(int, input().split())

F = np.zeros((N, N), dtype='bool')
B = np.zeros((N, N), dtype='bool')

uf = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  # 0-indexed
    F[a, b] = 1
    F[b, a] = 1
    uf.unite(a, b)

for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1  # 0-indexed
    B[c, d] = 1
    B[d, c] = 1

for i in range(N):
    cnt = 0
    for j in range(N):
        if i == j:
            continue
        if uf.is_same_group(i, j) and not F[i, j] and not B[i, j]:
            # print('i, j', i, j)
            cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
import sys
from io import StringIO
import unittest
import os


# union find木
# 参考：https://note.nkmk.me/python-union-find/
class UnionFind:
    def __init__(self, n):
        """
        コンストラクタ
        :要素数 n:
        """
        self.n = n
        # 添字x: 値yとすると・・
        #   root以外の場合： 要素xは集合yに所属する。
        #   rootの場合　　　： 集合xの要素数はy個である。(負数で保持する)
        self.parents = [-1] * n

    def getroot(self, x):
        """
        所属する集合(ルートの番号)を取得する。
        :調査する要素 x:
        """
        # 値が負数 = ルートに到達したので、ルート木の番号を返す。
        if self.parents[x] < 0:
            return x
        else:
            # 値が正数 = ルートに到達していない場合、さらに親の情報を確認する。
            # 下の行は経路圧縮の処理。
            self.parents[x] = self.getroot(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        2つの要素が所属する集合をを同じ集合に結合する。
        :結合する要素(1つ目) x:
        :結合する要素(2つ目) y:
        """
        # 既に同じ集合に存在するなら何もせず終了。
        x = self.getroot(x)
        y = self.getroot(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):
        """
        指定した集合に属する要素数を取得する。
        :調査する集合 x:
        """
        # 添え字[root]には、要素数が負数で格納されている。そのため、取得する際は-反転する。
        return -self.parents[self.getroot(x)]

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

    def members(self, x):
        root = self.getroot(x)
        return [i for i in range(self.n) if self.getroot(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():
    # 数値取得サンプル
    #   1行N項目 x, y = map(int, input().split())
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]
    n, m, k = map(int, input().split())
    friends = [list(map(int, input().split())) for i in range(m)]
    blocks = [list(map(int, input().split())) for i in range(k)]

    # uf 作成(要素数を+1しているのは添え字と人番号を合わせるため)
    uf = UnionFind(n + 1)

    # 除外リスト作成(これは、本問題特有の処理)
    # 添字x: 値yとすると・・ 要素xの友達候補を数えるとき、y(list)に該当する人は除外する。(要素数を+1しているのは添え字と人番号を合わせるため)
    omits = [[] for i in range(n + 1)]

    # UnionFindにて集合を明確にする。
    for friend in friends:
        uf.union(friend[0], friend[1])

        # 除外リストを更新(これは、本問題特有の処理)
        omits[friend[0]].append(friend[1])
        omits[friend[1]].append(friend[0])

    # ブロックリストの情報を除外リストに加える(これは、本問題特有の処理)
    for block in blocks:
        # 同じ集合に属するウ場合のみ、リストに追加
        if uf.is_same(block[0], block[1]):
            omits[block[0]].append(block[1])
            omits[block[1]].append(block[0])

    # 友達候補数を出力して終了(人は1始まりなので1からループを行う
    # ans = []
    # for i in range(1, n + 1):
        # 友達候補 = 集合数 - 除外リスト(自分の友人数 + 自分がブロックしている人数) - 1(集合に含まれる自分自身を除く)
    #     ans.append(uf.size(i) - len(omits[i]) - 1)

    ans = [str(uf.size(i) - len(omits[i])) - 1 for i in range(1, n + 1)]
    
    print(" ".join(ans))


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 4 1
2 1
1 3
3 2
3 4
4 1"""
        output = """0 1 0 1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5"""
        output = """0 0 0 0 0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """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"""
        output = """1 3 5 4 3 3 3 3 1 0"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

using pint = pair<int,int>;
int main () {
    int N, M, K;
    cin >> N >> M >> K;
    vector<set<int> > dame(N);
    UnionFind uf(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        dame[a].insert(b);
        dame[b].insert(a);
        uf.merge(a, b);
    }
    for (int i = 0; i < K; ++i) {
        int c, d; cin >> c >> d; --c, --d;
        if (!uf.issame(c, d)) continue;
        dame[c].insert(d);
        dame[d].insert(c);
    }

    for (int i = 0; i < N; ++i) {
        int mem = uf.size(i) - 1; // 同じ連結成分の「自分以外」の人数
        mem -= dame[i].size(); // その中ですでに友達かブロック関係の人数
        cout << mem << " ";
    }
    cout << endl;
}

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

# フレンドの隣接リスト
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    F[a].append(b)
    F[b].append(a)

# ブロックの隣接リスト
for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    B[c].append(d)
    B[d].append(c)


# 交友関係グループ（辞書型）
D = {}
# グループの親
parent = [-1] * N
# 訪問管理
visited = [False] * N

for root in range(N):
    if visited[root]:
        continue

    D[root] = set([root])
    # 訪問先のスタック
    stack = [root]
    # 訪問先が無くなるまで
    while stack:
        # 訪問者をポップアップ
        n = stack.pop()
        # 訪問者を訪問済み
        visited[n] = True
        # 訪問者のグループの親を設定
        parent[n] = root

        # root のフレンドをグループと訪問先に追加
        D[root].add(to)
        stack.append(to)

ans = [0] * N
for iam in range(N):
    # 自分の交友関係グループを設定
    group = D[parent[iam]]
    # グループからフレンドと自分を除く
    tmp_ans = len(group) - len(F[iam]) - 1
    # グループからブロックを除く
    for block in B[iam]:
        if block in group:
            tmp_ans -= 1
    ans[iam] = tmp_ans

print(*ans, sep=' ')

Submission status: Runtime Error

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

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

for i in range(k):
    c,d =(map(int,input().split()))
    c,d = c-1,d-1
    cannotgo[c].appned(d)
    cannotgo[d].appned(c)
# print(a)
# cango = [[]for i in range(n)]
# for i in a:
#     cango[i[0]-1].append(i[1]-1)
#     cango[i[1]-1].append(i[0]-1)
# print(cango)

# cannotgo=[[]for i in range(n)]
# for i in c:
#     cannotgo[i[0]-1].append(i[1]-1)
#     cannotgo[i[1]-1].append(i[0]-1)
# # print(cannotgo)
alre = [False]*n
parent = [-1]*n
gro = {}

# print(gro)
for i in range(n):
    if alre[i]==True:
        continue
    gro[i]=set([i])
    stack = [i]
    while stack:
        x = stack.pop()
        alre[x]=True
        parent[x]=i
        for to in cango[x]:
            if alre[to]:
                continue
            # print(to)
            gro[i].add(to)
            stack.append(to)
# print(gro)
# print(parent)
ans = [0]*n
# print(ans)
for iam in range(n):
    group = gro[parent[iam]]
    tmp_ans = len(group)-len(cango[iam])-1
    for block in cannotgo[iam]:
        if block in group:
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

for i in range(k):
    c,d =(map(int,input().split()))
    c,d = c-1,d-1
    cannotgo[c]=d
    cannotgo[d]=c
# print(a)
# cango = [[]for i in range(n)]
# for i in a:
#     cango[i[0]-1].append(i[1]-1)
#     cango[i[1]-1].append(i[0]-1)
# # print(cango)

# cannotgo=[[]for i in range(n)]
# for i in c:
#     cannotgo[i[0]-1].append(i[1]-1)
#     cannotgo[i[1]-1].append(i[0]-1)
# # print(cannotgo)
alre = [False]*n
parent = [-1]*n
gro = {}

# print(gro)
for i in range(n):
    if alre[i]==True:
        continue
    gro[i]=set([i])
    stack = [i]
    while stack:
        x = stack.pop()
        alre[x]=True
        parent[x]=i
        for to in cango[x]:
            if alre[to]:
                continue
            # print(to)
            gro[i].add(to)
            stack.append(to)
# print(gro)
# print(parent)
ans = [0]*n
# print(ans)
for iam in range(n):
    group = gro[parent[iam]]
    tmp_ans = len(group)-len(cango[iam])-1
    for block in cannotgo[iam]:
        if block in group:
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')