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:
from collections import deque
n,m,k=map(int,input().split())
fr=[[]]
for i in range(n-1):
  fr.append([])
for i in range(m):
  a,b=map(int,input().split())
  fr[a-1].append(b)
  fr[b-1].append(a)

belong=[0]*n
anslist=[0]*n
count=0
def bfs(k):
  global count
  if belong[k-1]==0:
    count+=1
    use=deque()
    use.append(k)
    ans=0
    aldic=[]
    while use:
      if not bool(use):
        break
      else:
        check=use.popleft()
        if check not in aldic:
          aldic.append(check)
          for x in fr[check-1]:
            use.append(x)
    for x in aldic:
      belong[x-1]=count
      anslist[x-1]=len(aldic)-len(fr[x-1])-1

for i in range(1,n+1):
  bfs(i)
for i in range(k):
  a,b=map(int,input().split())
  if belong[a-1]==belong[b-1]:
    anslist[a-1]-=1
    anslist[b-1]-=1
for i in range(0,len(anslist)):
  if i!=len(anslist)-1:
    print(anslist[i],end=" ")
  else:
    print(anslist[i])

Submission status: Time Limit Exceeded

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

belong=[0]*n
large=[]
anslist=[0]*n
count=0
def bfs(k):
  global count
  if belong[k-1]==0:
    count+=1
    use=deque()
    use.append(k)
    ans=0
    aldic=[]
    for i in range(0,10**100):
      if not bool(use):
        break
      else:
        check=use.popleft()
        if check not in aldic:
          aldic.append(check)
          for x in fr[check-1]:
            use.append(x)
    for x in aldic:
      belong[x-1]=count
      anslist[x-1]=len(aldic)-len(fr[x-1])-1

for i in range(1,n+1):
  bfs(i)
for i in range(k):
  a,b=map(int,input().split())
  if belong[a-1]==belong[b-1]:
    anslist[a-1]-=1
    anslist[b-1]-=1
for i in range(0,len(anslist)):
  if i!=len(anslist)-1:
    print(anslist[i],end=" ")
  else:
    print(anslist[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m,k=map(int,input().split())
fr=[{}]
for i in range(n-1):
  fr.append({})
for i in range(m):
  a,b=map(int,input().split())
  fr[a-1][b]=1
  fr[b-1][a]=1
for i in range(k):
  a,b=map(int,input().split())
  fr[a-1][b]=0
  fr[b-1][a]=0

def bfs(k):
  use=deque()
  use.append(k)
  ans=0
  aldic={}
  for i in range(0,10**100):
    if not bool(use):
      if k!=n:
        print(ans-1,end=" ")
      else:
        print(ans-1)
      break
    else:
      check=use.popleft()
      if check not in aldic:
        aldic[check]=1
        for x in fr[check-1]:
          if fr[check-1][x]==1:
            use.append(x)
        try:
          if fr[k-1][check]==0:
            pass
          else:
            pass
        except KeyError:
          ans+=1

for i in range(1,n+1):
  bfs(i)

Submission status: Time Limit Exceeded

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

def bfs(k):
  use=deque()
  use.append(k)
  ans=0
  aldic={}
  for i in range(1,n+1):
    aldic[i]=0
  for x in bl[k-1]:
    aldic[x]=-1
  for i in range(0,10**100):
    if not bool(use):
      if k!=n:
        print(ans-len(fr[k-1])-1,end=" ")
      else:
        print(ans-len(fr[k-1])-1)
      break
    else:
      check=use.popleft()
      if aldic[check]==0:
        aldic[check]=1
        for x in fr[check-1]:
          if aldic[x]!=1:
            use.append(x)
        ans+=1
      elif aldic[check]==-1:
        for x in fr[check-1]:
          if aldic[x]!=1:
            use.append(x)
for i in range(1,n+1):
  bfs(i)

Submission status: Time Limit Exceeded

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

def bfs(k):
  use=deque()
  use.append(k)
  ans=0
  aldic={}
  for i in range(0,10**100):
    if not bool(use):
      minus=0
      for x in bl[k-1]:
        if x in aldic:
          minus+=1
      if k!=n:
        print(ans-len(fr[k-1])-1-minus,end=" ")
      else:
        print(ans-len(fr[k-1])-1-minus)
      break
    else:
      check=use.popleft()
      if not check in aldic:
        aldic[check]=1
        for x in fr[check-1]:
          if not x in aldic:
            use.append(x)
        ans+=1
for i in range(1,n+1):
  bfs(i)

Submission status: Time Limit Exceeded

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

def bfs(k):
  use=deque()
  use.append(k)
  ans=0
  aldic={}
  for i in range(0,10**100):
    if not bool(use):
      if k!=n:
        print(ans-len(fr[k-1])-1,end=" ")
      else:
        print(ans-len(fr[k-1])-1)
      break
    else:
      check=use.popleft()
      if not check in aldic:
        aldic[check]=1
        for x in fr[check-1]:
          if not x in aldic:
            use.append(x)
        if not check in bl[k-1]:
          ans+=1
for i in range(1,n+1):
  bfs(i)

Submission status: Time Limit Exceeded

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

def bfs(k):
  use=deque()
  use.append(k)
  ans=0
  aldic={}
  for i in range(0,10**100):
    if not bool(use):
      if k!=n:
        print(ans-len(fr[k-1])-1,end=" ")
      else:
        print(ans-len(fr[k-1])-1)
      break
    else:
      check=use.popleft()
      if not check in aldic:
        aldic[check]=1
        for x in fr[check-1]:
          if not x in aldic:
            use.append(x)
        if not check in bl[k-1]:
          ans+=1
for i in range(1,n+1):
  bfs(i)

Submission status: Time Limit Exceeded

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

def bfs(k):
  use=deque()
  use.append(k)
  ans=0
  aldic={}
  for i in range(0,10**100):
    if not bool(use):
      if k!=n:
        print(ans-len(fr[k-1])-1,end=" ")
      else:
        print(ans-len(fr[k-1])-1)
      break
    else:
      check=use.popleft()
      if not check in aldic:
        aldic[check]=1
        for x in fr[check-1]:
            use.append(x)
        if not check in bl[k-1]:
          ans+=1
for i in range(1,n+1):
  bfs(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200100)

def abc157_d():
    N, M, K = map(int, input().split())
    fr = [set() for _ in range(N)]
    bl = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        fr[a].add(b)
        fr[b].add(a)
    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        bl[c].add(d)
        bl[d].add(c)

    def dfs(nd, lb):
        nonlocal label, gr
        label[nd] = lb
        gr[lb].add(nd)
        for ch in fr[nd]:
            if label[ch] != -1: continue
            dfs(ch, lb)

    label = [-1] * N
    lb = 0
    gr = []
    for i in range(N):
        if label[i] != -1: continue
        gr.append(set())
        dfs(i, lb)
        lb += 1

    ans = [0] * N
    for i in range(N):
        cand = gr[label[i]] - fr[i] - bl[i]
        ans[i] = len(cand) - 1
    print(*ans, sep=' ')

abc157_d()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

class prof:
    def __init__(self, num):
        self.num = num
        self.friends = deque([])
        self.blocks = deque([])        
        self.clus = -1
        self.ca = 0

    def set_friends(self, fre):
        self.friends.append(fre)

    def set_blocks(self, blo):
        self.blocks.append(blo)

    def set_clus(self, cl):
        self.clus = cl

    def set_ca(self, ca):
        self.ca = ca
    


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):

    nodes = [prof(i) for i in range(N)]

    for ai, bi in zip(A, B):
        nodes[ai-1].set_friends(bi)
        nodes[bi-1].set_friends(ai)
    for ai, bi in zip(C, D):
        nodes[ai-1].set_blocks(bi)
        nodes[bi-1].set_blocks(ai)
    
    cl = 0
    ser = set(range(1,N+1))
    finished = []
    while len(finished) != N:
        # cl +=1 
        q = deque([list(ser - set(finished))[0]])
        f_temp = []
        while bool(q):
            temp = q.popleft()
            if temp not in f_temp:
                # nodes[temp-1].set_clus(cl)
                f_temp.append(temp)
                for t in nodes[temp-1].friends:
                    if t not in f_temp : q.append(t)
            f_set = set(f_temp)
            for gr in f_temp:
                fr = set(nodes[gr-1].friends)
                bl = set(nodes[gr-1].blocks)
                nodes[gr-1].set_ca(len(f_set - fr - bl)-1)
        finished.extend(f_temp)

    print(*[x.ca for x in nodes])

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  # type: "List[int]"
    D = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

class prof:
    def __init__(self, num):
        self.num = num
        self.friends = []
        self.blocks = []        
        self.clus = -1
        self.ca = 0

    def set_friends(self, fre):
        self.friends.append(fre)

    def set_blocks(self, blo):
        self.blocks.append(blo)

    def set_clus(self, cl):
        self.clus = cl

    def set_ca(self, ca):
        self.ca = ca
    


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):

    nodes = [prof(i) for i in range(N)]

    for ai, bi in zip(A, B):
        nodes[ai-1].set_friends(bi)
        nodes[bi-1].set_friends(ai)
    for ai, bi in zip(C, D):
        nodes[ai-1].set_blocks(bi)
        nodes[bi-1].set_blocks(ai)
    
    cl = 0
    ser = set(range(1,N+1))
    finished = []
    while len(finished) != N:
        cl +=1 
        q = deque([list(ser - set(finished))[0]])
        f_temp = []
        while bool(q):
            temp = q.popleft()
            if temp not in f_temp:
                nodes[temp-1].set_clus(cl)
                f_temp.append(temp)
                for t in nodes[temp-1].friends:
                    if t not in f_temp : q.append(t)
            f_set = set(f_temp)
            for gr in f_temp:
                fr = set(nodes[gr-1].friends)
                bl = set(nodes[gr-1].blocks)
                nodes[gr-1].set_ca(len(f_set - fr - bl)-1)
        finished.extend(f_temp)


    print(*[x.ca for x in nodes])





    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  # type: "List[int]"
    D = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2020-05-22
def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    networks = {}  # The dict of networks as sets. Keys are leaders.
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        network = set()
        network_add = network.add
        stack = [person]
        stack_append = stack.append
        stack_pop = stack.pop
        while stack:
            new = stack_pop()
            visited[new] = True
            net_leaders[new] = person
            network_add(new)
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack_append(adj)
        networks[person] = network

    answers = []
    answers_append = answers.append
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        for block in blocks[person]:
            if block in net:
                ans -= 1
        answers_append(ans)

    print(*answers)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2020-05-22
def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    # The dict of networks as sets. Keys are leaders.
    networks = [None] * n
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        network = set()
        network_add = network.add
        stack = [person]
        stack_append = stack.append
        stack_pop = stack.pop
        while stack:
            new = stack_pop()
            visited[new] = True
            net_leaders[new] = person
            network_add(new)
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack_append(adj)
        networks[person] = network

    answers = []
    answers_append = answers.append
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        for block in blocks[person]:
            if block in net:
                ans -= 1
        answers_append(ans)

    print(*answers)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2020-05-22
def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    networks = {}  # The dict of networks as sets. Keys are leaders.
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        network = set()
        stack = [person]
        stack_append = stack.append
        stack_pop = stack.pop
        while stack:
            new = stack_pop()
            visited[new] = True
            net_leaders[new] = person
            network.add(new)
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack_append(adj)
        networks[person] = network

    answers = []
    answers_append = answers.append
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        for block in blocks[person]:
            if block in net:
                ans -= 1
        answers_append(ans)

    print(*answers)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2020-05-22
def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    networks = {}  # The dict of networks as sets. Keys are leaders.
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        networks[person] = set()
        stack = [person]
        while stack:
            new = stack.pop()
            visited[new] = True
            net_leaders[new] = person
            networks[person].add(new)
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack.append(adj)

    answers = [0] * n
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        for block in blocks[person]:
            if block in net:
                ans -= 1
        answers[person] = ans

    print(*answers)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2020-05-22
def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    networks = {}  # The dict of networks as sets. Keys are leaders.
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        networks[person] = set()
        stack = [person]
        while stack:
            new = stack.pop()
            visited[new] = True
            net_leaders[new] = person
            networks[person].add(new)
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack.append(adj)

    answers = []
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        for block in blocks[person]:
            if block in net:
                ans -= 1
        answers.append(ans)

    print(*answers)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2020-05-22
from collections import deque


def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    networks = {}  # The dict of networks as sets. Keys are leaders.
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        networks[person] = set()
        stack = deque([person])
        while stack:
            new = stack.pop()
            visited[new] = True
            net_leaders[new] = person
            networks[person].add(new)
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack.append(adj)

    answers = []
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        for block in blocks[person]:
            if block in net:
                ans -= 1
        answers.append(ans)

    print(*answers)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m, k = map(int, input().split())
friend = [set() for _ in range(n + 1)]
block = [set() for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    friend[a].add(b)
    friend[b].add(a)
for i in range(k):
    a, b = map(int, input().split())
    block[a].add(b)
    block[b].add(a)
res = [0] * n
visit = [0] * n
queue = deque()
for i in range(1, n + 1):
    if visit[i-1]:
        continue
    link = {i}
    queue.append(i)
    visit[i-1] = 1
    while queue:
        j = queue.pop()
        for k in friend[j]:
            if visit[k-1] == 0:
                queue.append(k)
                visit[k-1] = 1
                link.add(k)
        for i in link:
            res[i-1] = len(link)-len(link & friend[i]) - len(link & block[i]) - 1
print(*res)

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
friend = [set() for _ in range(n + 1)]
block = [set() for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    friend[a].add(b)
    friend[b].add(a)
for i in range(k):
    a, b = map(int, input().split())
    block[a].add(b)
    block[b].add(a)
res = [0] * n
visit = [0] * n
for i in range(1, n + 1):
    if visit[i-1]:
        continue
    link = {i}
    queue = [i]
    visit[i-1] = 1
    while queue:
        j = queue.pop(0)
        for k in friend[j]:
            if visit[k-1] == 0:
                queue.append(k)
                visit[k-1] = 1
                link.add(k)
        for i in link:
            res[i-1] = len(link)-len(link & friend[i]) - len(link & block[i]) - 1
print(*res)

Submission status: Time Limit Exceeded

Solution code:
def BFS(x):
  cnt=1
  v=deque([x])
  k=0
  zu[x]=k
  lis=[x]
  roots[x]=x
  
  while len(v)>0:
    a=v.popleft()
    roots[a]=x
    for i in fr[a]:
      if zu[i]==-1:
        zu[i]=zu[a]+1
        v.append(i)
        cnt += 1
        lis.append(i)

          
  return lis

##############################

from collections import deque
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K
fr=[ [] for _ in range(N)]
bl=[ set() for _ in range(N)]
zu=[ -1 for _ in range(N)] #訪問済みリスト
roots= [ -1 for _ in range(N)]

for i in range(M):
  A[i],B[i]= map(int,input().split())
  fr[A[i]-1].append(B[i]-1)
  fr[B[i]-1].append(A[i]-1)
for k in range(K):
  C[k],D[k]= map(int,input().split())
  bl[C[k]-1].add(D[k]-1)
  bl[D[k]-1].add(C[k]-1)
fr_set= [set(fr[i]) for i in range(N)]
    
size=[0]*N
pena=[0]*N
for i in range(N):
  if zu[i]==-1:
    kumi=BFS(i) #リスト
    for k in range(len(kumi)):
      size[kumi[k]]=len(kumi)
      
#print(size)
#print(roots)
      
ans=[0 for _ in range(N)]      
for i in range(N):
  ans[i]= size[i]-1
  for j in range(N):
    if i==j:
      pass
    else:
      if roots[j]==roots[i]:
        if j in bl[i] or j in fr_set[i]:
          ans[i] -= 1      
      
print(*ans)

Submission status: Time Limit Exceeded

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

F=[set() for i in range(n)]
B=[set() for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	a,b=a-1,b-1
	F[a].add(b)
	F[b].add(a)
for i in range(k):
	c,d=map(int,input().split())
	c,d=c-1,d-1
	B[c].add(d)
	B[d].add(c)
	
T=[set() for i in range(n)]
D=[0]*n
for i in range(n):
	if D[i]:
	    continue
	que=deque([])
	que.append(i)
	T[i].add(i)
	while que:
	    p=que.popleft()
	    for np in F[p]:
	        if D[np]!=1:
	            que.append(np)
	            T[i].add(np)
	            D[np]=1

S=[[] for i in range(n)]
for i in range(n):
    if T[i]:
        for t in T[i]:
            S[t]=list(T[i])[:]
            S[t].remove(t)
		
R=[0]*n
for i in range(n):
	R[i]=len(S[i])-len(F[i])-len(set(S[i])&set(B[i]))
print(*R)

Submission status: Time Limit Exceeded

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

F=[set() for i in range(n)]
B=[set() for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	F[a-1].add(b-1)
	F[b-1].add(a-1)
for i in range(k):
	c,d=map(int,input().split())
	B[c-1].add(d-1)
	B[d-1].add(c-1)
	
T=[[] for i in range(n)]
D=[0]*n
for i in range(n):
	if D[i]==1:
	    continue
	que=deque([])
	que.append(i)
	T[i].append(i)
	while que:
	    p=que.popleft()
	    for np in F[p]:
	        if D[np]!=1:
	            que.append(np)
	            T[i].append(np)
	            D[np]=1

S=[[] for i in range(n)]
for i in range(n):
    if T[i]:
        for t in T[i]:
            S[t]=set(T[i][:])
            S[t].remove(t)
		
R=[0]*n
for i in range(n):
	R[i]=len(S[i])-len(F[i])-len(set(S[i])&set(B[i]))
print(*R)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m,k=map(int,input().split())

L=[set() for i in range(n)]
U=[set() for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	L[a-1].add(b-1)
	L[b-1].add(a-1)
for i in range(k):
	c,d=map(int,input().split())
	U[c-1].add(d-1)
	U[d-1].add(c-1)
	
S=[[] for i in range(n)]
D=[0]*n

def dfs(n):
	D[n]=1
	T.append(n)
	for np in L[n]:
		if D[np]!=1:
			dfs(np)
			
for i in range(n):
	if D[i]==1:
	    continue
	T=[]
	dfs(i)
	for t in T:
		S[t]=T[:]
		S[t].remove(t)
		
R=[0]*n
for i in range(n):
	R[i]=len(S[i])-len(L[i])-len(set(S[i])&set(U[i]))
print(*R)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

F = [[[] for _ in range(2)] for _ in range(N)]
for m in AB:
    F[m[0] - 1][0].append(m[1] - 1)
    F[m[1] - 1][0].append(m[0] - 1)
for k in CD:
    F[k[0] - 1][1].append(k[1] - 1)
    F[k[1] - 1][1].append(k[0] - 1)

L = [0] * N
m = [[] for _ in range(N)]

for i in range(N):
    if L[i] != 0:
        continue
    l = []
    c = 0
    d = [0] * N
    d[i] = 1
    l.append(i)
    Q = deque()
    Q.append(i)
    while len(Q) > 0:
        q = Q.pop()
        for j in range(len(F[q][0])):
            a = F[q][0][j]
            if d[a] == 1:
                continue
            d[a] = 1
            c += 1
            Q.append(a)
            l.append(a)
    m[i] = l
    for j in l:
        L[j] = c
        m[j] = l

for i in range(N):
    print(L[i] - len(F[i][0]) - len(set(F[i][1]) & set(m[i])), end=' ')

print('')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m,k=map(int,input().split())

L=[[] for i in range(n)]
U=[[] for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	L[a-1].append(b-1)
	L[b-1].append(a-1)
for i in range(k):
	c,d=map(int,input().split())
	U[c-1].append(d-1)
	U[d-1].append(c-1)
	
S=[[] for i in range(n)]
D=[0]*n

def dfs(n):
	D[n]=1
	T.append(n)
	for np in L[n]:
		if D[np]!=1:
			dfs(np)
			
for i in range(n):
	if D[i]==1:
	    continue
	T=[]
	dfs(i)
	for t in T:
		S[t]=T[:]
		S[t].remove(t)
		
R=[0]*n
for i in range(n):
	R[i]=len(S[i])-len(L[i])-len(set(S[i])&set(U[i]))
print(*R)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m,k=map(int,input().split())

L=[[] for i in range(n)]
U=[[] for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	L[a-1].append(b-1)
	L[b-1].append(a-1)
for i in range(k):
	c,d=map(int,input().split())
	U[c-1].append(d-1)
	U[d-1].append(c-1)
	
S=[[] for i in range(n)]
D=[0]*n

def dfs(n):
	D[n]=1
	T.append(n)
	for np in L[n]:
		if D[np]!=1:
			dfs(np)
			
for i in range(n):
	if D[i]!=1:
		T=[]
		dfs(i)
	for t in T:
		S[t]=T[:]
		S[t].remove(t)
		
R=[0]*n
for i in range(n):
	R[i]=len(S[i])-len(L[i])-len(set(S[i])&set(U[i]))
print(*R)