Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Runtime Error

Solution code:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] > rank[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x

def uCnt(x):
    return -par[find(x)]

N, M, K = map(int, input().split())
par = [-1 for i in range(N)]
rank = [0] * N
frendCnt = [0] * N
bloc = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    frendCnt[a] += 1
    frendCnt[b] += 1
    unite(a, b)

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

for i in range(N):
    ans = uCnt(i) - frendCnt[i] - 1
    for j in bloc[i]:
       if same(i, j):
           ans -= 1
    print(ans, end=' ')

Submission status: Runtime Error

Solution code:
# coding: utf-8


def dfs(node: int):
    if node in checked:
        return

    checked.add(node)
    chain.add(node)
    for n in friends[node]-checked:
        dfs(n)


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    AB = [tuple(map(int, ab)) for ab in map(str.split, args[1:1+m])]
    CD = [tuple(map(int, cd)) for cd in map(str.split, args[1+m:1+m+k])]

    global checked
    checked = set()

    global friends
    friends = [set() for _ in range(n+1)]
    blocked = [set() for _ in range(n+1)]

    for a, b in AB:
        friends[a].add(b)
        friends[b].add(a)

    for c, d in CD:
        blocked[c].add(d)
        blocked[d].add(c)

    ret = [0]*(n+1)
    for a in range(1, n+1):
        if a in checked:
            continue

        global chain
        chain = set()
        dfs(a)
        for i in chain:
            ret[i] += len(chain-friends[i]-blocked[i]) - 1

    return ' '.join(map(str, ret[1:]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Runtime Error

Solution code:
# https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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

friend = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)

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

ans = [len(set(uf.size(i)) - set(friend[i]) - set(block[i])) - 1 for i in range(N)]
print(*ans)

Submission status: Runtime Error

Solution code:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] > rank[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x

def uCnt(x):
    return -par[find(x)]

N, M, K = map(int, input().split())
par = [-1 for i in range(N)]
rank = [0] * N
frendCnt = [0] * N
bloc = [[] for _ in range(N)]
for i in range(N):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    frendCnt[a] += 1
    frendCnt[b] += 1
    unite(a, b)

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

for i in range(N):
    ans = uCnt(i) - len(bloc[i]) - frendCnt[i] - 1
    print(ans, end=' ')

Submission status: Runtime Error

Solution code:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] > rank[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x

def uCnt(x):
    return -par[find(x)]

N, M, K = map(int, input().split())
par = [-1 for i in range(N)]
rank = [0] * N
frendCnt = [0] * N
bloc = [[] for _ in range(N)]
for i in range(N):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    frendCnt[a] += 1
    frendCnt[b] += 1
    unite(a, b)

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

for i in range(N):
    ans = uCnt(i) - len(bloc[i]) - frendCnt[i] - 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

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


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

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x]=y

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(min(a-1,b-1),max(a-1,b-1),li1)
# for i in range(K):
#     c = CD[i][0]
#     d = CD[i][1]
#     union(c-1,d-1,li2)

mm = [0 for i in range(max(li1)+1)]
for i in range(N):
    m = root(i,li1)
    mm[m] += 1

print(li1,file=sys.stderr)
print(mm,file=sys.stderr)
ans = [mm[li1[i]]-1 for i in range(N)]
# print(ans)

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


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

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


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

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x]=y

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(min(a-1,b-1),max(a-1,b-1),li1)
# for i in range(K):
#     c = CD[i][0]
#     d = CD[i][1]
#     union(c-1,d-1,li2)

mm = [0 for i in range(max(li1)+1)]
for i in range(N):
    m = root(i,li1)
    mm[m] += 1

print(li1,file=sys.stderr)
print(mm,file=sys.stderr)
ans = [mm[li1[i]-1]-1 for i in range(N)]
# print(ans)

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


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(2147483647)

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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

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

uf = UnionFind(n)

f = np.zeros((n,n),np.int32)
r = np.zeros((n,n),np.int32)
for i in range(m):
    a,b = map(int, input().split())
    f[a-1][b-1] = 1
    f[b-1][a-1] = 1
    uf.union(a-1, b-1)

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

q = f + r

ans = np.zeros((n),np.int32)
for i in range(n):
    for j in range(n):
        if not i == j and q[i][j] == 0 and uf.is_same(i,j):
            ans[i] += 1
            
print(*ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self,N):
        self.par =[-1 for i in range(N)]
    def find(self,x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

    def size(self,x):
        if self.par[x] < 0:
            return -self.par[x]
        else:
            self.par[x] = self.size(self.par[x])
            return self.par[x]
    def same(self,x,y):
        return self.find(x)==self.find(y)

N,M,K=map(int,input().split(' '))
Friend = UnionFind(N)
pull = [-1] * N
for i in range(M):
    a,b = map(int,input().split(' '))
    Friend.unite(a-1,b-1)
    pull[a-1] -= 1
    pull[b-1] -= 1
for i in range(K):
    c,d=map(int,input().split(' '))
    if Friend.same(c-1,d-1):
        pull[c-1] -=1
        pull[d-1] -=1
print(' '.join([str(Friend.size(i)+pull[i]) for i in range(N)]))

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited


if __name__ == "__main__":
    n, m, k = map(int, input().split())
    AB = [map(int, input().split()) for _ in range(m)]
    CD = [map(int, input().split()) for _ in range(k)]

    graph_f = defaultdict(set)
    graph_b = defaultdict(set)

    for a, b in AB:
        graph_f[a - 1].add(b - 1)
        graph_f[b - 1].add(a - 1)

    for c, d in CD:
        graph_b[c - 1].add(d - 1)
        graph_b[d - 1].add(c - 1)

    visited = set()
    conns = {}
    for i in range(n):
        if i not in visited:
            conn = dfs(graph_f, i)
            visited |= {i} | conn
            conns = {**conns, **{j: conn for j in conn}}

    print(' '.join([str(len(conns[i] - graph_f[i] - graph_b[i]) - 1) for i in range(n)]))

Submission status: Runtime Error

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

NIL = -1
N, M, K = map(int, input().split())
friends = [deque() for i in range(N)]
block = [deque() for i in range(N)]
prefriends = [deque() for i in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    friends[A].append(B)
    friends[B].append(A)

for i in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    block[C].append(D)
    block[D].append(C)


def dfs(x, y):
    for i in friends[y]:
        if check[i]:
            #print(i)
            prefriends[x].append(i)
            #print(set(prefriends[x]))
            check[i] = False
            dfs(x, i)
ans = [0]*N
#print(prefriends)
for j in range(N):
    #print(prefriends[j])
    check = [True]*N
    check[j] = False
    dfs(j, j)
    #print(set(prefriends[j]))
    #print(set(friends[j]))
    #print(set(block[j]))
    #print((set(prefriends[j]) - set(friends[j])) - set(block[j]))
    
    ans[j] = (set(prefriends[j]) - set(friends[j])) - set(block[j])
    #print(ans[j])
    #print()
ans = [len(ans[i]) for i in range(N)]
print(*ans)

Submission status: Runtime Error

Solution code:
friend_dic = {}
block_dic = {}
results = {}
N, M, K = map(int, input().split())

for i in range(1, N+1):
    friend_dic[i] = []
    block_dic[i] = []
    results[i] = None

for _ in range(M):
    a, b = map(int, input().split())
    friend_dic[a].append(b)
    friend_dic[b].append(a)

for _ in range(K):
    a, b = map(int, input().split())
    block_dic[a].append(b)
    block_dic[b].append(a)

def dfs(graph, start, cluster):
    cluster.append(start)
    for neighbor in graph[start]:
        if neighbor not in cluster:
            dfs(graph, neighbor, cluster)


result = []
for i in range(1, N+1):
    if results[i] is not None:
        result += results[i]
    else:
        cluster = []
        dfs(friend_dic, i, cluster)
        for v in cluster:
            results[v] = str(len(set(cluster) - set(friend_dic[v]) - set(block_dic[v])) - 1)
        result += results[i]
print(" ".join(result))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

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


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

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x]=y

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(min(a-1,b-1),max(a-1,b-1),li1)
# for i in range(K):
#     c = CD[i][0]
#     d = CD[i][1]
#     union(c-1,d-1,li2)

mm = [0 for i in range(max(li1))]
for i in range(N):
    m = root(i,li1)
    mm[m-1] += 1

print(li1,file=sys.stderr)
print(mm,file=sys.stderr)
ans = [mm[li1[i]-1]-1 for i in range(N)]
# print(ans)

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


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)

Submission status: Runtime Error

Solution code:
friend_dic = {}
block_dic = {}
results = {}

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

for i in range(1, N+1):
    friend_dic[i] = []
    block_dic[i] = []
    results[i] = None

for _ in range(M):
    a, b = map(int, input().split())
    friend_dic[a].append(b)
    friend_dic[b].append(a)

for _ in range(K):
    a, b = map(int, input().split())
    block_dic[a].append(b)
    block_dic[b].append(a)

def dfs(graph, start, cluster):
    cluster.append(start)
    for neighbor in graph[start]:
        if neighbor not in cluster:
            dfs(graph, neighbor, cluster)


result = []
for i in range(1, N+1):
    if results[i] is not None:
        result += results[i]
    else:
        cluster = []
        dfs(friend_dic, i, cluster)
        for v in cluster:
            results[v] = str(len(set(cluster) - set(friend_dic[v]) - set(block_dic[v])) - 1)
        result += results[i]
print(" ".join(result))

Submission status: Runtime Error

Solution code:
#!/bin/bash
""":"
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"
exit $?
"""
import sys


def _ia(offset=0): return [int(x) + offset for x in sys.stdin.readline().strip().split()]


def visit(g, i, c, adj, flag):
    if flag[i]: return

    g[i] = c
    flag[i] = True
    update = False
    for j in adj[i]:
        if flag[j]: continue
        update = True
        _ = visit(g, j, c, adj, flag)
    if update: c += 1
    return c


def main():
    n, m, k = _ia()
    ab = []
    adj = [[] for _ in range(n)]
    for _ in range(m):
        i, j = _ia(-1)
        ab.append([i, j])
        adj[i].append(j)
        adj[j].append(i)

    g = [i for i in range(n)]
    flag = [False] * n
    cnt = 0
    for i in range(n):
        cnt = visit(g, i, cnt, adj, flag)

    for _ in range(23):
        for abi in ab:
            i, j = abi
            g[i] = g[j] = min(g[i], g[j])
    for _ in range(k):
        ab.append(_ia(-1))

    ng = max(g) + 1
    dg = [0] * ng
    for gi in g: dg[gi] += 1

    r = [0] * n
    for abi in ab:
        i, j = abi
        gi, gj = g[i], g[j]
        if gi == gj:
            r[i] += 1
            r[j] += 1
    return " ".join([str(dg[g[i]] - r[i] - 1) for i in range(n)])


if __name__ == "__main__":
    print(main())

Submission status: Runtime Error

Solution code:
def search_friends(friends, current_f_sets, me):
    new_f_sets = current_f_sets
    for f in current_f_sets:
        me.add(f)
        new_f_sets = new_f_sets | search_friends(friends, friends[f]["f"] - me, me)
    return new_f_sets

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

friends = []
for _ in range(N):
    friends.append({"f": set([]), "b": set([])})
for _ in range(M):
    A, B = map(int, input().split(' '))
    friends[A-1]["f"].add(B-1)
    friends[B-1]["f"].add(A-1)
for _ in range(K):
    C, D = map(int, input().split(' '))
    friends[C-1]["b"].add(D-1)
    friends[D-1]["b"].add(C-1)


n_cands = []
for me in range(N):
    cands = search_friends(friends, friends[me]["f"], set([me]))
    cands = cands - set([me]) - friends[me]["f"] - friends[me]["b"]
    n_cands.append(len(cands))

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

Submission status: Runtime Error

Solution code:
friend_dic = {}
block_dic = {}
clusters = {}

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

for i in range(1, N+1):
    friend_dic[i] = []
    block_dic[i] = []
    clusters[i] = None

for _ in range(M):
    a, b = map(int, input().split())
    friend_dic[a].append(b)
    friend_dic[b].append(a)

for _ in range(K):
    a, b = map(int, input().split())
    block_dic[a].append(b)
    block_dic[b].append(a)

def dfs(graph, start, cluster):
    cluster.append(start)
    for neighbor in graph[start]:
        if neighbor not in cluster:
            dfs(graph, neighbor, cluster)


result = ""
for i in range(1, N+1):
    if clusters[i] is not None:
        cluster = clusters[i]
    else:
        cluster = []
        dfs(friend_dic, i, cluster)
        for v in cluster:
            clusters[v] = cluster
    result += str(len(set(cluster) - set(friend_dic[i]) - set(block_dic[i])) - 1)
print(" ".join(result))

Submission status: Runtime Error

Solution code:
import sys

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


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

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x]=y

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(min(a-1,b-1),max(a-1,b-1),li1)
# for i in range(K):
#     c = CD[i][0]
#     d = CD[i][1]
#     union(c-1,d-1,li2)

mm = [0 for i in range(max(li1))]
for i in range(N):
    m = root(i,li1)
    mm[m-1] += 1

print(li1,file=sys.stderr)
print(mm,file=sys.stderr)
ans = [mm[li1[i]-1]-1 for i in range(N)]
# print(ans)

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


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)

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

A = [0 for _ in range(N)]
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]
answer = [[] for _ in range(N)]

for a, b in AB:
  friend[a-1].append(b)
  friend[b-1].append(a)

for c, d in CD:
  block[c-1].append(d)
  block[d-1].append(c)

def search(root, fs, check):
  for f in fs:
    if check[f-1] != 0 or f == root:
      continue
    else:
      check[f-1] = 1
    search(root, friend[f-1], check)
    if f not in block[root-1] and f not in friend[root-1] and f != root:
      if f not in answer[root-1]:
        answer[root-1].append(f)

for i in range(N):
  search(i+1, friend[i], [0 for _ in range(N)])

for i in range(N):
  A[i] = len(answer[i])

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

Submission status: Runtime Error

Solution code:
import sys

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


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

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x]=y

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    union(min(a-1,b-1),max(a-1,b-1),li1)
# for i in range(K):
#     c = CD[i][0]
#     d = CD[i][1]
#     union(c-1,d-1,li2)

mm = [0 for i in range(max(li1))]
for i in range(N):
    m = root(i,li1)
    mm[m-1] += 1

# print(li1)
# print(mm)
ans = [mm[li1[i]-1]-1 for i in range(N)]
# print(ans)

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


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)

Submission status: Runtime Error

Solution code:
friend_dic = {}
block_dic = {}
cluster_sizes = {}

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

for i in range(N):
    friend_dic[i+1] = []
    block_dic[i+1] = []
    cluster_sizes[i+1] = 0

for _ in range(M):
    a, b = map(int, input().split())
    friend_dic[a].append(b)
    friend_dic[b].append(a)

for _ in range(K):
    a, b = map(int, input().split())
    block_dic[a].append(b)
    block_dic[b].append(a)

def dfs(graph, start, cluster):
    cluster.append(start)
    for neighbor in graph[start]:
        if neighbor not in cluster:
            dfs(graph, neighbor, cluster)


result = ""
for i in range(1, N+1):
    if cluster_sizes[i] != 0:
        cluster_size = cluster_sizes[i]
    else:
        cluster = []
        dfs(friend_dic, i, cluster)
        cluster_size = len(cluster)
        for v in cluster:
            cluster_sizes[v] = cluster_size
    result += str(cluster_size - len(friend_dic[i]) - len(block_dic[i]) - 1)

print(" ".join(result))

Submission status: Runtime Error

Solution code:
friend_dic = {}
block_dic = {}
cluster_size = {}

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

for i in range(N):
    friend_dic[i+1] = 0
    block_dic[i+1] = 0
    cluster_size[i+1] = 0

for _ in range(M):
    a, b = map(int, input().split())
    friend_dic[a] += 1
    friend_dic[b] += 1

for _ in range(K):
    a, b = map(int, input().split())
    block_dic[a] += 1
    block_dic[b] += 1

def dfs(graph, start, cluster):
    cluster.append(start)
    for neighbor in graph[start]:
        if neighbor not in cluster:
            dfs(graph, neighbor, cluster)


result = ""
for i in range(1, N+1):
    if cluster_sizes[i] != 0:
        cluster_size = cluster_sizes[i]
    else:
        cluster = []
        dfs(friend_dic, i, cluster)
        cluster_size = len(cluster)
        for v in cluster:
            cluster_sizes[v] = cluster_size
    result += str(cluster_size - friend_dic[i] - block_dic[i] - 1)

print(" ".join(result))

Submission status: Runtime Error

Solution code:
for i in range(1, N+1):

Submission status: Runtime Error

Solution code:

import sys
input = sys.stdin.readline


class unionFind:
    parent = []
    count = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.count = [1 for i in range(N)]

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

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.count[y] += self.count[x]
            self.count[x] = self.count[y]
            return

    def getCount(self, x):
        y = self.root(x)
        self.count[x] = self.count[y]
        return(self.count[x])


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

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

G = unionFind(N)
for a, b in AB:
    G.unite(a, b)

for i in range(N):
    G.root(i)

ans = [G.getCount(i) - 1 for i in range(N)]
# print(ans)
# print(G.count)
for a, b in AB:
    ans[a-1] -= 1
    ans[b-1] -= 1

for c, d in CD:
    if G.same(c, d):
        ans[c-1] -= 1
        ans[d-1] -= 1

print(*ans)

Submission status: Runtime Error

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

import sys
import math
import itertools

def main():
    n, m, k = map(int, sys.stdin.readline().split())
    fs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
    bs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(k)]

    g = [[] for _ in range(n)]
    for u, v in fs:
        g[u - 1].append(v - 1)
        g[v - 1].append(u - 1)

    bg = [[] for _ in range(n)]
    for u, v in bs:
        bg[u - 1].append(v - 1)
        bg[v - 1].append(u - 1)

    ccmembs = []
    ccmap = [-1] * n
    def color_component(ccid, u):
        ccmap[u] = ccid
        nmemb = 1
        for v in g[u]:
            if ccmap[v] < 0:
                nmemb += color_component(ccid, v)
        return nmemb

    for u in range(n):
        if ccmap[u] < 0:
            ccmembs.append(color_component(len(ccmembs), u))

    for u in range(n):
        c = (ccmembs[ccmap[u]]
                - sum(1 for v in g[u] if ccmap[u] == ccmap[v])
                - sum(1 for v in bg[u] if ccmap[u] == ccmap[v])
                - 1)
        print(c, end=(' ' if u != n - 1 else '\n'))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

import sys
input = sys.stdin.readline


class unionFind:
    parent = []
    count = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.count = [1 for i in range(N)]

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

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.count[y] += self.count[x]
            self.count[x] = self.count[y]
            return


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

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

G = unionFind(N)
for a, b in AB:
    G.unite(a, b)

for i in range(N):
    G.root(i)

ans = [G.count[i] - 1 for i in range(N)]

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

for c, d in CD:
    if G.same(c-1, d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1

print(*ans)