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):
from collections import deque,Counter
import sys
input = sys.stdin.readline

n,m,k = map(int,input().split())
frd = [[] for _ in range(n)]
blk = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    frd[a].append(b)
    frd[b].append(a)
for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    blk[c].append(d)
    blk[d].append(c)

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for i in range(n):
    ans = cnt[uni[i]] - len(frd[i]) - 1
    for b in blk[i]:
        if uni[i] == uni[b]: ans -= 1
    print(ans,end=" ")

from collections import deque,Counter

n,m,k = map(int,input().split())
frd = [[] for _ in range(n)]
blk = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    frd[a].append(b)
    frd[b].append(a)
for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    blk[c].append(d)
    blk[d].append(c)

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for i in range(n):
    ans = cnt[uni[i]] - len(frd[i]) - 1
    for b in blk[i]:
        if uni[i] == uni[b]: ans -= 1
    print(ans,end=" ")

from collections import deque,Counter
import sys
input = sys.stdin.readline

n,m,k = map(int,input().split())
ans = [0]*(n+1)
frd = [[] for _ in range(n+1)]

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

ucnt = 0
uni = [-1]*(n+1)
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,0))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if uni[nxt] != -1 or nxt == prev: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for _ in range(k):
    c,d = map(int,input().split())
    if uni[c] == uni[d]:
        ans[c] -= 1
        ans[d] -= 1

for i in range(1,n+1): 
    ans[i] += cnt[uni[i]] - 1
    print(ans[i],end=" ")

from collections import deque,Counter

n,m,k = map(int,input().split())
frd = [[] for _ in range(n)]
blk = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    frd[a].append(b)
    frd[b].append(a)
for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    blk[c].append(d)
    blk[d].append(c)

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for i in range(n):
    ans = cnt[uni[i]] - 1
    for f in frd[i]:
        if uni[i] == uni[f]: ans -= 1
    for b in blk[i]:
        if uni[i] == uni[b]: ans -= 1
    print(ans,end=" ")

from collections import deque,Counter
n,m,k = map(int,input().split())
G = [[] for _ in range(n)]

exc = [0]*n
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    exc[a] += 1
    exc[b] += 1

stk = deque()
grp = [-1]*n
grpnum = 0
def dfs(s,g):
    stk.append(s)
    grp[s] = g
    while stk:
        cur = stk.pop()
        for nxt in G[cur]:
            if grp[nxt] != -1: continue
            grp[nxt] = g
            stk.append(nxt)

for i in range(n):
    if grp[i] != -1: continue
    dfs(i,grpnum)
    grpnum += 1
cnt = Counter(grp)

for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if grp[c] == grp[d]:
        exc[c] += 1
        exc[d] += 1

ans = [cnt[grp[i]] - exc[i] - 1 for i in range(n)]
print(*ans)   

Verdicts: Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Accepted