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())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

par = [] # parent

def init():
    for i in range(N):
        par.append(i)

def root(x):
    if par[x] != x:
        par[x] = root(par[x])
    return par[x]

def same(x, y):
    return root(x) == root(y)

def unite(x, y):
    x, y = root(x), root(y)
    if x != y:
        par[x] = y


init()

block_num = [0]*N
friend_num = [0]*N
cls_cnt = {} # cluster count

for ab in AB:
    a, b = ab[0]-1, ab[1]-1

    friend_num[a] += 1
    friend_num[b] += 1

    unite(a,b)


for cd in CD:
    c, d = cd[0]-1, cd[1]-1
    block_num[c] += 1
    block_num[d] += 1


cls_cnt = {} # cluster count
for i in range(N):
    r = root(i)
    if r in cls_cnt:
        cls_cnt[r] += 1
    else:
        cls_cnt[r] = 1


for i in range(N):
    r = root(i)
    ans = cls_cnt[r] - 1 - friend_num[i] - block_num[i]
    print(ans , end=' ')

Submission status: Runtime Error

Solution code:
class UF:
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) #1-indexedにするために１個足している
        self.rnks = [0] * (n+1)

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

    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        if self.rnks[a_par] > self.rnks[b_par]:
            a_par,b_par = b_par,a_par
        if self.rnks[a_par] == self.rnks[b_par]:
            self.rnks[a_par] += 1
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def length(self,n):
        par = self.find(n)
        return abs(self.parents[par])

    def is_same(self,a,b):
        return self.find(a) == self.find(b)



def main():
    n,m,k = map(int,input().split())
    uf = UF(n)
    block_lst = [0 for _ in range(n+1)]
    friend_lst = [0 for _ in range(n+1)]
    #友達リスト部分
    for i in range(m):
        a,b = map(int,input().split())
        friend_lst[a] += 1
        friend_lst[b] += 1
        uf.union(a,b)
    #print(friend_lst)

    #ブロックリスト部分
    for i in range(k):
        c,d = map(int,input().split())
        if uf.is_same(c,d):#c,dが同じ友達候補グループにない限り、解答には影響しない！
            block_lst[c] += 1
            block_lst[d] += 1
    #print(block_lst)
    #メイン処理
    answer = [0] * n

    for i in range(1,n+1):
        f_o_f = uf.length(i)
        answer[i-1] = f_o_f - friend_lst[i] - block_lst[i] - 1


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






if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class UF:
    #経路圧縮のみのunion find木
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) #1-indexedにするために１個足している
        self.rnks = [0] * (n+1)

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

    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        if self.rnks[a_par] > self.rnks[b_par]:
            a_par,b_par = b_par,a_par
        if self.rnks[a_par] == self.rnks[b_par]:
            self.rnks[a_par] += 1
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def length(self,n):
        par = self.find(n)
        return abs(self.parents[par])

    def is_same(self,a,b):
        return self.find(a) == self.find(b)



def main():
    n,m,k = map(int,input().split())
    uf = UF(n)
    block_lst = [0 for _ in range(n+1)]
    friend_lst = [0 for _ in range(n+1)]
    #友達リスト部分
    for i in range(m):
        a,b = map(int,input().split())
        friend_lst[a] += 1
        friend_lst[b] += 1
        uf.union(a,b)
    #print(friend_lst)

    #ブロックリスト部分
    for i in range(k):
        c,d = map(int,input().split())
        if uf.is_same(c,d):#c,dが同じ友達候補グループにない限り、解答には影響しない！
            block_lst[c] += 1
            block_lst[d] += 1
    #print(block_lst)
    #メイン処理
    answer = []

    for i in range(1,n+1):
        f_o_f = uf.length(i)
        answer.append(f_o_f - friend_lst[i] - block_lst[i] - 1)


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






if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#import time
#start = time.time()

# スペース区切りの整数入力
N,M,K = map(int, input().split())

fcnum = [ 0 for i in range(N+1)]
fring = [[] for i in range(N+1)]
frno =  [-1 for i in range(N+1)]

ab = []
for i in range(M):
    aa,bb = map(int, input().split())
    if aa > bb:
        aa,bb = bb,aa
    fcnum[aa] -= 1
    fcnum[bb] -= 1
    ab.append([aa,bb])

for aa,bb in ab:
    if frno[aa] == -1 and frno[bb] == -1:
        frn = aa
        frno[aa] = frn
        frno[bb] = frn
        fring[frn].append(aa)
        fring[frn].append(bb)
    elif frno[aa] == -1 and frno[bb] != -1:
        frn = frno[bb]
        frno[aa] = frn
        fring[frn].append(aa)
    elif frno[aa] != -1 and frno[bb] == -1:
        frn = frno[aa]
        frno[bb] = frn
        fring[frn].append(bb)
    else:
        if frno[aa] != frno[bb]:
            if len(fring[frno[aa]]) > len(fring[frno[bb]]):
                frnto = frno[aa]
                frnfrom = frno[bb]
            else:
                frnto = frno[bb]
                frnfrom = frno[aa]
            fring[frnto].extend(fring[frnfrom])
            for mvf in fring[frnfrom]:
                frno[mvf] = frnto
            del fring[frnfrom]
            #fring[frnfrom] = []

for i in range(K):
    cc,dd = map(int, input().split())
    if frno[cc] == frno[dd]:
        fcnum[cc] -= 1
        fcnum[dd] -= 1

for k in range(1,len(fring)):
    cnum = len(fring[k]) - 1
    for ff in fring[k]:
        fcnum[ff] += cnum

for i in range(1,len(fcnum)):
    print(fcnum[i]," ",end="")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**3)

N, M, K = map(int,input().split())
tree = [-1 for _ in range(N)]
fc = [0] * N
bc = [0] * N
ans = [0] * N

def find(x):
    # x を引数に取り、xのroot番号を取得するメモ化再帰
    if tree[x] < 0:
        return x
    tree[x] = find(tree[x])
    return tree[x]

def unite(x, y):
    # x, y を引数に取り、x(自分)をy(相手)のrootに接続する関数
    rootx = find(x)
    rooty = find(y)
    if rootx == rooty:
        return
    if rootx < rooty:
        x , y = y, x
    tree[rooty] += tree[rootx]
    tree[rootx] = rooty

for m in range(M):
    a, b = map(int,input().split())
    fc[a-1] += 1
    fc[b-1] += 1
    unite(a-1, b-1)

for k in range(K):
    c, d = map(int,input().split())
    if find(c-1) == find(d-1):
        bc[c-1] += 1
        bc[d-1] += 1

for i in range(N):
    cnt = -tree[find(i)] - 1 - fc[i] - bc[i]
    ans[i] = cnt

print(*ans)

Submission status: Runtime Error

Solution code:
N, M, K = map(int,input().split())
tree = [-1 for _ in range(N)]
fc = [0] * N
bc = [0] * N
ans = [0] * N

def find(x):
    # x を引数に取り、xのroot番号を取得するメモ化再帰
    if tree[x] < 0:
        return x
    tree[x] = find(tree[x])
    return tree[x]

def unite(x, y):
    # x, y を引数に取り、x(自分)をy(相手)のrootに接続する関数
    rootx = find(x)
    rooty = find(y)
    if rootx == rooty:
        return
    if rootx < rooty:
        x , y = y, x
    tree[rooty] += tree[rootx]
    tree[rootx] = rooty

for m in range(M):
    a, b = map(int,input().split())
    fc[a-1] += 1
    fc[b-1] += 1
    unite(a-1, b-1)

for k in range(K):
    c, d = map(int,input().split())
    if find(c-1) == find(d-1):
        bc[c-1] += 1
        bc[d-1] += 1

for i in range(N):
    cnt = -tree[find(i)] - 1 - fc[i] - bc[i]
    ans[i] = cnt

print(*ans)

Submission status: Runtime Error

Solution code:
N, M, K = map(int,input().split())
tree = [-1 for i in range(N)]
fc = [0 for i in range(N)]
bc = [0 for i in range(N)]
ans = [0 for i in range(N)]

def find(x):
    # x を引数に取り、xのroot番号を取得するメモ化再帰
    if tree[x] < 0:
        return x
    tree[x] = find(tree[x])
    return tree[x]

def unite(x, y):
    # x, y を引数に取り、x(自分)をy(相手)のrootに接続する関数
    rootx = find(x)
    rooty = find(y)
    if rootx == rooty:
        return
    if rootx < rooty:
        x , y = y, x
    tree[rooty] += tree[rootx]
    tree[rootx] = rooty

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

for i in range(K):
    c, d = map(int,input().split())
    if find(c-1) == find(d-1):
        bc[c-1] += 1
        bc[d-1] += 1

for i in range(N):
    cnt = -tree[find(i)] - 1 - fc[i] - bc[i]
    ans[i] = cnt

print(*ans)

Submission status: Runtime Error

Solution code:
N, M, K = map(int,input().split())
tree = [-1 for i in range(N)]
fc = [0 for i in range(N)]
bc = [0 for i in range(N)]
ans = ""

def find(x):
    # x を引数に取り、xのroot番号を取得するメモ化再帰
    if tree[x] < 0:
        return x
    tree[x] = find(tree[x])
    return tree[x]

def unite(x, y):
    # x, y を引数に取り、x(自分)をy(相手)のrootに接続する関数
    rootx = find(x)
    rooty = find(y)
    if rootx == rooty:
        return
    if rootx < rooty:
        x , y = y, x
    tree[rooty] += tree[rootx]
    tree[rootx] = rooty
    return

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

for i in range(K):
    c, d = map(int,input().split())
    if find(c-1) == find(d-1):
        bc[c-1] += 1
        bc[d-1] += 1

for i in range(N):
    cnt = -tree[find(i)] - 1 - fc[i] - bc[i]
    ans += str(cnt)

print(' '.join(ans))

Submission status: Runtime Error

Solution code:
N, M, K = map(int,input().split())
frendunion = [[] for i in range(N)]
blockunion = [[] for i in range(N)]
tree = [-1 for i in range(N)]
bc = 0
ans = ""

def find(x):
    # x を引数に取り、xのroot番号を取得するメモ化再帰
    if tree[x] < 0:
        return x
    tree[x] = find(tree[x])
    return tree[x]

def unite(x, y):
    # x, y を引数に取り、x(自分)をy(相手)のrootに接続する関数
    rootx = find(x)
    rooty = find(y)
    if rootx == rooty:
        return
    if rootx < rooty:
        x , y = y, x
    tree[rooty] += tree[rootx]
    tree[rootx] = rooty
    return

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

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

for i in range(N):
    for j in blockunion[i]:
        if find(j) == find(i):
            bc += 1
    cnt = -tree[find(i)] - 1 - len(frendunion[i]) - bc
    ans += str(cnt)
    bc = 0

print(' '.join(ans))

Submission status: Runtime Error

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parents[y] = x
        self.parents[x] = x
        self.sizes[x] += self.sizes[y]
        self.sizes[y] = self.sizes[x]

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

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)

Submission status: Runtime Error

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]

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

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)

Submission status: Runtime Error

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

candidates = [0] * n
friends = [0] * n
blocks = [0] * n
parent = [i for i in range(n + 1)]
sizes = [1] * (n + 1)

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    if x == y:
        return
    parent[y] = x # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

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

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1

for i in range(n):
    candidates[i] = sizes[root(i)] - friends[i] - blocks[i] - 1

print(*candidates)

Submission status: Runtime Error

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

candidates = [0] * n
friends = [0] * n
blocks = [0] * n
parent = [i for i in range(n + 1)]
sizes = [1] * (n + 1)

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[y] = x # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    # sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

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

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1

for i in range(n):
    candidates[i] = sizes[root(i)] - friends[i] - blocks[i] - 1

print(*candidates)

Submission status: Runtime Error

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

candidates = [0] * n
friends = [0] * n
blocks = [0] * n
parent = [i for i in range(n + 1)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[y] = x # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    # sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

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

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1

for i in range(n):
    candidates[i] = sizes[root(i)] - friends[i] - blocks[i] - 1

print(*candidates)

Submission status: Runtime Error

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

candidates = [0] * n
friends = [0] * n
blocks = [0] * n
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[y] = x # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    # sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

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

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1

for i in range(n):
    candidates[i] = sizes[root(i)] - friends[i] - blocks[i] - 1

print(*candidates)

Submission status: Runtime Error

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

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[y] = x # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    # sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

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

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    candidates[i] = sizes[root(i)] - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Submission status: Runtime Error

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

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[y] = x # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

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

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    candidates[i] = sizes[root(i)] - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Submission status: Runtime Error

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

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[x] = y # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

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

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    candidates[i] = sizes[root(i)] - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Submission status: Runtime Error

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

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[x] = y # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

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

for _ in range(k):
    c, d = map(int, input().split())
    # if same(c - 1, d - 1):
    #     blocks[c - 1].add(d - 1)
    #     blocks[d - 1].add(c - 1)
    blocks[c - 1].add(d - 1)
    blocks[d - 1].add(c - 1)

for i in range(n):
    candidates[i] = sizes[root(i)] - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Submission status: Runtime Error

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

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[x] = y # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

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

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    x = root(i)
    # s = sizes[x]
    s = 0
    candidates[i] = s - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Submission status: Runtime Error

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

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    if x == y:
        return
    parent[x] = y
    # sizes[x] = sizes[x] + sizes[y]
    # sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

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

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    x = root(i)
    s = sizes[x]
    candidates[i] = s - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Submission status: Runtime Error

Solution code:
import numpy as np

class union_find:
    def __init__(self, N):
        self.parent = [0]*N
        for i in range(N):
            self.parent[i] = i
        self.size = [1]*N

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

    def match(self, i, j):
        return self.root(i) == self.root(j)

    def unit(self, i, j):
        x = self.root(i)
        y = self.root(j)
        if (x == y):
            return
        self.parent[x] = y
        self.size[y] = self.size[x] + self.size[y]

    def get_size(self, i):
        return self.size[self.root(i)]

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

num_friend = np.zeros(N)
for i in range(M):
    A, B = map(int, raw_input().split())
    uf.unit(A-1, B-1)
    num_friend[A-1] = num_friend[A-1] + 1
    num_friend[B-1] = num_friend[B-1] + 1

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

answers = []
for i in range(N):
    num_group = uf.get_size(i)
    num_f = num_friend[i]
    num_b = num_block[i]

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

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

Submission status: Runtime Error

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

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for i in range(n)]

def root(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    parent[x] = y
    sizes[x] = sizes[x] + sizes[y]
    sizes[y] = sizes[x]

def same(x, y):
    x = root(x)
    y = root(y)
    return x == y

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

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    x = root(i)
    s = sizes[x]
    candidates[i] = s - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Submission status: Runtime Error

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

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
dic = {}

def root(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    parent[x] = y

def same(x, y):
    x = root(x)
    y = root(y)
    return x == y

def size(x):
    global parent
    key = root(parent[x])
    s = 0
    for i in range(n):
        if root(parent[i]) == key:
            s += 1
    return s

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

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    x = root(i)
    s = 0
    if x in dic:
        s = dic[x]
    else:
        s = size(x)
        dic[x] = s
    candidates[i] = s - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)

Submission status: Runtime Error

Solution code:
import numpy as np
import math as m

def main(**kwargs):
    friends = {}
    blocks = {}

    for i in range(1, n + 1):
        friends[i] = []
        blocks[i] = []

    for i in range(m):
        friends[A[i]].append(B[i])
        friends[B[i]].append(A[i])

    for i in range(k):
        blocks[C[i]].append(D[i])
        blocks[D[i]].append(C[i])

    candidates = {}

    for i in range(1, n + 1):
        if not i in candidates.keys():
            cs = DFS(friends, i, [])

            for j in cs:
                candidates[j] = cs.copy()

    for i in range(1, n + 1):
        candidates[i].remove(i)

        for j in friends[i]:
            if j in candidates[i]:
                candidates[i].remove(j)

        for j in blocks[i]:
            if j in candidates[i]:
                candidates[i].remove(j)

    res = " ".join([str(len(candidates[i])) for i in range(1, n + 1)])
    return res

def DFS(G, s, vs):
    vs.append(s)

    for u in G[s]:
        if not u in vs:
            DFS(G, u, vs)

    return vs

if __name__ == "__main__":
    cin = np.array(input().split(" ")).astype("int")
    n, m, k, *_ = cin

    A = np.zeros(m, dtype="int")
    B = np.zeros(m, dtype="int")
    C = np.zeros(k, dtype="int")
    D = np.zeros(k, dtype="int")

    for i in range(m):
        cin = np.array(input().split(" ")).astype("int")
        A[i], B[i] = np.array(cin)

    for i in range(k):
        cin = np.array(input().split(" ")).astype("int")
        C[i], D[i] = np.array(cin)
    
    cout = main(n=n, m=m, k=k, A=A, B=B, C=C, D=D)
    print(cout)

Submission status: Runtime Error

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

candidates = [None] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
dic = {}

def root(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    parent[x] = y


def group(x):
    global parent
    key = root(parent[x])
    s = set()
    for i in range(n):
        if root(parent[i]) == key:
            s.add(i)
    return s

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

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

for i in range(n):
    x = root(i)
    s = set()
    if x in dic:
        s = dic[x]
    else:
        s = group(x)
        dic[x] = s
    candidates[i] = str(len(s - friends[i] - blocks[i]) - 1)

print(' '.join(candidates))