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
import os
f = open('input.txt', 'r')
sys.stdin = f

n, m, k = map(int, input().split())
a = [0]*m
c = [0]*k

union = []
sizeU = [1]*(n+1)
for i in range(n+1):
    union.append(i)

def root(n):
    global union
    if union[n] == n:
        return n
    res = union[union[n]]
    union[n] = res
    return res

def isSameRoots(n, m):
    nRoot = root(n)
    mRoot = root(m)
    return nRoot == mRoot

def unit(n, m):
    global union
    global sizeU
    nRoot = root(n)
    mRoot = root(m)
    sizeU[nRoot] += size(mRoot)
    union[mRoot] = root(nRoot)

def size(n):
    return sizeU[root(n)]

for i in range(m):
    inA, inB = map(int, input().split())
    if not isSameRoots(inA, inB):
        unit(inA, inB)

for i in range(1, n+1):
    print(size(i))

Submission status: Runtime Error

Solution code:
def main():
    class unionfind():
        def __init__(self,n):
            self.par = [i for i in range(n)]
            self.size = [1 for i in range(n)]
            self.rank = [0 for i in range(n)]
 
        def root(self,x):
            if self.par[x] == x:
                return x
            else:
                self.par[x] = self.root(self.par[x])
                return self.par[x]
 
        def same(self,x,y):
            return self.root(x) == self.root(y)
 
        def unite(self,x,y):
            x = self.root(x)
            y = self.root(y)
            if x==y:return
            else:
                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
                self.size[x] +=self.size[y]
        def get_size(self,x):
            x = self.root(x)
            return self.size[x]
 
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    n,m,k = map(int,input().split())
    uff = unionfind(n)
    fr = [0 for i in range(n)]
 
 
    for i in range(m):
        a,b = map(int,input().split())
        uff.unite(a-1,b-1)
        fr[a-1]+=1
        fr[b-1]+=1
 
 
    ans = []#[uff.get_size(i) -fr[i]-1 for i in range(n)]
 
    for i in range(k):
        c,d = map(int,input().split())
        if uff.same(c-1,d-1):
            ans[c-1] -=1
            ans[d-1] -=1
    print(*ans)
if __name__=="__main__":
    main()

Submission status: Runtime Error

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


par=[index for index in range(N+1)]

def root(x):
    global par

    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]


def same(x,y):
    global par

    if root(x)==root(y):
        return True
    else:
        return False

def unite(x,y):
    global par

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


friends=[[] for index1 in range(N+1)]
for index2 in range(M):
    a,b=map(int,input().split())
    unite(a,b)
    friends[a].append(b)
    friends[b].append(a)


block=[[] for index3 in range(N+1)]
for index4 in range(K):
    c,d=map(int,input().split())
    block[c].append(d)
    block[d].append(c)


relates=[0]*(N+1)
for i in range(1,N+1):
    relates[root(i)]+=1


Ans=[]
for j in range(1,N+1):
    ans=relates[root(j)]-1    #高速化可能   #1
    for k in friends[j]:
        if same(j,k):
            ans-=1
    for l in block[j]:
        if same(j,l):   #まとめられる
            ans-=1

    Ans.append(ans)

print(*Ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n, f, b = map(int, input().split())
F = [list(map(int, input().split())) for i in range(f)]
B = [list(map(int, input().split())) for i in range(b)]

R=np.zeros((n,n), dtype=int)
for i in range(n):
    R[i][i]=1

f_sets=[]

for friend in F:
    R[friend[0]-1][friend[1]-1]=2
    R[friend[1]-1][friend[0]-1]=2

    set0 = -1
    set1 = -1

    for i, f_set in enumerate(f_sets):
        if friend[0] in f_set:
            set0 = i
        if friend[1] in f_set:
            set1 = i

    if set0==-1 and set1==-1:
        f_sets.append(set(friend))

    if set0==-1 and set1!=-1:
        f_sets[set1].add(friend[0])

    if set0!=-1 and set1==-1:
        f_sets[set0].add(friend[1])

    if set0!=-1 and set1!=-1 and set0!=set1:
        f_sets[set0]=f_sets[set0]|f_sets[set1]
        f_sets.pop(set1)

for block in B:
    R[block[0]-1][block[1]-1]=3
    R[block[1]-1][block[0]-1]=3

ans=[]
for i in range(n):
    count=0
    for j in range(n):
        if R[i][j]==0:
            for f_set in f_sets:
                if (i+1 in f_set) and (j+1 in f_set):
                    count += 1
                    break

    ans.append(count)

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

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)


    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    n_to = [0 for _ in range(N + 1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        #a,b = AB[i]
        to[a].append(b)
        n_to[a] += 1
        to[b].append(a)
        n_to[b] += 1

    stack = defaultdict(lambda:0)
    visited = [False] * (N+1)
    belong = [None] * (N+1)


    def dfs(n):
        _stack = [n]
        visited[n] = True
        while _stack:
            node = _stack.pop()
            stack[n] += 1
            belong[node] = n
            for next in to[node]:
                if not visited[next]:
                    _stack.append(next)
                    visited[next] = True
        return None


    for i in range(1,N+1):
        if not visited[i]:
            dfs(i)

    block = [0 for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        #c, d = CD[i]
        if belong[c] == belong[d]:
            block[c] += 1
            block[d] += 1

    candidates = [0] * (N+1)

    for k in range(1,N+1):
        tr = belong[k]
        candidates[k] = stack[tr] - 1 - n_to[k] - block[k]

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return graph_g[s]

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        dfs(edge, graph_cnt)


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

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

for i in range(N):
    if is_visted[i]:
        continue
    dfs(i, None)

group_to_idx = [set() for i in range(graph_cnt+1)]
if len(group_to_idx) != 0:
    for i in range(N):
        group_to_idx[graph_g[i]].add(i)

ret = []
for i in range(N):
    cand = len(group_to_idx[graph_g[i]])
    fri = len(to[i])
    tmp_block = len(group_to_idx[graph_g[i]] & set(block[i]))

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)

Submission status: Runtime Error

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

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return graph_g[s]

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        dfs(edge, graph_cnt)


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

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

for i in range(N):
    dfs(i, None)

group_to_idx = [set() for i in range(graph_cnt+1)]
if len(group_to_idx) != 0:
    for i in range(N):
        group_to_idx[graph_g[i]].add(i)

ret = []
for i in range(N):
    cand = len(group_to_idx[graph_g[i]])
    fri = len(to[i])
    tmp_block = len(group_to_idx[graph_g[i]] & set(block[i]))

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)

Submission status: Runtime Error

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

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return graph_g[s]

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        dfs(edge, graph_cnt)


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

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

for i in range(N):
    dfs(i, None)

group_to_idx = [set() for i in range(graph_cnt+1)]
for i in range(N):
    group_to_idx[graph_g[i]].add(i)

ret = []
for i in range(N):
    cand = len(group_to_idx[graph_g[i]])
    fri = len(to[i])
    tmp_block = len(group_to_idx[graph_g[i]] & set(block[i]))

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)

Submission status: Runtime Error

Solution code:
import numpy as np

n, f, b = map(int, input().split())
F = [list(map(int, input().split())) for i in range(f)]
B = [list(map(int, input().split())) for i in range(b)]

R=np.zeros((n,n), dtype=int)
for i in range(n):
    R[i][i]=1

f_sets=[]

for friend in F:
    R[friend[0]-1][friend[1]-1]=2
    R[friend[1]-1][friend[0]-1]=2

    set0 = -1
    set1 = -1

    for i, f_set in enumerate(f_sets):
        if friend[0] in f_set:
            set0 = i
        if friend[1] in f_set:
            set1 = i

    if set0==-1 and set1==-1:
        f_sets.append(set(friend))

    if set0==-1 and set1!=-1:
        f_sets[set1].add(friend[0])

    if set0!=-1 and set1==-1:
        f_sets[set0].add(friend[1])

    if set0!=-1 and set1!=-1 and set0!=set1:
        f_sets[set0]=f_sets[set0]|f_sets[set1]
        #f_sets.pop(set1)

for block in B:
    R[block[0]-1][block[1]-1]=3
    R[block[1]-1][block[0]-1]=3

ans=[]
for i in range(n):
    count=0
    for j in range(n):
        if R[i][j]==0:
            for f_set in f_sets:
                if (i+1 in f_set) and (j+1 in f_set):
                    count += 1
                    break

    ans.append(count)

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

Submission status: Runtime Error

Solution code:
import numpy as np
import sys #追加
sys.setrecursionlimit(5000*5000) #追加

n, f, b = map(int, input().split())
F = [list(map(int, input().split())) for i in range(f)]
B = [list(map(int, input().split())) for i in range(b)]

R=np.zeros((n,n), dtype=int)
for i in range(n):
    R[i][i]=1

f_sets=[]

for friend in F:
    R[friend[0]-1][friend[1]-1]=2
    R[friend[1]-1][friend[0]-1]=2

    set0 = -1
    set1 = -1

    for i, f_set in enumerate(f_sets):
        if friend[0] in f_set:
            set0 = i
        if friend[1] in f_set:
            set1 = i

    if set0==-1 and set1==-1:
        f_sets.append(set(friend))

    if set0==-1 and set1!=-1:
        f_sets[set1].add(friend[0])

    if set0!=-1 and set1==-1:
        f_sets[set0].add(friend[1])

    if set0!=-1 and set1!=-1 and set0!=set1:
        f_sets[set0]=f_sets[set0]|f_sets[set1]
        f_sets.pop(set1)

for block in B:
    R[block[0]-1][block[1]-1]=3
    R[block[1]-1][block[0]-1]=3

ans=[]
for i in range(n):
    count=0
    for j in range(n):
        if R[i][j]==0:
            for f_set in f_sets:
                if (i+1 in f_set) and (j+1 in f_set):
                    count += 1
                    break

    ans.append(count)

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

Submission status: Runtime Error

Solution code:
import numpy as np
import sys #追加
sys.setrecursionlimit(5000*5000) #追加

n, f, b = map(int, input().split())
F = [list(map(int, input().split())) for i in range(f)]
B = [list(map(int, input().split())) for i in range(b)]

R=np.zeros((n,n), dtype=int)
for i in range(n):
    R[i][i]=1

f_sets=[]

for friend in F:
    R[friend[0]-1][friend[1]-1]=2
    R[friend[1]-1][friend[0]-1]=2

    set0 = -1
    set1 = -1

    for i, f_set in enumerate(f_sets):
        if friend[0] in f_set:
            set0 = i
        if friend[1] in f_set:
            set1 = i

    if set0==-1 and set1==-1:
        f_sets.append(set(friend))

    if set0==-1 and set1!=-1:
        f_sets[set1].add(friend[0])

    if set0!=-1 and set1==-1:
        f_sets[set0].add(friend[1])

    if set0!=-1 and set1!=-1 and set0!=set1:
        f_sets[set0]=f_sets[set0]|f_sets[set1]
        f_sets.pop(set1)

for block in B:
    R[block[0]-1][block[1]-1]=3
    R[block[1]-1][block[0]-1]=3

for i in range(n):
    count=0
    for j in range(n):
        if R[i][j]==0:
            for f_set in f_sets:
                if (i+1 in f_set) and (j+1 in f_set):
                    count += 1
                    break

    if i==0:
        ans=str(count)
    else:
        ans=ans+' '+str(count)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

sys.setrecursionlimit(10**8)

n, f, k = map(int, input().split())
F = [list(map(int, input().split())) for i in range(f)]
B = [list(map(int, input().split())) for i in range(k)]

R=np.zeros((n,n), dtype=int)
for i in range(n):
    R[i][i]=1

f_sets=[]

for friend in F:
    R[friend[0]-1][friend[1]-1]=2
    R[friend[1]-1][friend[0]-1]=2

    set0 = -1
    set1 = -1

    for i, f_set in enumerate(f_sets):
        if friend[0] in f_set:
            set0 = i
        if friend[1] in f_set:
            set1 = i

    if set0==-1 and set1==-1:
        f_sets.append(set(friend))

    if set0==-1 and set1!=-1:
        f_sets[set1].add(friend[0])

    if set0!=-1 and set1==-1:
        f_sets[set0].add(friend[1])

    if set0!=-1 and set1!=-1 and set0!=set1:
        f_sets[set0]=f_sets[set0]|f_sets[set1]
        f_sets.pop(set1)

for block in B:
    R[block[0]-1][block[1]-1]=3
    R[block[1]-1][block[0]-1]=3

for i in range(n):
    count=0
    for j in range(n):
        if R[i][j]==0:
            for f_set in f_sets:
                if (i+1 in f_set) and (j+1 in f_set):
                    count += 1
                    break

    if i==0:
        ans=str(count)
    else:
        ans=ans+' '+str(count)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n, f, k = map(int, input().split())
F = [list(map(int, input().split())) for i in range(f)]
B = [list(map(int, input().split())) for i in range(k)]

R=np.zeros((n,n), dtype=int)
for i in range(n):
    R[i][i]=1

f_sets=[]

for friend in F:
    R[friend[0]-1][friend[1]-1]=2
    R[friend[1]-1][friend[0]-1]=2

    set0 = -1
    set1 = -1

    for i, f_set in enumerate(f_sets):
        if friend[0] in f_set:
            set0 = i
        if friend[1] in f_set:
            set1 = i

    if set0==-1 and set1==-1:
        f_sets.append(set(friend))

    if set0==-1 and set1!=-1:
        f_sets[set1].add(friend[0])

    if set0!=-1 and set1==-1:
        f_sets[set0].add(friend[1])

    if set0!=-1 and set1!=-1 and set0!=set1:
        f_sets[set0]=f_sets[set0]|f_sets[set1]
        f_sets.pop(set1)

for block in B:
    R[block[0]-1][block[1]-1]=3
    R[block[1]-1][block[0]-1]=3

for i in range(n):
    count=0
    for j in range(n):
        if R[i][j]==0:
            for f_set in f_sets:
                if (i+1 in f_set) and (j+1 in f_set):
                    count += 1
                    break

    if i==0:
        ans=str(count)
    else:
        ans=ans+' '+str(count)

print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from collections import defaultdict

def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        to[a].append(b)
        to[b].append(a)
    block = [[] for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        block[c].append(d)
        block[d].append(c)

    stack = defaultdict(lambda:[])
    visited = [False] * (N+1)

    def dfs(n, tree= None):
        visited[n] = True
        if tree==None:
            tree = n
        stack[tree].append(n)
        for next in to[n]:
            if not visited[next]:
                dfs(next, tree)
        return None

    while True:
        k = -1
        for i in range(1,N+1):
            if not visited[i]:
                k = i
                break
        if k == -1:break
        dfs(k)

    candidates = [0] * (N+1)

    for tree in stack.keys():
        for k in stack[tree]:
            check_list = to[k] + block[k] + [k]
            for k_ in stack[tree]:
                if not k_ in check_list:
                    candidates[k] += 1

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

Submission status: Runtime Error

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

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

for i in range(M):
    A, B = map(int, input().split())
    to[A-1].append(B-1)
    to[B-1].append(A-1)
    flg = False
    A_idx = None
    B_idx = None
    for tmp_idx, tmp_set in enumerate(sets):
        if A - 1 in tmp_set:
            A_idx = tmp_idx
        if B - 1 in tmp_set:
            B_idx = tmp_idx
        if A - 1 in tmp_set or B - 1 in tmp_set:
            flg = True
            tmp_set.add(A - 1)
            tmp_set.add(B - 1)

    if not flg:
        sets.append({A-1, B-1})
    elif A_idx != None and B_idx != None and A_idx != B_idx:
        for j in sets[B_idx]:
            sets[A_idx].add(j)
        sets.pop(B_idx)

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

for i in range(N):
    i_idx = -1
    for tmp_idx, tmp_set in enumerate(sets):
        if i in tmp_set:
            i_idx = tmp_idx
    l = len(sets[i_idx])
    m1 = len(to[i])
    
    m2 = 0
    for j in block[i]:
        if j in sets[i_idx]:
            m2 += 1

    if i != N-1:
        print(l - 1 - m1 - m2, end=' ')
    else:
        print(l - 1 - m1 - m2)

Submission status: Runtime Error

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

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

for i in range(M):
    A, B = map(int, input().split())
    to[A-1].append(B-1)
    to[B-1].append(A-1)
    flg = False
    A_idx = None
    B_idx = None
    for tmp_idx, tmp_set in enumerate(sets):
        if A - 1 in tmp_set:
            A_idx = tmp_idx
        if B - 1 in tmp_set:
            B_idx = tmp_idx
        if A - 1 in tmp_set or B - 1 in tmp_set:
            flg = True
            tmp_set.add(A - 1)
            tmp_set.add(B - 1)

    if not flg:
        sets.append({A-1, B-1})
    elif A_idx != None and B_idx != None and A_idx != B_idx:
        for j in sets[B_idx]:
            sets[A_idx].add(j)
        sets.pop(B_idx)

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

print(sets)

for i in range(N):
    i_idx = -1
    for tmp_idx, tmp_set in enumerate(sets):
        if i in tmp_set:
            i_idx = tmp_idx
    l = len(sets[i_idx])
    m1 = len(to[i])
    
    m2 = 0
    for j in block[i]:
        if j in sets[i_idx]:
            m2 += 1

    if i != N-1:
        print(l - 1 - m1 - m2, end=' ')
    else:
        print(l - 1 - m1 - m2)

Submission status: Runtime Error

Solution code:
class graph:
    def __init__(self, n):
        self.node = [[] for _ in range(n)]
        self.belongs = [-1] * n
        self.unexplored = [True] * n
        self.linked = []

    def unit(self, a, b):
        self.node[a].append(b)
        self.node[b].append(a)
    
    def get_graph(self):
        return self.node

    def dfs(self, start, idx):
        self.unexplored[start] = False
        self.belongs[start] = idx
        self.linked[idx].append(start)
        for d in self.node[start]:
            if self.unexplored[d]:
                self.dfs(d, idx)
    
    def link_split(self):
        num = 0
        for i in range(len(self.node)):
            if self.unexplored[i]:
                self.linked.append([])
                self.dfs(i, num)
                num += 1

    def get_link(self):
        return self.linked
    
    def get_belogns(self):
        return self.belongs
    
    def get_neighbor(self):
        return [len(d) for d in self.node]

n,m,k = map(int, input().split())
g = graph(n)
i = 0
while i < m:
    a, b = map(int, input().split())
    g.unit(a-1, b-1)
    i += 1

g.link_split()
links = g.get_link()
belongs = g.get_belogns()
neighbors = g.get_neighbor()
link_size = [len(d) for d in links]
dec_num = [-1] * n
i = 0
while i < k:
    a, b = map(int, input().split())
    if belongs[a-1] == belongs[b-1]:
        dec_num[a-1] -= 1
        dec_num[b-1] -= 1
    i += 1

print(' '.join(str(link_size[belongs[i]]+dec_num[i]-neighbors[i]) for i in range(n)))

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

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

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    friend = [i]
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = friends_table[i][:]]
    while next_stack:
        next = next_stack.pop()
        # 訪問済み
        if i == group_list[next]:
            continue
        friend += [next]
        group_list[next] = i
        next_stack += friends_table[next]
    for f in friend:
        friends_candidate[f] = friend

for i in range(N):
    print(len(set(friends_candidate[i]).difference(set(friends_table[i] + blocks_table[i])))-1)

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

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

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    friend = [i]
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = friends_table[i].copy()
    while next_stack:
        next = next_stack.pop()
        # 訪問済み
        if i == group_list[next]:
            continue
        friend += [next]
        group_list[next] = i
        next_stack += friends_table[next]
    for f in friend:
        friends_candidate[f] = friend
        
for i in range(N):
    print(len(set(friends_candidate[i]).difference(set(friends_table[i] + blocks_table[i])))-1)

Submission status: Runtime Error

Solution code:
def find (x) : 
    fa[x] = x if fa[x] == x else find (fa[x])
    return fa[x]

def union (x, y) :
    fa[find (x)] = find (y)
    
N, M, K = list (map (int, input().split()))

fa = [x for x in range (N + 1)]
ans = [-1 for i in range (N + 1)]
siz = [0 for i in range (N + 1)]

for i in range (M) :
    a, b = list (map (int, input().split()))
    union (a, b)
    ans[a] -= 1
    ans[b] -= 1
    
for i in range (1, N + 1) :
    siz[find(i)] += 1

for i in range (1, N + 1) :
    ans[i] += siz[find (i)]

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

print (' '.join (list (map(str , ans[1 : N + 1]))))

Submission status: Runtime Error

Solution code:
fa = [x for x in range (100002)]
ans = [-1 for i in range (100002)]
siz = [0 for i in range (100002)]

def find (x) : 
    fa[x] = x if fa[x] == x else find (fa[x])
    return fa[x]

def union (x, y) :
    fa[find (x)] = find (y)
    
N, M, K = list (map (int, input().split()))

for i in range (M) :
    a, b = list (map (int, input().split()))
    union (a, b)
    ans[a] -= 1
    ans[b] -= 1
    
for i in range (1, N + 1) :
    siz[find(i)] += 1

for i in range (1, N + 1) :
    ans[i] += siz[find (i)]

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

print (' '.join (list (map(str , ans[1 : N + 1]))))

Submission status: Runtime Error

Solution code:
fa = [x for x in range (100002)]
ans = [-1 for i in range (100002)]
siz = [0 for i in range (100002)]
rank = [0 for i in range (100002)]


def find (x) : # find the highest ancestor of x
    fa[x] = x if fa[x] == x else find (fa[x])
    return fa[x]

def union (x, y) :
    fa[find (x)] = find (y)
    

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

for i in range (M) :
    a, b = list (map (int, input().split()))
    union (a, b)
    ans[a] -= 1
    ans[b] -= 1
    
# TODO : .... build ans[]
for i in range (1, N + 1) :
    siz[find(i)] += 1

for i in range (1, N + 1) :
    ans[i] += siz[find (i)]

# TODO : eliminate blockships
for i in range (K) :
    c, d = list (map (int, input().split()))
    if (find (c) == find (d)) :
        ans[c] -= 1
        ans[d] -= 1

print (' '.join (list (map(str , ans[1 : N + 1]))))

Submission status: Runtime Error

Solution code:
class graph:
    def __init__(self, n):
        self.node = [[] for _ in range(n)]
        self.belongs = [-1] * n
        self.unexplored = [True] * n
        self.linked = []

    def unit(self, a, b):
        self.node[a].append(b)
        self.node[b].append(a)
    
    def get_graph(self):
        return self.node

    def dfs(self, start, idx):
        self.unexplored[start] = False
        self.belongs[start] = idx
        self.linked[idx].append(start)
        for d in self.node[start]:
            if self.unexplored[d]:
                self.dfs(d, idx)
    
    def link_split(self):
        num = 0
        for i in range(len(self.node)):
            if self.unexplored[i]:
                self.linked.append([])
                self.dfs(i, num)
                num += 1

    def get_link(self):
        return self.linked
    
    def get_belogns(self):
        return self.belongs
    
    def get_neighbor(self):
        return [len(d) for d in self.node]

n,m,k = map(int, input().split())
g = graph(n)
for i in range(m):
    a, b = map(int, input().split())
    g.unit(a-1, b-1)

g.link_split()
links = g.get_link()
belongs = g.get_belogns()
neighbors = g.get_neighbor()
link_size = [len(d) for d in links]
dec_num = [-1] * n
for i in range(k):
    a, b = map(int, input().split())
    if belongs[a-1] == belongs[b-1]:
        dec_num[a-1] -= 1
        dec_num[b-1] -= 1

print(' '.join(str(link_size[belongs[i]]+dec_num[i]-neighbors[i]) for i in range(n)))

Submission status: Runtime Error

Solution code:
class graph:
    def __init__(self, n):
        self.node = [[] for _ in range(n)]
        self.belongs = [-1] * n
        self.unexplored = [True] * n
        self.linked = []

    def unit(self, a, b):
        self.node[a].append(b)
        self.node[b].append(a)
    
    def get_graph(self):
        return self.node

    def dfs(self, start, k):
        self.unexplored[start] = False
        self.belongs[start] = k
        self.linked[k].append(start)
        for d in self.node[start]:
            if self.unexplored[d]:
                self.dfs(d, k)
    
    def link_split(self):
        num = 0
        for i in range(len(self.node)):
            if self.unexplored[i]:
                self.linked.append([])
                self.dfs(i, num)
                num += 1

    def get_link(self):
        return self.linked
    
    def get_belogns(self):
        return self.belongs
    
    def get_neighbor(self):
        return [len(d) for d in self.node]

n,m,k = map(int, input().split())
g = graph(n)
for i in range(m):
    a, b = map(int, input().split())
    g.unit(a-1, b-1)

g.link_split()
links = g.get_link()
belongs = g.get_belogns()
neighbors = g.get_neighbor()
link_size = [len(d) for d in links]
dec_num = [-1] * n
for i in range(k):
    a, b = map(int, input().split())
    if belongs[a-1] == belongs[b-1]:
        dec_num[a-1] -= 1
        dec_num[b-1] -= 1

print(' '.join(str(link_size[belongs[i]]+dec_num[i]-neighbors[i]) for i in range(n)))

Submission status: Runtime Error

Solution code:
import queue
q = queue.LifoQueue()

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)

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

seen = [False]*n
group = [-1]*n
G = []

def dfs(v):
    global start
    seen[v] = True
    group[v] = start
    graph.append(v)
    
    for i in friend[v]:
        if seen[i]:
            continue
        dfs(i)

start = 0
for i in range(n):
    if seen[i] == False:
        graph = []
        dfs(i)
        start += 1
        G.append(graph)

group_sum = []
for j in set(group):
    group_sum.append(group.count(j))

print(G)
print(group)
print(group_sum)

c_list = []
for k in range(n):
    c = group_sum[group[k]] - len(set(G[group[k]]) & set(friend[k] + block[k])) - 1
    c_list.append(c)

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