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

for i in range(M):
  A,B = map(int, input().split())
  friend[A].append(B)
  friend[B].append(A)

for i in range(K):
  C,D = map(int, input().split())
  block[C].append(D)
  block[D].append(C)
#print(friend)
#print(block)

import queue
grouping = [False]*(N+1)
#print(grouping)
grouping[0] = True
groups = []
for i in range(1,N+1):
  if grouping[i] == True:
    continue 
  #print(p)
  group = [i]
  grouping[i] = True
  q = queue.Queue()
  q.put(i)
  while not q.empty():
    #print('v:',visited)
    p = q.get()
    for f in friend[p]:
      #print(p,f)
      if grouping[f]==False:
        q.put(f)
        group.append(f)
        grouping[f] =True
  groups.append(group)
  #print('g:',grouping)
counts=[0]*(N+1)
for group in groups:
  gsize = len(group)
  for g in group:
    b = 0
    for h in block[g]:
      if h in group:
        b += 1
    counts[g] = gsize-1-len(friend[g])-b
print(' '.join(map(str,counts[1:])))

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
friend = [[] for _ in range(N+1)]
block = [[] for _ in range(N+1)]

for i in range(M):
  A,B = map(int, input().split())
  friend[A].append(B)
  friend[B].append(A)

for i in range(K):
  C,D = map(int, input().split())
  block[C].append(D)
  block[D].append(C)
#print(friend)
#print(block)

import queue
grouping = [False]*(N+1)
#print(grouping)
grouping[0] = True
groups = []
while False in grouping:
  for i in range(1,N):
    if grouping[i] == False:
      p = i
      break
  #print(p)
  visited = [False]*(N+1)
  group = [p]
  visited[p],grouping[p] =True,True
  q = queue.Queue()
  q.put(p)
  while not q.empty():
    #print('v:',visited)
    p = q.get()
    for f in friend[p]:
      #print(p,f)
      if visited[f]==False:
        q.put(f)
        group.append(f)
        visited[f],grouping[f] =True,True
  groups.append(group)
  #print('g:',grouping)
counts=[0]*(N+1)
for group in groups:
  gsize = len(group)
  for g in group:
    b = 0
    for h in block[g]:
      if h in group:
        b += 1
    counts[g] = gsize-1-len(friend[g])-b
print(' '.join(map(str,counts[1:])))

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
friend = [[] for _ in range(N+1)]
block = [[] for _ in range(N+1)]

for i in range(M):
  A,B = map(int, input().split())
  friend[A].append(B)
  friend[B].append(A)

for i in range(K):
  C,D = map(int, input().split())
  block[C].append(D)
  block[D].append(C)
#print(friend)
#print(block)

import queue
grouping = [False]*(N+1)
#print(grouping)
grouping[0] = True
groups = []
while False in grouping:
  for i in range(1,N):
    if grouping[i] == False:
      p = i
      break
  #print(p)
  visited = [False]*(N+1)
  group = [p]
  visited[p],grouping[p] =True,True
  q = queue.Queue()
  q.put(p)
  while not q.empty():
    #print('v:',visited)
    p = q.get()
    for f in friend[p]:
      #print(p,f)
      if visited[f]==False:
        q.put(f)
        group.append(f)
        visited[f],grouping[f] =True,True
  groups.append(group)
  #print('g:',grouping)
counts=[0]*(N+1)
for group in groups:
  for g in group:
    for h in group:
      if h not in block[g] and h!=g and h not in friend[g]:
        counts[g] += 1
print(' '.join(map(str,counts[1:])))

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
friend = [[] for _ in range(N+1)]
block = [[] for _ in range(N+1)]

for i in range(M):
  A,B = map(int, input().split())
  friend[A].append(B)
  friend[B].append(A)

for i in range(K):
  C,D = map(int, input().split())
  block[C].append(D)
  block[D].append(C)
#print(friend)
#print(block)

import queue

for i in range(1,N+1):
  c = 0
  visited = [False]*(N+1)
  visited[i]=True
  q = queue.Queue()
  for f in friend[i]:
    q.put(f)
    visited[f] = True
  frifri = []
  while not q.empty():
    p = q.get()
    for f in friend[p]:
      if visited[f]==False:
        q.put(f)
        frifri.append(f)
        visited[f] = True 
  for g in frifri:
      if g not in block[i]:
        c += 1
  print(c,end=' ')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import queue


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    graph = [Node(i) for i in range(N+1)]  # 0番目の要素はインデックスを合わせるためのダミー
    for a, b in zip(A, B):
        graph[a].add_friend(b)
        graph[b].add_friend(a)

    for c, d in zip(C, D):
        graph[c].add_block(d)
        graph[d].add_block(c)

    ns = [0 for _ in range(N)]

    for i in range(1, len(graph)):
        q = queue.Queue()
        node = graph[i]
        passed = {i}
        fr_coho = []
        for fr in node.get_friends():
            passed.add(fr)
            for fr2 in graph[fr].get_friends():
                if not fr2 in passed and not fr2 in node.get_friends():
                    q.put(fr2)
        while not q.empty():
            fr = q.get(block=False)
            if not fr in passed:
                fr_coho.append(fr)
                passed.add(fr)
                for fr2 in graph[fr].get_friends():
                    if not fr2 in passed:
                        q.put(fr2)

        # print("val" + str(i))
        for f_c in fr_coho:
            # print(f_c)
            if not f_c in node.get_blocks():
                ns[i-1] += 1

    for i in range(len(ns)):
        if i == N - 1:
            print(ns[i])
        else:
            print(str(ns[i]) + " ", end="")


class Node:
    def __init__(self, val):
        self.val = val
        self.friends = []
        self.blocks = []

    def add_friend(self, friend):
        self.friends.append(friend)

    def add_block(self, block):
        self.blocks.append(block)
    
    def get_friends(self):
        return self.friends

    def get_blocks(self):
        return self.blocks

# 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
import queue


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    graph = [Node(i) for i in range(N+1)]  # 0番目の要素はインデックスを合わせるためのダミー
    for a, b in zip(A, B):
        graph[a].add_friend(b)
        graph[b].add_friend(a)

    for c, d in zip(C, D):
        graph[c].add_block(d)
        graph[d].add_block(c)

    ns = [0 for _ in range(N)]

    for i in range(1, len(graph)):
        q = queue.Queue()
        node = graph[i]
        passed = [i]
        fr_coho = []
        for fr in node.get_friends():
            passed.append(fr)
            for fr2 in graph[fr].get_friends():
                if not fr2 in passed and not fr2 in node.get_friends():
                    q.put(fr2)
        while not q.empty():
            fr = q.get(block=False)
            if not fr in passed:
                fr_coho.append(fr)
                passed.append(fr)
                for fr2 in graph[fr].get_friends():
                    if not fr2 in passed:
                        q.put(fr2)

        # print("val" + str(i))
        for f_c in fr_coho:
            # print(f_c)
            if not f_c in node.get_blocks():
                ns[i-1] += 1

    for i in range(len(ns)):
        if i == N - 1:
            print(ns[i])
        else:
            print(str(ns[i]) + " ", end="")


class Node:
    def __init__(self, val):
        self.val = val
        self.friends = []
        self.blocks = []

    def add_friend(self, friend):
        self.friends.append(friend)

    def add_block(self, block):
        self.blocks.append(block)
    
    def get_friends(self):
        return self.friends

    def get_blocks(self):
        return self.blocks

# 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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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


class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        self.c = None

    def find(self, x):
        if self.p[x] < 0:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

    def count_member(self, x):
        return -self.p[self.find(x)]


uf = UnionFind(n)

for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    FRIENDS[a][b] = FRIENDS[b][a] = 1
    uf.union(a, b)

cd = [list(map(lambda x: int(x)-1, input().split())) for _ in range(k)]

ans = []

for i in range(n):
    c_friends = sum(FRIENDS[i])
    c_member = uf.count_member(i)
    ans.append(c_member - c_friends - 1)

for c, d in cd:
    if uf.find(c) == uf.find(d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m, k = map(int, input().split())
FRIENDS = [[0]*n for _ in range(n)]
BLOCKS = [[0]*n for _ in range(n)]


class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        self.c = None

    def find(self, x):
        if self.p[x] < 0:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

    def count_member(self, x):
        return -self.p[self.find(x)]


uf = UnionFind(n)

for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    FRIENDS[a][b] = FRIENDS[b][a] = 1
    uf.union(a, b)


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


ans = []


for i in range(n):
    c_friends = sum(FRIENDS[i])
    blocks = BLOCKS[i]
    c_member = uf.count_member(i)
    c_blocks = 0
    for j, b in enumerate(blocks):
        if b:
            if uf.find(i) == uf.find(j):
                c_blocks += 1
    ans.append(c_member - 1 - c_friends - c_blocks)

print(*ans)

Submission status: Time Limit Exceeded

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

friends = [[] for _ in range(n+1)]
blocks = [[] for _ in range(n+1)]

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

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

groups = []
nseen = {i for i in range(1, n+1)}
while len(nseen)>0:
    stack = [nseen.pop()]
    tmp = set()
    while len(stack)>0:
        node = stack.pop()
        tmp.add(node)
        for c_node in friends[node]:
            if c_node not in nseen:
                continue
            stack.append(c_node)
            nseen.remove(c_node)
    groups.append(tmp)

for i in range(1, n+1):
    for j in groups:
        if i in j:
            print(len(j - set(friends[i]) - set(blocks[i]))-1, end=' ')
            break

Submission status: Time Limit Exceeded

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

friends = [[] for _ in range(n+1)]
blocks = [[] for _ in range(n+1)]

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

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

groups = []
seen = [False]*(n+1)
while True:
    for i in range(1, n+1):
        if not seen[i]:
            stack = [i]
            break
    else:
        break
    tmp = set()
    while len(stack)>0:
        node = stack.pop()
        tmp.add(node)
        seen[node] = True
        for c_node in friends[node]:
            if seen[c_node]:
                continue
            stack.append(c_node)
    groups.append(tmp)


for i in range(1, n+1):
    for j in groups:
        if i in j:
            print(len(j - set(friends[i]) - set(blocks[i]))-1, end=' ')
            break

Submission status: Time Limit Exceeded

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

friends = []
blocks = []
groups = []
fs = [[] for _ in range(n+1)]
bs = [[] for _ in range(n+1)]

for _ in range(m):
    friends.append(tuple(map(int, input().split())))
for _ in range(k):
    blocks.append(tuple(map(int, input().split())))

for i, j in friends:
    fs[i].append(j)
    fs[j].append(i)

for i, j in blocks:
    bs[i].append(j)
    bs[j].append(i)

seen = [False]*(n+1)
while True:
    for i in range(1, n+1):
        if not seen[i]:
            stack = [i]
            break
    else:
        break
    tmp = set()
    while len(stack)>0:
        node = stack.pop()
        tmp.add(node)
        seen[node] = True
        for c_node in fs[node]:
            if seen[c_node]:
                continue
            stack.append(c_node)
    groups.append(tmp)


for i in range(1, n+1):
    for j in groups:
        if i in j:
            print(len(j - set(fs[i]) - set(bs[i]))-1, end=' ')
            break

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import bisect
n,m,k=map(int,input().split())
F=defaultdict(set)
B=defaultdict(set)
for i in range(m):
   a,b=map(int,input().split())
   F[a].add(b)
   F[b].add(a)
for i in range(k):
   c,d=map(int,input().split())
   B[c].add(d)
   B[d].add(c)

ans=[0]*n
for i in F:
   V=set()
   for j in F[i]:
      que=deque([j])
      while que:
         s=que.pop()
         if s not in V:
            V.add(s)
            for k in F[s]:
               que.append(k)
   for j in B[i]:
      if j in V:
         V.remove(j)
   ans[i-1]=len(V)-len(F[i])-1
   
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
n,m,k=map(int,input().split())
F=defaultdict(set)
B=defaultdict(set)
for i in range(m):
   a,b=map(int,input().split())
   F[a].add(b)
   F[b].add(a)
for i in range(k):
   c,d=map(int,input().split())
   B[c].add(d)
   B[d].add(c)

ans=[0]*n
for i in F:
   V=set()
   for j in F[i]:
      que=deque([j])
      while que:
         s=que.pop()
         if s not in V:
            V.add(s)
            for k in F[s]:
               que.append(k)
   for j in B[i]:
      if j in V:
         V.remove(j)
   ans[i-1]=len(V)-len(F[i])-1
   
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
n,m,k=map(int,input().split())
F=defaultdict(set)
B=defaultdict(set)
for i in range(m):
   a,b=map(int,input().split())
   F[a].add(b)
   F[b].add(a)
for i in range(k):
   c,d=map(int,input().split())
   B[c].add(d)
   B[d].add(c)

ans=[0]*n
for i in F:
   V=[]
   for j in F[i]:
      que=deque([j])
      while que:
         s=que.pop()
         if s not in V:
            V.append(s)
            for k in F[s]:
               que.append(k)
   for j in B[i]:
      if j in V:
         V.remove(j)
   ans[i-1]=len(V)-len(F[i])-1
   
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def dfs(cur_node, candidates, visited, level, cnt):

  while len(candidates) > 0:
    node, level = candidates.pop(0)

    if visited[node]: continue
    visited[node] = True

    if level > 0: cnt += 1

    for n in adj_list[node][FRIEND]:
      if n in adj_list[cur_node][BLOCK]:
        candidates.append((n, 0))
      if visited[n] == False:
        candidates.append((n, level+1))

  return cnt

# -----------------------------------------

FRIEND, BLOCK = 0, 1

N, F, B = list(map(int, input().split()))
adj_list = defaultdict(dict)
for i in range(1, N+1):
  adj_list[i][0] = set()
  adj_list[i][1] = set()

for _ in range(F):
  u, v = list(map(int, input().split()))
  adj_list[u][FRIEND].add(v)
  adj_list[v][FRIEND].add(u)

for _ in range(B):
  u, v = list(map(int, input().split()))
  adj_list[u][BLOCK].add(v)
  adj_list[v][BLOCK].add(u)

ans = []

for i in range(1, N+1):
  visited = [False] * (N+1)
  visited[i] = True
  candidates = []
  for node in adj_list[i][FRIEND]:
    # if status == FRIEND:
    # node, level
    candidates.append((node, 0))

  cnt = 0
  cnt = dfs(i, candidates, visited, 0, 0)
  ans.append(cnt)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [i for i in range(n + 1)]
        # rank
        self.rank = [0] * (n + 1)

    def find(self, x):
        # 根の番号を返す(所属する集合を確認する)
        # ここの再帰をDFSで実装して高速化できるか試す
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def check(self, x, y):
        # x,yが同じ集合に属するかどうか調べる
        return self.find(x) == self.find(y)


    def size(self,x):
        # 集合のサイズを調べる
        return self.par.count(self.find(x))

    def union(self, vx, vy):
        # 根を探す
        x = self.find(vx)
        y = self.find(vy)
        # rankの小さいものを大きいほうにくっつける
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.find(vx)
        else:
            self.par[y] = x
            self.find(vy)
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
                
import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
uf=UnionFind(n)
out=[[] for i in range(n+1)]

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

for i in range(k):
    c,d=map(int,input().split())
    if uf.check(c,d):
        out[c].append(d)
        out[d].append(c)
'''
print(out)
print(uf.par)
'''
for i in range(1,n+1):
    ans=uf.size(i)-1-len(out[i])
    print(ans,end=' ')

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [i for i in range(n + 1)]
        # rank
        self.rank = [0] * (n + 1)

    def find(self, x):
        # 根の番号を返す(所属する集合を確認する)
        # ここの再帰をDFSで実装して高速化できるか試す
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def check(self, x, y):
        # x,yが同じ集合に属するかどうか調べる
        return self.find(x) == self.find(y)


    def size(self,x):
        # 集合のサイズを調べる
        return self.par.count(self.find(x))

    def union(self, vx, vy):
        # 根を探す
        x = self.find(vx)
        y = self.find(vy)
        # rankの小さいものを大きいほうにくっつける
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.find(vx)
        else:
            self.par[y] = x
            self.find(vy)
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

n,m,k=map(int,input().split())
uf=UnionFind(n)
out=[[] for i in range(n+1)]

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

for i in range(k):
    c,d=map(int,input().split())
    if uf.check(c,d):
        out[c].append(d)
        out[d].append(c)
'''
print(out)
print(uf.par)
'''
for i in range(1,n+1):
    ans=uf.size(i)-1-len(out[i])
    print(ans,end=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
N, M, K = map(int, input().split())
H = [[] for i in range(N + 1)]
count = [0] * (N)

# 友達マップ
for i in range(M):
  A, B = map(int, input().split())
  H[A].append(B)
  H[B].append(A)
  
# ブロックマップ
for i in range(K):
  C, D = map(int, input().split())
  H[C].append(-D)
  H[D].append(-C)

# 友達候補探索
def get_friend(parent, target):
  if target in checked or target == parent:
    return
  checked.append(target)
  
  for s in H[target]:
    if s > 0 and (s == parent or s in counted or s in H[parent] or -s in H[parent]) == False:
      count[parent - 1] += 1
      counted.append(s)
    if s > 0 and (s == parent or s in checked) == False:
      get_friend(parent, s)

for i in range(1, N + 1):
  checked = []
  counted = []
  for j in H[i]:
    if j > 0:
      get_friend(i, j)

print (str(count).replace(',', '').replace('[', '').replace(']', ''))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, K = MAP()
friend = [LIST() for _ in range(M)]
block = [LIST() for _ in range(K)]

d = [[INF]*N for _ in range(N)]

for i in range(N):
    d[i][i] = 0

for x1, x2 in friend:
    d[x1 - 1][x2 - 1] = 1
    d[x2 - 1][x1 - 1] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])


for x1, x2 in block:
    d[x1 - 1][x2 - 1] = 0
    d[x2 - 1][x1 - 1] = 0

for i in range(N):
	sug = 0
	for j in range(len(d[i])):
		if d[i][j] > 1 and d[i][j] != INF:
			sug += 1
	print(sug, end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M, K = MAP()
A = [LIST() for i in range(M)]
C = [LIST() for i in range(K)]

tree = UnionFind(N)
block = defaultdict(list)
friend = defaultdict(list)

for a, b in A:
    tree.union(a-1, b-1)
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)

for c, d in C:
    block[c-1].append(d-1)
    block[d-1].append(c-1)

for i in range(N):
    # print("i:", i)
    # print(block[i], friend[i])
    # print(set(block[i]) | set(friend[i]))
    # print("tree_members:", tree.members(i))
    # ans = tree.size(i) - len(set(block[i]) | set(friend[i])) - 1
    ans = set(tree.members(i)) - (set(block[i]) | set(friend[i]))
    # print(ans)
    ans = len(ans) - 1
    print(ans, end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
N,M,K=map(int,input().split())

class UnionFind(): 
  def __init__(self,n):
    self.parent={}
    for i in range(n):
      self.parent[i]=[i]
      
  def find_parent(self,x):
    import sys
    parent=self.parent
    for key in parent.keys():
      if x in parent[key]:
        return key
        sys.exit()
        
  def union(self,x,y):
    parent=self.parent
    x_par,y_par=self.find_parent(x),self.find_parent(y)
    if x_par==y_par:
      pass
    else:
      if len(parent[x_par])<len(parent[y_par]):
        parent[y_par]+=parent[x_par]
        parent.pop(x_par)
      else:
        parent[x_par]+=parent[y_par]
        parent.pop(y_par)
    self.parent=parent
    return None

  def par_size(self):
    return self.parent
  
uf=UnionFind(N)

good=defaultdict(list)
bad=defaultdict(list)

for i in range(M):
  x,y=map(int,input().split())
  x-=1
  y-=1
  uf.union(x,y)
  good[x].append(y)
  good[y].append(x)
  
for i in range(K):
  x,y=map(int,input().split())
  x-=1
  y-=1
  bad[x].append(y)
  bad[y].append(x)
  
parent=uf.par_size()
ans=''
for i in range(N):
  par=uf.find_parent(i)
  s=len(parent[par])
  cnt=0
  for j in good[i]:
    par_j=uf.find_parent(j)
    if par==par_j:
      cnt+=1
  for j in bad[i]:
    par_j=uf.find_parent(j)
    if par==par_j:
      cnt+=1
  ans+=' '+str(s-cnt-1)
print(ans)