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 = list(map(int,input().split()))





G = [[] for _ in range(N)]
# print(G)

for _ in range(M):
    a,b = list(map(int,input().split()))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
# print(G)

KG = [[] for _ in range(N)]

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


def dfs(G,v):
    global l
    
    seen[v] = 1
    l += 1
    # print(v+1)
    seenV.append(v)
    
    for next_v in G[v]:
        if seen[next_v] == 1:
            continue
        else:
            dfs(G,next_v)

Adj_size = [0]*N

Adj = [0]*N
seen = [0]*N
Y = []
for v in range(N):
    l = 0
    seenV = []
    if seen[v] == 0:
        dfs(G,v)
        
    
    # print("l=",l)
    
    for v in seenV:
        Adj_size[v] = l
        Adj[v] = seenV
    # print(Adj_size)
    
    
    y = Adj_size[v] - len(G[v])-1
    for k in KG[v]:
        if k in Adj[v]:
            y += -1
    # print("v=",v+1,"y=",y)
    Y.append(str(y))

print(" ".join(Y))



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





G = [[] for _ in range(N)]

for _ in range(M):
    a,b = list(map(int,input().split()))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
# print("G:",G)

KG = [[] for _ in range(N)]

for _ in range(K):
    a,b = list(map(int,input().split()))
    KG[a-1].append(b-1)
    KG[b-1].append(a-1)
# print("KG:",KG)





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





G = [[] for _ in range(N)]

for _ in range(M):
    a,b = list(map(int,input().split()))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
# print("G:",G)

KG = [[] for _ in range(N)]

for _ in range(K):
    a,b = list(map(int,input().split()))
    KG[a-1].append(b-1)
    KG[b-1].append(a-1)
# print("KG:",KG)



def dfs(G,v):
    # global l
    
    seen[v] = 1
    # l += 1
    # print(v+1)
    seenV.append(v)
    
    for next_v in G[v]:
        if seen[next_v] == 1:
            continue
        else:
            dfs(G,next_v)

# Adj_size = [0]*N

Adj = [[] for _ in range(N)]
seen = [0]*N
Y = []
for v in range(N):
    # l = 0
    if seen[v] == 0:
        
        seenV = []
        dfs(G,v)
    




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





G = [[] for _ in range(N)]

for _ in range(M):
    a,b = list(map(int,input().split()))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
print("G:",G)

KG = [[] for _ in range(N)]

for _ in range(K):
    a,b = list(map(int,input().split()))
    KG[a-1].append(b-1)
    KG[b-1].append(a-1)
print("KG:",KG)

def dfs(G,v):
    global l
    
    seen[v] = 1
    l += 1
    # print(v+1)
    seenV.append(v)
    
    for next_v in G[v]:
        if seen[next_v] == 1:
            continue
        else:
            dfs(G,next_v)

Adj_size = [0]*N

Adj = [0]*N
seen = [0]*N
Y = []
for v in range(N):
    l = 0
    seenV = []
    if seen[v] == 0:
        dfs(G,v)
        print("dfs done !!!")
    print("v=",v+1,"seen:",seen)
    print("l=",l)
    print(seenV)
    for sv in seenV:
        Adj_size[sv] = l
        Adj[sv] = seenV
    # print("Adj_size:",Adj_size)
    
    
    y = Adj_size[v] - len(G[v])-1
    for k in KG[v]:
        if k in Adj[v]:
            y += -1
    print("v=",v+1,"y=",y)
    Y.append(str(y))

print("ADj",Adj)
print("Y",Y)
print("G",G)

print(" ".join(Y))



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





G = [[] for _ in range(N)]

for _ in range(M):
    a,b = list(map(int,input().split()))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
# print("G:",G)

KG = [[] for _ in range(N)]

for _ in range(K):
    a,b = list(map(int,input().split()))
    KG[a-1].append(b-1)
    KG[b-1].append(a-1)
# print("KG:",KG)



def dfs(G,v):
    # global l
    
    seen[v] = 1
    # l += 1
    # print(v+1)
    seenV.append(v)
    
    for next_v in G[v]:
        if seen[next_v] == 1:
            continue
        else:
            dfs(G,next_v)

# Adj_size = [0]*N

Adj = [[] for _ in range(N)]
seen = [0]*N
Y = []
for v in range(N):
    # l = 0
    seenV = []
    if seen[v] == 0:
        # dfs(G,v)
        pass
    
        
    
    # print("l=",l)
    
    
    for sv in seenV:
        Adj[sv] = seenV
    
    # print("Adj[",v,"] :",Adj[v])
    
    
    
    y = len(Adj[v]) - len(G[v]) - 1
    for k in KG[v]:
        if k in Adj[v]:
            y += -1
    # print("v=",v+1,"y=",y)
    Y.append(str(y))

# print("ADj",Adj)

# print("G",G)

print(" ".join(Y))




def find(x):
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
 
def unite(x,y):
  x,y=find(x),find(y)
  if x!=y:
    if x>y:
        x,y=y,x
    par[x]+=par[y]
    par[y]=x
    
def same(x,y):
  return find(x)==find(y)
 
def size(x):
  return-par[find(x)]
 
N,M,K = map(int,input().split())
par=[-1]*N
B = [set() for _ in range(N)]
FF = [0]*N
for _ in range(M):
    a,b = map(int,input().split())
    unite(a-1,b-1)
    FF[a-1] += 1
    FF[b-1] += 1
# print(F)
for j in range(K):
    a,b = map(int,input().split())
    B[a-1].add(b-1)
    B[b-1].add(a-1)

Y = []
for i in range(N):
    y = size(i) - FF[i] -1
    for b in B[i]:
        if same(i,b):
            y += -1
    Y.append(str(y))
print(" ".join(Y))


Verdicts: Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Accepted