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 bisect
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, M, K, ABs, CDs):
    friend_map = [[] for _ in range(N + 1)]
    for a, b in ABs:
        friend_map[a].append(b)
        friend_map[b].append(a)

    block_map = [[] for _ in range(N + 1)]
    for c, d in CDs:
        block_map[c].append(d)
        block_map[d].append(c)

    # print('friend_map')
    # for i in range(len(friend_map)):
    #     print(friend_map[i])
    #
    # print('block_map')
    # for i in range(len(block_map)):
    #     print(block_map[i])

    def dfs(group_num, members, now_n):
        belongs[now_n] = group_num
        members.append(now_n)
        for f in friend_map[now_n]:
            if belongs[f] == -1:
                members = dfs(group_num, members, f)
        return members

    friend_groups = []
    belongs = [-1] * (N + 1)
    for i in range(1, N + 1):
        if belongs[i] == -1:
            m = dfs(len(friend_groups), [], i)
            m.sort()
            friend_groups.append(m)

    # print('friend_groups')
    # for i in range(len(friend_groups)):
    #     print(friend_groups[i])

    # print('belongs')
    # print(belongs)
    ans = ''
    for n in range(1, N + 1):
        block = 0
        group = friend_groups[belongs[n]]
        for b in block_map[n]:
            # if bisect.bisect_left(group, b) >= len(group):
            #     print(group)
            #     print(n, b)
            #     input()
            x = bisect.bisect_left(group, b)
            # if x < len(group) and b == group[x]:
            #     block += 1
            if belongs[n] == belongs[b]:
                block += 1
        # print('n', n, 'friend_num', len(friend_map[n]), 'block_num', block)
        ans += ' ' + str(len(group) - len(friend_map[n]) - block - 1)
    print(ans[1:])


if __name__ == '__main__':
    # # handmade test
    # N, M, K = 2 * 10 ** 5, 10 ** 5, 10 ** 5
    # ABs = [[1, i] for i in range(2, 10 ** 5 + 2)]
    # CDs = [[i, i + 1] for i in range(2, 10 ** 5 + 2)]
    # while True:
    #     import random
    #     N, M, K = 20, 10, 10
    #     ABs = []
    #     while True:
    #         if len(ABs) == M:
    #             break
    #         a = random.randint(1, N - 1)
    #         b = random.randint(a + 1, N)
    #         if not [a, b] in ABs:
    #             ABs.append([a, b])
    #     CDs = []
    #     while True:
    #         if len(CDs) == K:
    #             break
    #         c = random.randint(1, N - 1)
    #         d = random.randint(c + 1, N)
    #         if not [c, d] in ABs and not [c, d] in CDs:
    #             CDs.append([c, d])
    #     print(N, M, K)
    #     print(ABs)
    #     print(CDs)
    #     solve(N, M, K, ABs, CDs)

    N, M, K = map(int, input().split())
    ABs = [[int(i) for i in input().split()] for _ in range(M)]
    CDs = [[int(i) for i in input().split()] for _ in range(K)]
    solve(N, M, K, ABs, CDs)

Submission status: Runtime Error

Solution code:
import bisect
from decorator import stop_watch


@stop_watch
def solve(N, M, K, ABs, CDs):
    friend_map = [[] for _ in range(N + 1)]
    for a, b in ABs:
        friend_map[a].append(b)
        friend_map[b].append(a)

    block_map = [[] for _ in range(N + 1)]
    for c, d in CDs:
        block_map[c].append(d)
        block_map[d].append(c)

    # print('friend_map')
    # for i in range(len(friend_map)):
    #     print(friend_map[i])
    #
    # print('block_map')
    # for i in range(len(block_map)):
    #     print(block_map[i])

    def dfs(group_num, members, now_n):
        belongs[now_n] = group_num
        members.append(now_n)
        for f in friend_map[now_n]:
            if belongs[f] == -1:
                members = dfs(group_num, members, f)
        return members

    friend_groups = []
    belongs = [-1] * (N + 1)
    for i in range(1, N + 1):
        if belongs[i] == -1:
            m = dfs(len(friend_groups), [], i)
            m.sort()
            friend_groups.append(m)

    # print('friend_groups')
    # for i in range(len(friend_groups)):
    #     print(friend_groups[i])

    # print('belongs')
    # print(belongs)
    ans = ''
    for n in range(1, N + 1):
        block = 0
        group = friend_groups[belongs[n]]
        for b in block_map[n]:
            # if bisect.bisect_left(group, b) >= len(group):
            #     print(group)
            #     print(n, b)
            #     input()
            x = bisect.bisect_left(group, b)
            # if x < len(group) and b == group[x]:
            #     block += 1
            if belongs[n] == belongs[b]:
                block += 1
        # print('n', n, 'friend_num', len(friend_map[n]), 'block_num', block)
        ans += ' ' + str(len(group) - len(friend_map[n]) - block - 1)
    print(ans[1:])


if __name__ == '__main__':
    # # handmade test
    # N, M, K = 2 * 10 ** 5, 10 ** 5, 10 ** 5
    # ABs = [[1, i] for i in range(2, 10 ** 5 + 2)]
    # CDs = [[i, i + 1] for i in range(2, 10 ** 5 + 2)]
    # while True:
    #     import random
    #     N, M, K = 20, 10, 10
    #     ABs = []
    #     while True:
    #         if len(ABs) == M:
    #             break
    #         a = random.randint(1, N - 1)
    #         b = random.randint(a + 1, N)
    #         if not [a, b] in ABs:
    #             ABs.append([a, b])
    #     CDs = []
    #     while True:
    #         if len(CDs) == K:
    #             break
    #         c = random.randint(1, N - 1)
    #         d = random.randint(c + 1, N)
    #         if not [c, d] in ABs and not [c, d] in CDs:
    #             CDs.append([c, d])
    #     print(N, M, K)
    #     print(ABs)
    #     print(CDs)
    #     solve(N, M, K, ABs, CDs)

    N, M, K = map(int, input().split())
    ABs = [[int(i) for i in input().split()] for _ in range(M)]
    CDs = [[int(i) for i in input().split()] for _ in range(K)]
    solve(N, M, K, ABs, CDs)

Submission status: Runtime Error

Solution code:
import bisect
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, M, K, ABs, CDs):
    friend_map = [[] for _ in range(N + 1)]
    for a, b in ABs:
        friend_map[a].append(b)
        friend_map[b].append(a)

    block_map = [[] for _ in range(N + 1)]
    for c, d in CDs:
        block_map[c].append(d)
        block_map[d].append(c)

    # print('friend_map')
    # for i in range(len(friend_map)):
    #     print(friend_map[i])
    #
    # print('block_map')
    # for i in range(len(block_map)):
    #     print(block_map[i])

    def bfs(group_num, members, now_n):
        belongs[now_n] = group_num
        members.append(now_n)
        for f in friend_map[now_n]:
            if belongs[f] == -1:
                members = bfs(group_num, members, f)
        return members

    friend_groups = []
    belongs = [-1] * (N + 1)
    for i in range(1, N + 1):
        if belongs[i] == -1:
            m = bfs(len(friend_groups), [], i)
            m.sort()
            friend_groups.append(m)

    # print('friend_groups')
    # for i in range(len(friend_groups)):
    #     print(friend_groups[i])

    # print('belongs')
    # print(belongs)
    ans = ''
    for n in range(1, N + 1):
        block = 0
        group = friend_groups[belongs[n]]
        for b in block_map[n]:
            # if bisect.bisect_left(group, b) >= len(group):
            #     print(group)
            #     print(n, b)
            #     input()
            x = bisect.bisect_left(group, b)
            if x < len(group) and b == group[x]:
                block += 1
        # print('n', n, 'friend_num', len(friend_map[n]), 'block_num', block)
        ans += ' ' + str(len(group) - len(friend_map[n]) - block - 1)
    print(ans[1:])


if __name__ == '__main__':
    # # handmade test
    # N, M, K = 2 * 10 ** 5, 10 ** 5, 10 ** 5
    # ABs = [[1, i] for i in range(2, 10 ** 5 + 2)]
    # CDs = [[i, i + 1] for i in range(2, 10 ** 5 + 2)]

    N, M, K = map(int, input().split())
    ABs = [[int(i) for i in input().split()] for _ in range(M)]
    CDs = [[int(i) for i in input().split()] for _ in range(K)]
    solve(N, M, K, ABs, CDs)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
N, M, K = map(int,input().split())
class UnionFind:
    def __init__(self, N):
        self.par = [-1 for i in range(N+1)]
        self.rank = [1]*(N+1)
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] > self.rank[y]:
            self.par[x] += self.par[y]
            self.par[y] = x
        else:
            self.par[y] += self.par[x]
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

UF = UnionFind(N)
friendlist = [[] for _ in range(N+1)]
for n in range(M):
    A, B = map(int,input().split())
    friendlist[A].append(B)
    friendlist[B].append(A)
    if not UF.same_check(A,B):
        UF.union(A, B)
blocklist = [[] for _ in range(N+1)]
for n in range(K):
    C, D = map(int, input().split())
    blocklist[C].append(D)
    blocklist[D].append(C)

for person in range(1,N+1):
    root = UF.find(person)
    ans = -UF.par[root]-1
    ans -= len(friendlist[person])
    for l in blocklist[person]:
        if UF.same_check(person,l):
            ans -= 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**10)
N, M, K = map(int,input().split())
class UnionFind:
    def __init__(self, N):
        self.par = [-1 for i in range(N+1)]
        self.rank = [1]*(N+1)
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] > self.rank[y]:
            self.par[x] += self.par[y]
            self.par[y] = x
        else:
            self.par[y] += self.par[x]
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

UF = UnionFind(N)
friendlist = [[] for _ in range(N+1)]
for n in range(M):
    A, B = map(int,input().split())
    friendlist[A].append(B)
    friendlist[B].append(A)
    if not UF.same_check(A,B):
        UF.union(A, B)
blocklist = [[] for _ in range(N+1)]
for n in range(K):
    C, D = map(int, input().split())
    blocklist[C].append(D)
    blocklist[D].append(C)

for person in range(1,N+1):
    root = UF.find(person)
    ans = -UF.par[root]-1
    ans -= len(friendlist[person])
    for l in blocklist[person]:
        if UF.same_check(person,l):
            ans -= 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000)
N, M, K = map(int,input().split())
class UnionFind:
    def __init__(self, N):
        self.par = [-1 for i in range(N+1)]
        self.rank = [1]*(N+1)
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] > self.rank[y]:
            self.par[x] += self.par[y]
            self.par[y] = x
        else:
            self.par[y] += self.par[x]
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

UF = UnionFind(N)
friendlist = [[] for _ in range(N+1)]
for n in range(M):
    A, B = map(int,input().split())
    friendlist[A].append(B)
    friendlist[B].append(A)
    if not UF.same_check(A,B):
        UF.union(A, B)
blocklist = [[] for _ in range(N+1)]
for n in range(K):
    C, D = map(int, input().split())
    blocklist[C].append(D)
    blocklist[D].append(C)

for person in range(1,N+1):
    root = UF.find(person)
    ans = -UF.par[root]-1
    ans -= len(friendlist[person])
    for l in blocklist[person]:
        if UF.same_check(person,l):
            ans -= 1
    print(ans)

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(2000)
N, M, K = map(int,input().split())
class UnionFind:
    def __init__(self, N):
        self.par = [-1 for i in range(N+1)]
        self.rank = [1]*(N+1)
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] > self.rank[y]:
            self.par[x] += self.par[y]
            self.par[y] = x
        else:
            self.par[y] += self.par[x]
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

UF = UnionFind(N)
friendlist = [[] for _ in range(N+1)]
for n in range(M):
    A, B = map(int,input().split())
    friendlist[A].append(B)
    friendlist[B].append(A)
    if not UF.same_check(A,B):
        UF.union(A, B)
blocklist = [[] for _ in range(N+1)]
for n in range(K):
    C, D = map(int, input().split())
    blocklist[C].append(D)
    blocklist[D].append(C)

for person in range(1,N+1):
    root = UF.find(person)
    ans = -UF.par[root]-1
    ans -= len(friendlist[person])
    for l in blocklist[person]:
        if UF.same_check(person,l):
            ans -= 1
    print(ans)

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(2000)
from collections import deque
K = int(input())
d = deque(["1","2","3","4","5","6","7","8","9"])
ans = 0
for i in range(K):
    now = d.popleft()
    num = int(now[-1])
    if num == 0:
        d.append(now+"0")
        d.append(now+"1")
    elif num == 9:
        d.append(now+"8")
        d.append(now+"9")
    else:
        d.append(now+str(num-1))
        d.append(now+str(num))
        d.append(now+str(num+1))
print(now)

Submission status: Runtime Error

Solution code:
N, M, K = map(int,input().split())
class UnionFind:
    def __init__(self, N):
        self.par = [-1 for i in range(N+1)]
        self.rank = [1]*(N+1)
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] > self.rank[y]:
            self.par[x] += self.par[y]
            self.par[y] = x
        else:
            self.par[y] += self.par[x]
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

UF = UnionFind(N)
friendlist = [[] for _ in range(N+1)]
for n in range(M):
    A, B = map(int,input().split())
    friendlist[A].append(B)
    friendlist[B].append(A)
    if not UF.same_check(A,B):
        UF.union(A, B)
blocklist = [[] for _ in range(N+1)]
for n in range(K):
    C, D = map(int, input().split())
    blocklist[C].append(D)
    blocklist[D].append(C)

for person in range(1,N+1):
    root = UF.find(person)
    ans = -UF.par[root]-1
    ans -= len(friendlist[person])
    for l in blocklist[person]:
        if UF.same_check(person,l):
            ans -= 1
    print(ans)

Submission status: Runtime Error

Solution code:
N, M, K = map(int,input().split())
class UnionFind:
    def __init__(self, N):
        self.par = [-1 for i in range(N+1)]
        self.rank = [1]*(N+1)
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] > self.rank[y]:
            self.par[x] += self.par[y]
            self.par[y] = x
        else:
            self.par[y] += self.par[x]
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

UF = UnionFind(N)
friendlist = [[] for _ in range(N+1)]
for n in range(M):
    A, B = map(int,input().split())
    friendlist[A].append(B)
    friendlist[B].append(A)
    if not UF.same_check(A,B):
        UF.union(A, B)
blocklist = [[] for _ in range(N+1)]
for n in range(K):
    C, D = map(int, input().split())
    blocklist[C].append(D)
    blocklist[D].append(C)

for person in range(1,N+1):
    root = UF.find(person)
    ans = -UF.par[root]-1
    ans -= len(friendlist[person])
    for l in blocklist[person]:
        if UF.same_check(person,l):
            ans -= 1
    print(ans)

Submission status: Runtime Error

Solution code:
N, M, K = map(int,input().split())
class UnionFind:
    def __init__(self, N):
        self.par = [-1 for i in range(N+1)]
        self.rank = [1]*(N+1)
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] > self.rank[y]:
            self.par[x] += self.par[y]
            self.par[y] = x
        else:
            self.par[y] += self.par[x]
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

UF = UnionFind(N)
friendlist = [[] for _ in range(N+1)]
for n in range(M):
    A, B = map(int,input().split())
    friendlist[A].append(B)
    friendlist[B].append(A)
    if not UF.same_check(A,B):
        UF.union(A, B)
blocklist = [[] for _ in range(N+1)]
for n in range(K):
    C, D = map(int, input().split())
    blocklist[C].append(D)
    blocklist[D].append(C)

for person in range(1,N+1):
    root = UF.find(person)
    ans = -UF.par[root]-1
    ans -= friendlist[person]
    for l in blocklist[person]:
        if UF.same_check(person,l):
            ans -= 1
    print(ans)

Submission status: Runtime Error

Solution code:
N, M, K = map(int,input().split())
class UnionFind:
    def __init__(self, N):
        self.par = [-1 for i in range(N+1)]
        self.rank = [1]*(N+1)
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] > self.rank[y]:
            self.par[x] += self.par[y]
            self.par[y] = x
        else:
            self.par[y] += self.par[x]
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

UF = UnionFind(N)
friendlist = [[] for _ in range(N+1)]
for n in range(M):
    A, B = map(int,input().split())
    friendlist[A].append(B)
    friendlist[B].append(A)
    if not UF.same_check(A,B):
        UF.union(A, B)
blocklist = [[] for _ in range(N+1)]
for n in range(K):
    C, D = map(int, input().split())
    blocklist[C].append(D)
    blocklist[D].append(C)

for person in range(1,N+1):
    root = UF.find(person)
    ans = -UF.par[root]-1
    dellist = friendlist[person]+blocklist[person]
    for l in dellist:
        if UF.same_check(person,l):
            ans -= 1
    print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

class UnionFind():
        def __init__(self, n):
            self.parents = list(range(n))
            self.size = [1] * n
    
        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 union(self, x, y):
            x = self.find(x)
            y = self.find(y)
            if x != y:
                self.parents[y] = x
                self.size[x] += self.size[y]

def main():
    N, M, K = map(int, input().split())
    friend_adj = [[] for _ in range(N)]
    block_adj = [[] for _ in range(N)]
    uf = UnionFind(N)

    for _ in range(M):
        a, b = map(lambda x: int(x)-1, input().split())
        friend_adj[a].append(b)
        friend_adj[b].append(a)
        uf.union(a,b)
    for _ in range(K):
        c, d = map(lambda x: int(x)-1, input().split())
        if uf.find(c) == uf.find(d):
            friend_adj[c].append(d)
            friend_adj[d].append(c)

    ans = [uf.size[uf.find(i)]-1 for i in range(N)]

    for i in range(N):
        ans[i] -= len(friend_adj[i])        
        # for b in block_adj[i]:
        #     if uf.find(b) == uf.find(i):
        #         ans[i] -= 1
    print(*ans)
    
    
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import deque

class UnionFind():
        def __init__(self, n):
            self.parents = list(range(n))
            self.size = [1] * n
    
        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 union(self, x, y):
            x = self.find(x)
            y = self.find(y)
            if x != y:
                self.parents[y] = x
                self.size[x] += self.size[y]

def main():
    N, M, K = map(int, input().split())
    friend_adj = [[] for _ in range(N)]
    block_adj = [[] for _ in range(N)]

    for _ in range(M):
        a, b = map(lambda x: int(x)-1, input().split())
        friend_adj[a].append(b)
        friend_adj[b].append(a)
    for _ in range(K):
        c, d = map(lambda x: int(x)-1, input().split())
        block_adj[c].append(d)
        block_adj[d].append(c)

    uf = UnionFind(N)
    for i in range(N):
        for v in friend_adj[i]:
            uf.union(i,v)

    ans = [uf.size[uf.find(i)]-1 for i in range(N)]

    for i in range(N):
        ans[i] -= len(friend_adj[i])        
        for b in block_adj[i]:
            if uf.find(b) == uf.find(i):
                ans[i] -= 1
    print(*ans)
    # print(uf.parents, uf.size)
    
    
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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


v=[0]*n
l=[0]*n
w=[0]*n

def dfs(now,c):
    global ln
    if v[now]==1:
        return
    v[now]=1
    ln+=1
    w[now]=c
    l[c]=ln
    for i in r[now]:
        dfs(i,c)
    return

for i in range(n):
    ln=0
    dfs(i,i)

ans =[]
for i in range(n):
    d=0
    for j in bk[i]:
        if w[j]==w[i]:
            d+=1
    ans.append(str(l[w[i]]-1-d-len(r[i])))
print(' '.join(ans))

Submission status: Runtime Error

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n,m,k=nm()

fr=[[] for _ in range(n)]
bl=[[] for _ in range(n)]


for i in range(m):
  a,b=nm()
  fr[a-1].append(b-1)
  fr[b-1].append(a-1)
for i in range(k):
  c,d=nm()
  bl[c-1].append(d-1)
  bl[d-1].append(c-1)

def dfs(owner,num,visited):
  ans=0
  if owner!=num and num not in fr[owner]:
    ans+=1
  for e in fr[num]:
    if e not in visited:
      visited.add(e)
      if e not in bl[owner]:
        ans+=dfs(owner,e,visited)

  return ans

for i in range(n):
  print(dfs(i,i,set()))

Submission status: Runtime Error

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

g = [[] for i in range(n+1)]
f = [0]*(n+1)
b = []
for i in range(m):
  u, v = map(int, input().split())
  g[u].append(v)
  g[v].append(u)
  f[u] += 1
  f[v] += 1
for i in range(k):
  b.append(map(int, input().split()))

count = 0
renketu_list = [-1]*(n+1)
renketu_size = [0]
stack = []
for i in range(1, n+1):
  if renketu_list[i] == -1:
    count += 1
    renketu_list[i] = count
    renketu_size.append(1)
    while len(g[i]) > 0:
      stack.append(g[i].pop())
    while len(stack) > 0:
      u,v=stack.pop()
      if renketu_list[v] == -1:
        renketu_list[v] = count
        renketu_size[count] += 1
        while len(g[v])>0:
          stack.append(g[v].pop())

s = [0] * (n+1)
for i in range(1, n):
  s[i] += renketu_size[renketu_list[i]] + f[i]
  
for i in range(k):
  u, v = b[i]
  if renketu_list[u] == renketu_list[v]:
    s[u] -= 1
    s[v] -= 1

print(" ".join(list(map(str, s))))

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())
ab = []
for _ in range(m):
    ab.append([int(x)-1 for x in input().split()])
cd = []
for _ in range(k):
    cd.append([int(x)-1 for x in input().split()])
group = [-1 for _ in range(n)]
lis = [[] for _ in range(n)]
for x in ab:
    a = x[0]
    b = x[1]
    lis[a].append(b)
    lis[b].append(a)
g_n = 0
def dfs(now):
    global g_n
    group[now] = g_n
    global group_len_n
    group_len_n += 1
    for i in lis[now]:
        if group[i] == -1:
            dfs(i)
group_len = []
for i in range(n):
    if group[i] == -1:
        group_len_n = 0
        dfs(i)
        group_len.append(group_len_n)
        g_n += 1
friend = [0 for _ in range(n)]
block = [0 for _ in range(n)]
for x in ab:
    a = x[0]
    b = x[1]
    if group[a] == group[b]:
        friend[a] += 1
        friend[b] += 1
for x in cd:
    c = x[0]
    d = x[1]
    if group[c] == group[d]:
        block[c] += 1
        block[d] += 1
ans = []
for i in range(n):
    ans.append(str(group_len[group[i]] - friend[i] - block[i] -1))
print(" ".join(ans))

Submission status: Runtime Error

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

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

VISITED = 1
NOT_VISITED = 0
visit = [ NOT_VISITED for _ in range( n ) ]
graph_id = [ -1 for _ in range( n ) ]

def dfs( ver, g_id ):
    if graph_id[ ver ] == -1:
        graph_id[ ver ] = g_id
    else:
        return
    for next_v in friend[ ver ]:
        dfs( next_v, g_id )

g_id = 0
for ver in range( n ):
    if graph_id[ ver ] != -1:
        continue
    dfs( ver, g_id )
    g_id += 1

graph_size = [ 0 for _ in range( n ) ]
for ver in range( n ):
    graph_size[ graph_id[ ver ] ] += 1

ans = [ graph_size[ graph_id[ ver ] ] for ver in range( n ) ]

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

for ver in range( n ):
    ans[ ver ] = ans[ ver ] - len( friend[ ver ] ) - 1

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

Submission status: Runtime Error

Solution code:
def abc157_d():
    N, M, K = map(int, input().split())
    fr = [set() for _ in range(N)]
    bl = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        fr[a].add(b)
        fr[b].add(a)
    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        bl[c].add(d)
        bl[d].add(c)

    def dfs(nd, lb):
        nonlocal label, gr
        label[nd] = lb
        gr[lb].add(nd)
        for ch in fr[nd]:
            if label[ch] != -1: continue
            dfs(ch, lb)

    label = [-1] * N
    lb = 0
    gr = []
    for i in range(N):
        if label[i] != -1: continue
        gr.append(set())
        dfs(i, lb)
        lb += 1

    ans = [0] * N
    for i in range(N):
        cand = gr[label[i]] - fr[i] - bl[i]
        ans[i] = len(cand) - 1
    print(*ans, sep=' ')

abc157_d()