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: Time Limit Exceeded

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

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)] 
          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        try:
            nxt = fl.index(-1)
        except:
            nxt = 0

    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        print(ff, end = ' ')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)] 
          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    #dic = {}
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        #cnt = 0
        while q:
            now = q.popleft()
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    #cnt +=1
                    q.append(f)
        #dic[nxt] = cnt
        try:
            nxt = fl.index(-1)
        except:
            nxt = 0
    dic = collections.Counter(fl)
    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])-1
        mbf.append(ff)
    print(*mbf)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N,M,K = list(map(int,input().split()))
fr = [[] for i in range(N+1)]
bl = [[] for i in range(N+1)] 
      
for _ in range(M):
    a,b = map(int,input().split())
    fr[a].append(b)
    fr[b].append(a)
for _ in range(K):
    c,d = map(int,input().split())
    bl[c].append(d)
    bl[d].append(c)

fl = [-1 for i in range(N+1)]
fl[0] = 0
fl[1] = 1
nxt = 1
#dic = {}
while nxt != 0:
    q = collections.deque([nxt])
    
    fl[nxt]=nxt
    #cnt = 0
    while q:
        now = q.popleft()
        for f in fr[now]:
            if fl[f] == -1:
                fl[f] = nxt
                #cnt +=1
                q.append(f)
    #dic[nxt] = cnt
    try:
        nxt = fl.index(-1)
    except:
        nxt = 0
dic = collections.Counter(fl)
mbf = collections.deque()
for i in range(1,N+1):
    ff = 0
    for j in bl[i]:
        if fl[j] == fl[i]:
            ff -= 1
    
    ff += dic[fl[i]]-len(fr[i])-1
    mbf.append(ff)
print(*mbf)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N,M,K = list(map(int,input().split()))
fr = [[] for i in range(N+1)]
bl = [[] for i in range(N+1)] 
      
for _ in range(M):
    a,b = map(int,input().split())
    fr[a].append(b)
    fr[b].append(a)
for _ in range(K):
    c,d = map(int,input().split())
    bl[c].append(d)
    bl[d].append(c)

fl = [-1 for i in range(N+1)]
fl[0] = 0
fl[1] = 1
nxt = 1
dic = {}
while nxt != 0:
    q = collections.deque([nxt])
    
    fl[nxt]=nxt
    cnt = 0
    while q:
        now = q.popleft()
        for f in fr[now]:
            if fl[f] == -1:
                fl[f] = nxt
                cnt +=1
                q.append(f)
    dic[nxt] = cnt
    try:
        nxt = fl.index(-1)
    except:
        nxt = 0

mbf = collections.deque()
for i in range(1,N+1):
    ff = 0
    for j in bl[i]:
        if fl[j] == fl[i]:
            ff -= 1
    
    ff += dic[fl[i]]-len(fr[i])
    mbf.append(ff)
print(*mbf)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N,M,K = list(map(int,input().split()))
fr = [[] for i in range(N+1)]
bl = [[] for i in range(N+1)] 
      
for _ in range(M):
    a,b = map(int,input().split())
    fr[a].append(b)
    fr[b].append(a)
for _ in range(K):
    c,d = map(int,input().split())
    bl[c].append(d)
    bl[d].append(c)

fl = [-1 for i in range(N+1)]
fl[0] = 0
fl[1] = 1
nxt = 1
dic = {}
while nxt != 0:
    q = collections.deque([nxt])
    
    fl[nxt]=nxt
    cnt = 0
    while q:
        now = q.popleft()
        for f in fr[now]:
            if fl[f] == -1:
                fl[f] = nxt
                cnt +=1
                q.append(f)
    dic[nxt] = cnt
    if -1 in set(fl):
        nxt = fl.index(-1)
    else:
        nxt = 0

mbf = collections.deque()
for i in range(1,N+1):
    ff = 0
    for j in bl[i]:
        if fl[j] == fl[i]:
            ff -= 1
    
    ff += dic[fl[i]]-len(fr[i])
    mbf.append(ff)
print(*mbf)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N,M,K = list(map(int,input().split()))
fr = [[] for i in range(N+1)]
bl = [[] for i in range(N+1)] 
      
for _ in range(M):
    a,b = map(int,input().split())
    fr[a].append(b)
    fr[b].append(a)
for _ in range(K):
    c,d = map(int,input().split())
    bl[c].append(d)
    bl[d].append(c)

fl = [-1 for i in range(N+1)]
fl[0] = 0
fl[1] = 1
nxt = 1
dic = {}
while nxt != 0:
    q = collections.deque([nxt])
    
    fl[nxt]=nxt
    cnt = 0
    while q:
        now = q.popleft()
        for f in fr[now]:
            if fl[f] == -1:
                fl[f] = nxt
                cnt +=1
                q.append(f)
    dic[nxt] = cnt
    if -1 in fl:
        nxt = fl.index(-1)
    else:
        nxt = 0

mbf = collections.deque()
for i in range(1,N+1):
    ff = 0
    for j in bl[i]:
        if fl[j] == fl[i]:
            ff -= 1
    
    ff += dic[fl[i]]-len(fr[i])
    mbf.append(ff)
print(*mbf)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N,M,K = list(map(int,input().split()))
fr = [[] for i in range(N+1)]
bl = [[] for i in range(N+1)] 
      
for _ in range(M):
    a,b = map(int,input().split())
    fr[a].append(b)
    fr[b].append(a)
for _ in range(K):
    c,d = map(int,input().split())
    bl[c].append(d)
    bl[d].append(c)

fl = [-1 for i in range(N+1)]
fl[0] = 0
fl[1] = 1
nxt = 1
dic = {}
while nxt != 0:
    q = collections.deque([nxt])
    
    fl[nxt]=nxt
    cnt = 0
    while q:
        now = q.popleft()
        for f in fr[now]:
            if fl[f] == -1:
                fl[f] = nxt
                cnt +=1
                q.append(f)
    dic[nxt] = cnt
    if -1 in fl:
        nxt = fl.index(-1)
    else:
        nxt = 0

mbf = []
for i in range(1,N+1):
    ff = 0
    for j in bl[i]:
        if fl[j] == fl[i]:
            ff -= 1
    
    ff += dic[fl[i]]-len(fr[i])
    mbf.append(ff)
print(*mbf)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N,M,K = list(map(int,input().split()))
fr = [[] for i in range(N+1)]
bl = [[] for i in range(N+1)] 
      
for _ in range(M):
    a,b = map(int,input().split())
    fr[a].append(b)
    fr[b].append(a)
for _ in range(K):
    c,d = map(int,input().split())
    bl[c].append(d)
    bl[d].append(c)

mbf = []
for i in range(1,N+1):
    q = collections.deque([i])
    fl = [-1 for i in range(N+1)]
    fl[i]=0
    cnt = 0
    while q:
        now = q.popleft()
        for f in fr[now]:
            if fl[f] == -1:
                if fl[now]==0:
                    fl[f] = 1
                else:
                    fl[f] = 'a'
                    cnt +=1
                if f in bl[i]:
                    fl[f] = 'b'
                    cnt -=1
                q.append(f)
    
    mbf.append(cnt)
print(*mbf)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
n, m, k = map(int, sys.stdin.readline().split())
F = [[] for _ in range(n)]
B = [[] for _ in range(n)]

for i in range(m):
    a,b = map(lambda x: x-1, map(int, sys.stdin.readline().split()))
    F[a].append(b)
    F[b].append(a)

for i in range(k):
    c,d = map(lambda x: x-1, map(int, sys.stdin.readline().split()))
    B[c].append(d)
    B[d].append(c)

ans = []
for i in range(n):
    que = deque([i])
    V = [False]*n
    V[i] = True
    _B = set(B[i])
    _F = set(F[i])
    _ans = 0
    while que:
        nw = que.popleft()
        for nx in F[nw]:
            if V[nx]: continue
            V[nx] = True
            if nx not in _B and not nx in _F:
                _ans += 1
            que.append(nx)
    ans.append(_ans)
print(" ".join([str(_ans) for _ans in ans]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5) #再帰回数を増やさないとREになる


N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] 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)
for _ in range(K):
  c, d = map(int, input().split())
  block[c-1].append(d-1)
  block[d-1].append(c-1)


friendnetwork = []
sgn = [0 for _ in range(N)] #groupnumを書いていく
groupnum = 0

def makenetwork(n, groupnum):
  for item in friend[n]:
    if sgn[item] > 0:
      continue
    else:
      sgn[item] = groupnum
      makenetwork(item, groupnum)

for k in range(N):
  if sgn[k] == 0:
    groupnum += 1
    sgn[k] = groupnum
    makenetwork(k, groupnum)


friends = [[] for _ in range(groupnum)]
for k in range(N):
  friends[sgn[k]-1].append(k)

ans = ''
for k in range(N):
  num = len(friends[sgn[k]-1])-1  - len(friend[k])
  for item in block[k]:
    if sgn[item] == sgn[k]:
      num -= 1
  ans += str(num) + ' '

ans.rstrip()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
import copy
n, m, k = map(int, input().split())
#friends[person_id] = {f1, f2...}
friends = dd(set)
blocks = dd(set)
for i in range(m):
    a, b = map(int, input().split())
    friends[a].add(b)
    friends[b].add(a)
for i in range(k):
    c, d = map(int, input().split())
    blocks[c].add(d)
    blocks[d].add(c)
#print(friends)
#print(blocks)

#BFS
group_now = -1
#person_num_dic[person] -> group_num
person_num_dic = {}
for person in range(1, n+1):
    if person not in person_num_dic:
        group_now += 1
        person_num_dic[person] = group_now
        stack = set([person])
        while len(stack) != 0:
            #print(stack)
            next_stack = set()
            for target in list(stack):
                f_of_f = friends[target]
                for man in list(f_of_f):
                    if man not in person_num_dic:
                        person_num_dic[man] = group_now
                        next_stack.add(man)
            stack = next_stack
        #print()
#print(person_num_dic)

#group_dic[group] -> set:{n1, n2, ...}
group_dic = dd(set)
for person, group in person_num_dic.items():
    group_dic[group].add(person)
#print(group_dic)

ans = []
for person in range(1, n+1):
    group = person_num_dic[person]
    cand_friend = copy.copy(group_dic[group])
    #print(cand_friend)
    cand_friend -= friends[person]
    cand_friend -= set([person])
    cand_friend -= blocks[person]
    ans.append(len(cand_friend))
    #print(cand_friend)
    #print()
print(*ans, sep=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

fri = [[] for _ in range(n+1)]
blo = [[] for _ in range(n+1)]

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

for i in range(k):
    a, b = map(int, input().split())
    blo[a].append(b)
    blo[b].append(a)


gru = [-1] * (n+1)
gru[0] = 0
visited = [False]*(n+1)
D = {}

for root in range(1,n+1):
    if visited[root]:
        continue
    
    D[root]= set([root])
    d = deque()
    d.append(root)
    while d:
        v = d.popleft()
        visited[v] = True
        gru[v] = root
        for to in fri[v]:
            if visited[to]:
                continue
            D[root].add(to)
            d.append(to)


nans = [0]*n
for i in range(1,n+1):
    g = D[gru[i]]
    ans = len(g)-len(fri[i])-1
    for b in blo[i]:
        if b in g:
            ans -= 1
    nans[i-1] = ans

print(*nans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

fri = [[] for _ in range(n+1)]
blo = [[] for _ in range(n+1)]

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

for i in range(k):
    a, b = map(int, input().split())
    blo[a].append(b)
    blo[b].append(a)


gru = [-1] * (n+1)
gru[0] = 0
visited = [False]*(n+1)
D = {}

for root in range(1,n+1):
    if visited[root]:
        continue
    
    D[root]= set([root])
    d = deque()
    d.append(root)
    while d:
        v = d.popleft()
        visited[v] = True
        gru[v] = root
        for to in fri[v]:
            if visited[to]:
                continue
            D[root].add(to)
            d.append(to)


for i in range(1,n+1):
    g = D[gru[i]]
    ans = len(g)-len(fri[i])-1
    for b in blo[i]:
        if b in g:
            ans -= 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

fri = [[] for _ in range(n+1)]
blo = [[] for _ in range(n+1)]

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

for i in range(k):
    a, b = map(int, input().split())
    blo[a].append(b)
    blo[b].append(a)


gru = [-1] * (n+1)
gru[0] = 0
gru[1] = 0

nosa = 1
nowgru = 0
grouplist = [[] for _ in range(n+1)]
while True:

    d = deque()
    d.append(nosa)
    grouplist[nowgru].append(nosa)
    gru[nosa] = nowgru
    while d:
        v = d.pop()
        for i in fri[v]:
            if gru[i] != -1:
                continue
            gru[i] = nowgru
            d.append(i)
            grouplist[nowgru].append(i)

    nowgru +=1
    if -1 in gru:
        nosa = gru.index(-1)
    else:
        break


for i in range(1,n+1):
    g = grouplist[gru[i]]
    ans = len(g)-len(fri[i])-1
    for b in blo[i]:
        if b in g:
            ans -= 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
n,m,k= map(int, input().split())
 
fri = [[] for _ in range(n+1)]
blo = [[] for _ in range(n+1)]
 
for i in range(m):
    a, b = map(int, input().split())
    fri[a].append(b)
    fri[b].append(a)
 
for i in range(k):
    a, b = map(int, input().split())
    blo[a].append(b)
    blo[b].append(a)
 
 
gru = [-1] * (n+1)
gru[0] = 0
gru[1] = 0
 
nosa = 1
nowgru = 0
grouplist = [[] for _ in range(n+1)]
grouplist[nowgru].append(nosa)
while True:
 
    d = deque()
    d.append(nosa)
 
    while d:
        v = d.popleft()
        for i in fri[v]:
            if gru[i] != -1:
                continue
            gru[i] = nowgru
            d.append(i)
            grouplist[nowgru].append(i)
 
    nowgru +=1
    if -1 in gru:
        nosa = gru.index(-1)
    else:
        break
 
 
for i in range(1,n+1):
    print(len(set(grouplist[gru[i]])-set(blo[i]))-len(fri[i])-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

fri = [[] for _ in range(n+1)]
blo = [[] for _ in range(n+1)]

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

for i in range(k):
    a, b = map(int, input().split())
    blo[a].append(b)
    blo[b].append(a)


gru = [-1] * (n+1)
gru[0] = 0
gru[1] = 0

nosa = 1
nowgru = 0
grouplist = [[] for _ in range(n+1)]
grouplist[nowgru].append(nosa)
while True:

    d = deque()
    d.append(nosa)

    while d:
        v = d.popleft()
        for i in fri[v]:
            if gru[i] != -1:
                continue
            gru[i] = nowgru
            d.append(i)
            grouplist[nowgru].append(i)

    nowgru +=1
    if -1 in gru:
        nosa = gru.index(-1)
    else:
        break


for i in range(1,n+1):
    print(len(set(grouplist[gru[i]])-set(blo[i]))-len(fri[i])-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

fri = [[] for _ in range(n+1)]
blo = [[] for _ in range(n+1)]

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

for i in range(k):
    a, b = map(int, input().split())
    blo[a].append(b)
    blo[b].append(a)


gru = [-1] * (n+1)
gru[0] = 0
gru[1] = 0

nosa = 1
nowgru = 0
grouplist = [[] for _ in range(n+1)]
grouplist[nowgru].append(nosa)
while True:

    d = deque()
    d.append(nosa)

    while d:
        v = d.popleft()
        for i in fri[v]:
            if gru[i] != -1:
                continue
            gru[i] = nowgru
            d.append(i)
            grouplist[nowgru].append(i)

    nowgru +=1
    if -1 in gru:
        nosa = gru.index(-1)
    else:
        break


for i in range(1,n+1):
    print(len(set(grouplist[gru[i]])-set(fri[i])-set(blo[i])-set([i])))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m, k = map(int, input().split())
fr = [[] for _ in range(n)]
bl = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    fr[a-1].append(b)
    fr[b-1].append(a)
for _ in range(k):
    c, d = map(int, input().split())
    bl[c-1].append(d)
    bl[d-1].append(c)

ans = [0]*n
for i in range(1, n+1):
    q = deque([i])
    tf = [1]*n
    tf[i-1] = 0
    while q:
        p = q.popleft()
        for node in fr[p-1]:
            if tf[node-1]:
                tf[node-1] = 0
                q.append(node)
                if node in bl[i-1]:
                    continue
                ans[i-1] += 1

ans = [str(ans[i]-len(fr[i])) for i in range(n)]
print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
N, M, K = map(int, input().split())
ABs = [tuple(map(int, input().split())) for _ in range(M)]
CDs = [tuple(map(int, input().split())) for _ in range(K)]
graph = {i+1: set() for i in range(N)}
block = {i+1: set() for i in range(N)}
ans = {i+1: 0 for i in range(N)}


def connected_components(graph):
    seen = set()
    def component(n):
        nodes = set([n])
        while nodes:
            n = nodes.pop()
            seen.add(n)
            nodes |= set(graph[n]) - seen
            yield n
    for n in graph:
        if n not in seen:
            yield set(component(n))


for a, b in ABs:
    graph[a].add(b)
    graph[b].add(a)
for c, d in CDs:
    block[c].add(d)
    block[d].add(c)
for connected in connected_components(graph):
    for c in connected:
        ans[c] = len(connected - (graph[c] | block[c]))
for i in range(1, N+1):
    print(ans[i]-1, end=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

N, M, K = map(int, input().split())
G = [[] for _ in range(N)]
AB = []
for _ in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    AB.append((a-1, b-1))

H = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    H[c-1].append(d-1)
    H[d-1].append(c-1)

seen = [0]*N
def dfs(v):
    seen[v] = 1
    ret = [v]
    for u in G[v]:
        if seen[u] == 1: continue
        ret += dfs(u)
    return ret

num = [0]*N
for v in range(N):
    if seen[v] == 1: continue
    new = dfs(v)
    size = len(new)
    for n in new:
        num[n] = len(set(new) - set(H[n]) - set(G[n])) - 1
    
print(' '.join(map(str, num)))

Submission status: Time Limit Exceeded

Solution code:
# dfs
import collections
n,m,k = map(int, input().split())

friend = [[]*(n+1) for _ in range(n+1)]
block = [[]*(n+1) for _ in range(n+1)]
friend_candidate = [[0]*(n+1) for _ in range(n+1)]
teams = [0]*(n+1)
for _ in range(m):
  a,b = map(int, input().split())
  friend[a].append(b)
  friend[b].append(a)
for _ in range(k):
  c,d = map(int, input().split())
  block[c].append(d)
  block[d].append(c)
  
def dfs(i):
  teams[i] = team
  for j in friend[i]:
    if teams[j] != 0:
      continue
    teams[j] = team
    dfs(j)

team=1
for i in range(1,n+1):
  if teams[i] != 0:
    continue
  dfs(i)
  team+=1
c = collections.Counter(teams)
for i in range(1,n+1):
  temp = c[teams[i]]-len(friend[i])-1
  for j in block[i]:
    if teams[j] == teams[i]:
      temp -= 1
  print(temp,end='')
  if i != n:
    print(" ",end='')

Submission status: Time Limit Exceeded

Solution code:
# dfs
import collections
n,m,k = map(int, input().split())

friend = [[]*(n+1) for _ in range(n+1)]
block = [[]*(n+1) for _ in range(n+1)]
friend_candidate = [[0]*(n+1) for _ in range(n+1)]
teams = [0]*(n+1)
for _ in range(m):
  a,b = map(int, input().split())
  friend[a].append(b)
  friend[b].append(a)
for _ in range(k):
  c,d = map(int, input().split())
  block[c].append(d)
  block[d].append(c)
  
def hoge(man):
  for i in man:
    if teams[i] != 0:
      continue
    teams[i] = team
    for j in friend[i]:
      teams[j] = team
      hoge(friend[j])

team=1
for i in range(1,n+1):
  if teams[i] != 0:
    continue
  t=[i]
  hoge(t)
  team+=1
c = collections.Counter(teams)
for i in range(1,n+1):
  temp = c[teams[i]]-len(friend[i])-1
  for j in block[i]:
    if teams[j] == teams[i]:
      temp -= 1
  print(temp,end='')
  if i != n:
    print(" ",end='')

Submission status: Time Limit Exceeded

Solution code:
# D - Friend Suggestions
from collections import deque
N,M,K = map(int,input().split())
friend = [set() for _ in range(N+1)]
block = [{i} for i in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    friend[x].add(y)
    friend[y].add(x)
for _ in range(K):
    x,y = map(int,input().split())
    block[x].add(y)
    block[y].add(x)
connect = [{i} for i in range(N+1)]
check = [0]*(N+1)
for i in range(1,N+1):
    if check[i]!=0:
        continue
    que = deque([i])
    con = {i}
    while len(que)>0:
        j = que.popleft()
        for x in friend[j]:
            if x not in con:
                que.append(x)
                con.add(x)
    for x in con:
        connect[x] = set(con)
        check[x] = 1
ans = [len(connect[i].difference(friend[i],block[i])) for i in range(1,N+1)]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# D - Friend Suggestions
from collections import deque
N,M,K = map(int,input().split())
friend = [set() for _ in range(N+1)]
block = [{i} for i in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    friend[x].add(y)
    friend[y].add(x)
for _ in range(K):
    x,y = map(int,input().split())
    block[x].add(y)
    block[y].add(x)
connect = [{i} for i in range(N+1)]
for i in range(1,N+1):
    if connect[i]!={i}:
        continue
    que = deque([i])
    con = {i}
    while len(que)>0:
        j = que.popleft()
        for x in friend[j]:
            if x not in con:
                que.append(x)
                con.add(x)
    for x in con:
        connect[x] = set(con)
ans = [len(connect[i].difference(friend[i],block[i])) for i in range(1,N+1)]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# D - Friend Suggestions
N,M,K = map(int,input().split())
friend = [set() for _ in range(N+1)]
block = [set() for _ in range(N+1)]
friendly = [{i} for i in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    friend[x].add(y)
    friend[y].add(x)
    if y not in friendly[x]:
        friendly[x].add(y)
        friendly[y].add(x)
    friend_x = set(friendly[x])
    friend_y = set(friendly[y])
    for w in friend_x:
        friendly[w].add(y)
        for z in friend_y:
            friendly[w].add(z)
    for w in friend_y:
        friendly[w].add(x)
        for z in friend_x:
            friendly[w].add(z)
for _ in range(K):
    x,y = map(int,input().split())
    block[x].add(y)
    block[y].add(x)
ans = []
for i in range(1,N+1):
    tmp = []
    for x in friendly[i]:
        if x!=i and x not in friend[i] and x not in block[i]:
            tmp.append(x)
    ans.append(len(tmp))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n,m,k = map(int, input().split())
f = [[] for _ in range(n)]
g = [[] for _ in range(n)]

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

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

d = {}
parent = [-1] * n
seen = [False] * n

# DFS
for i in range(n):
    if seen[i]:
        continue
    stack = deque()
    # グループは集合で管理
    d[i] = set([i])
    stack = [i]
    while stack:
        v = stack.pop()
        seen[v] = True
        # 親を設定して同じ連結成分であることを判別する
        parent[v] = i
        for nv in f[v]:
            if seen[nv]:
                continue
            # 集合に追加する
            d[i].add(nv)
            stack.append(nv)

ans = [0] * n
for i in range(n):
    # 連結成分ごとに集合を取り出す
    group = d[parent[i]]
    # 集合の全要素数 - 友達 - ブロック - 自分
    sum = len(group) - len(f[i]) - len(set(g[i]) & group) - 1
    ans[i] = sum

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #親
        self.rank = [0 for _ in range(n)] #根の深さ

    #xの属する木の根を求める
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    #xとyの属する集合のマージ
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N, M, K = map(int, input().split())
tree = UnionFind(N)
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]

for _ in range(M):
    A, B = map(int, input().split())
    tree.unite(A-1, B-1)
    friend[A-1].append(B-1)
    friend[B-1].append(A-1)

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


ans = []
for i in range(N):
    cnt = 0
    for j in range(N):
        if j not in set(friend[i]) and j not in set(block[i]) and i != j:
            cnt += tree.same(i, j)
    ans.append(cnt)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    edge[a].append(b)
    edge[b].append(a)


from collections import deque
label=[-1]*n

i=0
for start in range(n):
    if label[start]!=-1:
        continue
    else:
        i+=1
        label[start]=i    
    dist_friends=[-1]*n
    dist_friends[start]=0
    f=deque([start])

    while f:
        v=f.popleft()        

        for e in edge[v]:
            if dist_friends[e]==-1 and label[e]==-1:
                dist_friends[e]=dist_friends[v]+1
                label[e]=i
                f.append(e)   

Renketsu=[0]*(n+1)

for i in label:
    Renketsu[i]+=1

Block=[0]*n
for _ in range(k):
    c,d=map(int,input().split())
    c,d=c-1,d-1
    if label[c]==label[d]:
        Block[c]+=1
        Block[d]+=1

ans=[]
for k in range(n):
    ans.append(Renketsu[label[k]]-1 - len(edge[k]) - Block[k])
print(*ans)