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 sys
sys.setrecursionlimit(10**5)
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)]
con = [1 for _ in range(n+1)]
uni = [-1 for i in range(n+1)]

def root(num, pea):
    if pea[num] < 0:
        return num
    else:
        pea[num] = root(pea[num], pea)
        return pea[num]

for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    if uni[a] != uni[b] or uni[a] < 0 or uni[b] < 0:
        root_a = root(a, uni)
        root_b = root(b, uni)
        root_a, root_b = sorted([root_a, root_b])
        uni[root_a] += uni[root_b]
        uni[root_b] = root_a
        root(root_b, uni)

for i in range(k):
    c, d = cd[i]
    if root(c, uni) == root(d, uni):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    root_i = root(i, uni)
    result.append(-uni[root_i]-con[i])
print(*result)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000)
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)]
con = [1 for _ in range(n+1)]
uni = [-1 for i in range(n+1)]

def root(num, pea):
    if pea[num] < 0:
        return num
    else:
        pea[num] = root(pea[num], pea)
        return pea[num]

for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    if uni[a] != uni[b] or uni[a] < 0 or uni[b] < 0:
        root_a = root(a, uni)
        root_b = root(b, uni)
        root_a, root_b = sorted([root_a, root_b])
        uni[root_a] += uni[root_b]
        uni[root_b] = root_a
        root(root_b, uni)

for i in range(k):
    c, d = cd[i]
    if root(c, uni) == root(d, uni):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    root_i = root(i, uni)
    result.append(-uni[root_i]-con[i])
print(*result)

Submission status: Runtime Error

Solution code:
import numpy as np
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)]
con = [1 for _ in range(n+1)]
uni = np.array([-1 for i in range(n+1)])

def root(num, pea):
    if pea[num] < 0:
        return num
    else:
        pea[num] = root(pea[num], pea)
        return pea[num]


for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    if uni[a] != uni[b] or uni[a] < 0 or uni[b] < 0:
        root_a = root(a, uni)
        root_b = root(b, uni)
        root_a, root_b = sorted([root_a, root_b])
        uni[root_a] += uni[root_b]
        uni[root_b] = root_a

for i in range(k):
    c, d = cd[i]
    if root(c, uni) == root(d, uni):
        con[c] += 1
        con[d] += 1

result = []
for i in range(1, n+1):
    root_i = root(i, uni)
    result.append(-uni[root_i]-con[i])
print(*result)

Submission status: Runtime Error

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

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

        if abs(x) < abs(y):
            x, y = y, x
        self.rank[x] += self.rank[y]
        self.rank[y] = x

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

n,m,k=map(int, input().split())
uf=UnionFind(n)
friend = [0]*n
for i in range(m):
    a,b=map(int, input().split())
    friend[a-1] +=1
    friend[b-1] +=1
    uf.union(a-1,b-1)

block = [[] for _ in range(n)]
for i in range(k):
    x,y=map(int, input().split())
    block[x-1].append(y-1)
    block[y-1].append(x-1)

ans = [0]*n
for i in range(n):
    ans[i] = uf.size(i)-1-friend[i]
    for j in block[i]:
        if uf.same(i,j):
            ans[i] -= 1
    ans[i] = str(ans[i])
    
print(" ".join(ans))

Submission status: Runtime Error

Solution code:
# union find (データ構造) 
# union : ある要素とある要素を集合にする：木構造とする O(logn)
# 長さが短い方をくっつける or 経路縮約
# find : ある要素がどの集合に属しているかを返す：根を調べる O(logn)

# ならし計算量：ある時点まで見た時の計算量
# アッカーマン関数の逆数

# 負でサイズ，正で親のIDを持つ
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.tree = [-1]*n

    def find(self, x):
        # ある要素が度の集合に属しているかを返す
        if self.tree[x] < 0:
            # 根だったら根を返す
            return x
        else:
            # そうじゃなかったら親を返す
            return self.find(self.tree[x])

    def union(self, x, y):
        # ある要素をある要素に入れる
        x = self.find( x)
        y = self.find( y)#根同士をくっつけるかたちにする

        if x == y:
            # 処理する必要なし
            return False
        else:
            if self.tree[x] < self.tree[y]:
                # 小さい方にくっつける
                x, y = y, x
            # yをxにくっつける
            self.tree[x] += self.tree[y] # サイズ
            self.tree[y] = x # 根
            return True

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

N, M, K = map(int, input().split())
uf = UnionFind(N)
friend = [0]*N
block = [0]*N

for _ in range(M):
    A, B = map(int, input().split())
    friend[A - 1] += 1
    friend[B - 1] += 1
    uf.union(A - 1, B - 1)

for _ in range(K):
    C, D = map(int, input().split())
    if uf.find(C - 1) == uf.find(D - 1):
        block[C - 1] += 1
        block[D - 1] += 1

[print(max(0, uf.size(i) - friend[i] - block[i] - 1)) for i in range(N)]

Submission status: Runtime Error

Solution code:
# union find (データ構造) 
# union : ある要素とある要素を集合にする：木構造とする O(logn)
# 長さが短い方をくっつける or 経路縮約
# find : ある要素がどの集合に属しているかを返す：根を調べる O(logn)

# ならし計算量：ある時点まで見た時の計算量
# アッカーマン関数の逆数

# 負でサイズ，正で親のIDを持つ
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.tree = [-1]*n

    def find(self, x):
        # ある要素が度の集合に属しているかを返す
        if self.tree[x] < 0:
            # 根だったら根を返す
            return x
        else:
            # そうじゃなかったら親を返す
            return self.find(self.tree[x])

    def union(self, x, y):
        # ある要素をある要素に入れる
        x = self.find( x)
        y = self.find( y)#根同士をくっつけるかたちにする

        if x == y:
            # 処理する必要なし
            return False
        else:
            if self.tree[x] < self.tree[y]:
                # 小さい方にくっつける
                x, y = y, x
            # yをxにくっつける
            self.tree[x] += self.tree[y] # サイズ
            self.tree[y] = x # 根
            return True

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

N, M, K = map(int, input().split())
uf = UnionFind(N)
friend = [0]*N
block = [0]*N

for _ in range(M):
    A, B = map(int, input().split())
    friend[A - 1] += 1
    friend[B - 1] += 1
    uf.union(A - 1, B - 1)

for _ in range(K):
    C, D = map(int, input().split())
    if uf.find(C - 1) == uf.find(D - 1):
        block[C - 1] += 1
        block[D - 1] += 1

[print(uf.size(i) - friend[i] - block[i] - 1) for i in range(N)]

Submission status: Runtime Error

Solution code:
n, m, k=map(int, input().split())
fre = [set() for _ in range(n+1)]
bro = [set() for _ in range(n+1)]
nf = [set() for _ in range(n+1)]
for _ in range(m):
  a, b = map(int, input().split())
  fre[a].add(b)
  fre[b].add(a)
for _ in range(k):
  c, d = map(int, input().split())
  bro[c].add(d)
  bro[d].add(c)

ans = [0]*(n+1)
def sf(x, y):
  for i in fre[x]:
    s = fre[i]-fre[y]-nf[y]
    s.discard(x)
    s.discard(y)
    for j in s:
      if j not in bro[y]:
        ans[y]+=1
        ans[j]+=1
        nf[y].add(j)
        nf[j].add(y)
      sf(j, y)
for l in range(1, n+1):
  sf(l, l)
print(*ans[1:])

Submission status: Runtime Error

Solution code:
import collections
import sys

sys.setrecursionlimit(1000000)
N,M,K = map(int,input().split())
graph = {}
block = {}
for _ in range(M):
    a,b =map(int,input().split())
    if a not in graph:
        graph[a] = set()
    if b not in graph:
        graph[b] = set()
    graph[a].add(b)
    graph[b].add(a)
for _ in range(K):
    a,b =map(int,input().split())
    if a not in block:
        block[a] = set()
    if b not in block:
        block[b] = set()
    block[a].add(b)
    block[b].add(a)


def dfs(i,visit,bl,start):
    visit.add(i)
    if i not in graph:
        return
    for g in graph[i]:
        if g not in visit:
            if start in block and g in block[start]:
                bl.add(g)
            dfs(g,visit,bl,start)
ans = [0]*N
for i in range(N):
    visit =set()
    bl = set()
    dfs(i + 1,visit,bl,i + 1)
    ans[i] = len(visit) - len(bl) - len(graph[i + 1]) -1
for i in range(len(ans) -1):
    print(ans[i], end=" ")
print(ans[-1])

Submission status: Runtime Error

Solution code:
import collections
import sys

sys.setrecursionlimit(1000000)
N,M,K = map(int,input().split())
graph = {}
block = {}
for _ in range(M):
    a,b =map(int,input().split())
    if a not in graph:
        graph[a] = set()
    if b not in graph:
        graph[b] = set()
    graph[a].add(b)
    graph[b].add(a)
for _ in range(K):
    a,b =map(int,input().split())
    if a not in block:
        block[a] = set()
    if b not in block:
        block[b] = set()
    block[a].add(b)
    block[b].add(a)


def dfs(i,visit,bl,start):
    visit.add(i)
    for g in graph[i]:
        if g not in visit:
            if start in block and g in block[start]:
                bl.add(g)
            dfs(g,visit,bl,start)
ans = [0]*N
for i in range(N):
    visit =set()
    bl = set()
    dfs(i + 1,visit,bl,i + 1)
    ans[i] = len(visit) - len(bl) - len(graph[i + 1]) -1
for i in range(len(ans) -1):
    print(ans[i], end=" ")
print(ans[-1])

Submission status: Runtime Error

Solution code:
import collections
import sys

sys.setrecursionlimit(10000)
N,M,K = map(int,input().split())
graph = collections.defaultdict(set)
block =  collections.defaultdict(set)
for _ in range(M):
    a,b =map(int,input().split())
    graph[a].add(b)
    graph[b].add(a)
for _ in range(K):
    a,b =map(int,input().split())
    block[a].add(b)
    block[b].add(a)


def dfs(i,visit,bl,start):
    visit.add(i)
    for g in graph[i]:
        if g not in visit:
            if start in block and g in block[start]:
                bl.add(g)
            dfs(g,visit,bl,start)
ans = [0]*N
for i in range(N):
    visit =set()
    bl = set()
    dfs(i + 1,visit,bl,i + 1)
    ans[i] = len(visit) - len(bl) - len(graph[i + 1]) -1
for i in range(len(ans) -1):
    print(ans[i], end=" ")
print(ans[-1])

Submission status: Runtime Error

Solution code:
import collections
N,M,K = map(int,input().split())
graph = collections.defaultdict(set)
block =  collections.defaultdict(set)
for _ in range(M):
    a,b =map(int,input().split())
    graph[a].add(b)
    graph[b].add(a)
for _ in range(K):
    a,b =map(int,input().split())
    block[a].add(b)
    block[b].add(a)
    
def dfs(i,visit,bl,start):
    visit.add(i)
    for g in graph[i]:
        if g not in visit:
            if start in block and g in block[start]:
                bl.add(g)
            dfs(g,visit,bl,start)
ans = [0]*N
for i in range(N):
    visit =set()
    bl = set()
    dfs(i + 1,visit,bl,i + 1)
    ans[i] = len(visit) - len(bl) - len(graph[i + 1]) -1
for i in range(len(ans) -1):
    print(ans[i], end=" ")
print(ans[-1])

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
graph = [[] for _ in range(N)]
block = [[] for _ in range(N)]
connected_components = []
count = 0
counts = [0 for _ in range(N)]
seen = [False for _ in range(N)]
def dfs(v, c, seen, origin):
    global count
    seen[v] = True
    for node in graph[v]:
        if seen[node] == True:
            continue
        if node not in block[origin]:
            count += 1
        dfs(node, c+1, seen, origin)
def dfs_connected(v, order):
    seen[v] = True
    connected_components[order].append(v)
    for node in graph[v]:
        if seen[node] == True:
            continue
        dfs_connected(node, order)

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

for Ki in range(K):
    a, b = map(int, input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)

for v in range(N):
    if seen[v] == True:
        continue
    connected_components.append([])
    dfs_connected(v, v)

for components in connected_components:
    for component in components:
        seen = [False for _ in range(N)]
        count = 0
        dfs(component, count, seen, component)
        counts[component] = count-len(graph[component])

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

Submission status: Runtime Error

Solution code:
import collections
N,M,K = map(int,input().split())
graph = collections.defaultdict(set)
block =  collections.defaultdict(set)
for _ in range(M):
    a,b =map(int,input().split())
    graph[a].add(b)
    graph[b].add(a)
for _ in range(K):
    a,b =map(int,input().split())
    block[a].add(b)
    block[b].add(a)
    
def dfs(i,visit,bl,start):
    visit.add(i)
    for g in graph[i]:
        if g not in visit:
            if start in block and g in block[start]:
                bl.add(g)
            dfs(g,visit,bl,start)
ans = []
for i in range(N):
    visit =set()
    bl = set()
    dfs(i + 1,visit,bl,i + 1)
    ans.append(str(len(visit) - len(bl) - len(graph[i + 1]) -1))
print(" ".join(ans))

Submission status: Runtime Error

Solution code:
import collections
N,M,K = map(int,input().split())
graph = collections.defaultdict(set)
block =  collections.defaultdict(set)
for _ in range(M):
    a,b =map(int,input().split())
    graph[a].add(b)
    graph[b].add(a)
for _ in range(K):
    a,b =map(int,input().split())
    block[a].add(b)
    block[b].add(a)
ans = []
count = [0]
#print(block[2])
def dfs(i,visit,bl,start):
    visit.add(i)
    for g in graph[i]:
        if g not in visit:
            if g in block[start]:
                bl.add(g)
            dfs(g,visit,bl,start)
ans = []
for i in range(N):
    visit =set()
    bl = set()
    count[0] = 0
    dfs(i + 1,visit,bl,i + 1)
    ans.append(str(len(visit) - len(bl) - len(graph[i + 1]) -1))
print(" ".join(ans))

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
group = [-1]*N
count = []
remove = set()
friend = [0]*N

for _ in range(M):
    A, B = map(int, input().split())
    friend[A - 1] += 1
    friend[B - 1] += 1
    if (group[A - 1] == -1) and (group[B - 1] == -1):
        
        group[A - 1] = len(count)
        group[B - 1] = len(count)

        count.append(2)

    elif (group[A - 1] == -1) and (group[B - 1] != -1):
        group[A -1] = group[B - 1]
        count[group[B - 1]] += 1


    elif (group[A - 1] != -1) and (group[B - 1] == -1):
        group[B -1] = group[A - 1]
        count[group[A - 1]] += 1

    elif group[A - 1] != group[B - 1]:
        g = min(group[A - 1], group[B - 1])
        gg = max(group[A - 1], group[B - 1])
        group = [g if i == gg else i for i in group] #置換
        count[g] += count[gg] 
        remove.add(gg)

block = [0]*N
for _ in range(K):
    C, D = map(int, input().split())
    if group[C - 1] == group[D - 1]:
        block[C - 1] += 1
        block[D - 1] += 1

[print(count[group[n]] - friend[n] - block[n] - 1) for n in range(N)]

Submission status: Runtime Error

Solution code:
class Node():
    def __init__(self, v):
        self.value = v
        self.friends = set()
        self.blocked = set()

n, m, k = list(map(int, input().split()))
link = {i: Node(i) for i in range(1, n+1)}
for _ in range(m):
    a, b = list(map(int, input().split()))
    link[a].friends.add(link[b])
    link[b].friends.add(link[a])

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

def traverse(hist, friends, blocked):
    for f in friends:
        if f not in hist:
            if f not in blocked:
                hist.add(f)
            traverse(hist, f.friends, blocked)
    return hist

for i in range(1, n+1):
    node = link[i]
    hist = traverse(set(), node.friends, node.blocked)
    cnt = len(hist - set([node]) - node.friends - node.blocked)
    print(cnt, end="" if i == n else " ")

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
graph = [[] for _ in range(N)]
block = [[] for _ in range(N)]
count = 0
counts = []
def dfs(v, c, seen, origin):
    global count
    seen[v] = True
    for node in graph[v]:
        if seen[node] == True:
            continue
        if node not in block[origin]:
            count += 1
        dfs(node, c+1, seen, origin)

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

for Ki in range(K):
    a, b = map(int, input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)

for v in range(N):
    seen = [False for _ in range(N)]
    count = 0
    dfs(v, count, seen, v)
    counts.append(count-len(graph[v]))
print(' '.join(map(str, counts)))

Submission status: Runtime Error

Solution code:
from collections import deque
from copy import deepcopy

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+1)
direct_connect = [0]*(N+1)
for _ in range(M):
  a, b = map(int, input().split())
  UF.union(a, b)
  direct_connect[a] += 1
  direct_connect[b] += 1
for _ in range(K):
  a, b = map(int, input().split())
  if UF.same(a, b):
    direct_connect[a] += 1
    direct_connect[b] += 1
print(" ".join([UF.size(i)-direct_connect[i]-1 for _ in range(1, N+1)]))

Submission status: Runtime Error

Solution code:
from collections import deque
from copy import deepcopy

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+1)
direct_connect = [0]*(N+1)
for _ in range(M):
  a, b = map(int, input().split())
  UF.union(a, b)
  direct_connect[a] += 1
  direct_connect[b] += 1
for _ in range(K):
  a, b = map(int, input().split())
  if UF.same(a, b):
    direct_connect[a] += 1
    direct_connect[b] += 1
print(" ".join([UF.size(i)-direct_connect[i]-1 for _ in range(1, N+1)])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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

#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

#xが属する集合の個数
def size(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 = size(i) - frendCnt[i] - 1
    for j in bloc[i]:
      if same(i, j):
           ans -= 1
    print(ans, end=' ')

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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 + 1)]
rank = [0] * (N + 1)
frendCnt = [0] * (N + 1)
bloc = [[] for _ in range(N + 1)]
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:
import sys
input = sys.stdin.readline

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 + 1)]
rank = [0] * N
frendCnt = [0] * N
bloc = [[] for _ in range(N + 1)]
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:
import sys
input = sys.stdin.readline

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:
import sys
input = sys.stdin.readline

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:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import defaultdict

def main():
  n, m, k = map(int, input().strip().split())
  friends = defaultdict(lambda :{'children':list(), 'x':-1, 'visited':False})
  blocks = defaultdict(list)
  visited = set()
  
  for _ in range(m):
    a, b = map(int, input().strip().split())
    friends[a]['children'].append(b)
    friends[b]['children'].append(a)

  for _ in range(k):
    c, d = map(int, input().strip().split())
    blocks[c].append((d))
    blocks[d].append((c))
    
  def dfs(i, x):
    friends[i]['x'] = x
    friends[i]['visited'] = True
    count = 1
    for child in friends[i]['children']:
      if friends[child]['visited']:
        continue
      count += dfs(child, x)
    return count
  
  num = 1
  size = dict()
  for i in range(1, n+1):
    if friends[i]['visited']:
      continue
    count = dfs(i, num)
    size[num] = count
    num += 1
    
  ans = []
  for i in range(1, n+1):
    nblock = 0
    for ib in blocks[i]:
      if friends[i]['x'] == friends[ib]['x']:
        nblock += 1
    ans.append(size[friends[i]['x']] - len(friends[i]['children']) - nblock - 1)
  print(' '.join(list(map(str, ans))))
  
if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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:
N, M, K = list(map(int, input().split()))
users_all = [[] for i in range(N)]

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

blocks_all = [[] for i in range(N)]
for i in range(K):
    C, D = list(map(int, input().split()))
    blocks_all[C-1].append(D-1)
    blocks_all[D-1].append(C-1)
blocks_all = [set(lst) for lst in blocks_all]

def dfs(i, friends, blocks, candidates, consumed={}):
    for user in users_all[i]:
        if user in consumed:
            continue
        consumed[user] = True
        if user not in friends:
            if user not in blocks:
                candidates.append(user)
        dfs(user, friends, blocks, candidates, consumed)

candidates_all = [[] for i in range(N)]
for i,friends in enumerate(users_all):
    dfs(i, friends+[i], blocks_all[i], candidates_all[i], {i:True})

print(' '.join([str(len(candidates)) for candidates in candidates_all]))