Problem: 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?

Submission attempts (in order):
n,m,k=map(int,input().split())
A=[]
B=[]
for i in range(m):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
C=[]
D=[]
for i in range(k):
    c,d=map(int,input().split())
    C.append(c)
    D.append(d)
union=[]
for i in range(n):
    br=0
    for j in range(len(union)):
        if i+1 in set(union[j]):
            br=1
            break
    if br==1:
        continue
    fri=[i+1]
    mark=[0]
    while 0 in set(mark):
        for s in range(len(fri)):
            if mark[s]==0:
                for t in range(m):
                    if A[t]==fri[s] and B[t] not in set(fri):
                        fri.append(B[t])
                        mark.append(0)
                    if B[t]==fri[s] and A[t] not in set(fri):
                        fri.append(A[t])
                        mark.append(0)
                mark[s]=1
    union.append(fri)
counter=[]
for i in range(n):
    counter.append(0)

for i in range(m):
    counter[A[i]-1]+=1
    counter[B[i]-1]+=1
for i in range(k):
    for j in range(len(union)):
        if C[i] in union[j] and D[i] in union[j]:
            counter[C[i]-1]+=1
            counter[D[i]-1]+=1
            break

for i in range(n):
    for j in range(len(union)):
        if i+1 in union[j]:
            print(len(union[j])-counter[i]-1,end=" ")
            break

import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].append(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

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

fri=[[] for i in range(n)]
blk=[[] for i in range(n)]

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

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


seen=[0 for i in range(n)]

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append([])
        dfs(i)
        cnt+=1

seq=[0 for i in range(n)]

print(*seq)


n,m,k=map(int,input().split())
A=[]
B=[]
for i in range(m):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
C=[]
D=[]
for i in range(k):
    c,d=map(int,input().split())
    C.append(c)
    D.append(d)
union=[]
for i in range(n):
    br=0
    for j in range(len(union)):
        if i+1 in set(union[j]):
            br=1
            break
    if br==1:
        continue
    fri=[i+1]
    mark=[0]
    while 0 in set(mark):
        for s in range(len(fri)):
            if mark[s]==0:
                for t in range(m):
                    if A[t]==fri[s] and B[t] not in set(fri):
                        fri.append(B[t])
                        mark.append(0)
                    if B[t]==fri[s] and A[t] not in set(fri):
                        fri.append(A[t])
                        mark.append(0)
                mark[s]=1
    union.append(fri)
unionsize=[]
for i in range(len(union)):
    unionsize.append(len(union[i]))
counter=[]
for i in range(n):
    counter.append(0)

for i in range(m):
    counter[A[i]-1]+=1
    counter[B[i]-1]+=1
for i in range(k):
    for j in range(len(union)):
        if C[i] in union[j] and D[i] in union[j]:
            counter[C[i]-1]+=1
            counter[D[i]-1]+=1
            break

for i in range(n):
    for j in range(len(union)):
        if i+1 in union[j]:
            print(unionsize[j]-counter[i]-1,end=" ")
            break

import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].add(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

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

fri=[[] for i in range(n)]
blk=[set() for i in range(n)]

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

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


seen=[0 for i in range(n)]

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append(set())
        dfs(i)
        cnt+=1

seq=[0 for i in range(n)]

print(*seq)

import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].append(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

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

fri=[[] for i in range(n)]
blk=[[] for i in range(n)]

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

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


seen=[0 for i in range(n)]

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append([])
        dfs(i)
        cnt+=1

seq=[0 for i in range(n)]

for unii in uni:
    for j in unii:
        cj=len(unii)-len(fri[j-1])-len(set(unii)&set(blk[j-1])-1
        seq[j-1]=cj

print(*seq)

n,m,k=map(int,input().split())
A=[]
B=[]
for i in range(m):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
C=[]
D=[]
for i in range(k):
    c,d=map(int,input().split())
    C.append(c)
    D.append(d)
seq=[]
for i in range(n):
    fri=[i+1]
    mark=[0]
    while 0 in set(mark):
        for s in range(len(fri)):
            if mark[s]==0:
                for t in range(m):
                    if A[t]==fri[s] and B[t] not in set(fri):
                        fri.append(B[t])
                        mark.append(0)
                    if B[t]==fri[s] and A[t] not in set(fri):
                        fri.append(A[t])
                        mark.append(0)
                mark[s]=1
    fri.remove(i+1)
    for t in range(m):
        if A[t]==i+1:
            fri.remove(B[t])
        if B[t]==i+1:
            fri.remove(A[t])
    for s in range(k):
        if C[s]==i+1 and D[s] in set(fri):
            fri.remove(D[s])
    for s in range(k):
        if D[s]==i+1 and C[s] in set(fri):
            fri.remove(C[s])
    seq.append(len(fri))
for i in range(n):
    print(seq[i],end=" ")

import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].add(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

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

fri=[[] for i in range(n)]
blk=[set() for i in range(n)]

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

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


seen=[0 for i in range(n)]

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append(set())
        dfs(i)
        cnt+=1

seq=[0 for i in range(n)]

for unii in uni:
    for j in unii:
        cj=len(unii)-len(fri[j-1])-len(unii&blk[j-1])-1
        seq[j-1]=cj

print(*seq)

Verdicts: Time Limit Exceeded

Wrong Answer

Time Limit Exceeded

Wrong Answer

Runtime Error

Time Limit Exceeded

Accepted