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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M,K = inputIL()

friend = [[] for _ in range(N)]
for _ in range(M):
  a,b = inputIL()
  friend[a-1].append(b-1)
  friend[b-1].append(a-1)
  
block = [[] for _ in range(N)]
for _ in range(K):
  a,b = inputIL()
  block[a-1].append(b-1)
  block[b-1].append(a-1)

  
cluster = [None for i in range(N)]
count = []

Q = list(range(N))
n = -1
while Q:
  n += 1
  q = deque([Q.pop()])
  cluster[q[0]] = n
  c = 1
  while q:
    i = q.popleft()
    for j in friend[i]:
      if cluster[j] == None:
        cluster[j] = n
        c += 1
        Q.remove(j)
        q.append(j)
  count.append(c)

ans = []

for i in range(N):
  a = count[cluster[i]]
  for j in friend[i]:
    if cluster[i]==cluster[j]:
      a -= 1
  for j in block[i]:
    if cluster[i]==cluster[j]:
      a -= 1
  ans.append(str(a-1))

print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def dfs(start, graph, target):
    dq = deque(list(graph[start]))
    searched = []

    while dq:
        pointer = dq.pop()
        
        if not pointer in searched:
            searched.append(pointer)

            if pointer == target:
                return True

            dq += list(graph[pointer])

    return False

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

# members = set([i for i in range(1, n+1)])
f_graph =  {i : set() for i in range(1, n+1)}
b_graph =  {i : set() for i in range(1, n+1)}
a_graph =  {i : 0 for i in range(1, n+1)}

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

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

for member in range(1, n+1):
    other_members = set([i for i in range(member, n+1)]) - f_graph[member] - b_graph[member] - {member}

    for target in other_members:
       if dfs(member, f_graph, target):
            a_graph[member] += 1
            a_graph[target] += 1

print(" ".join(map(str, a_graph.values())))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def dfs(start, graph, target):
    dq = deque([start])
    searched = []

    while dq:
        pointer = dq.pop()
        
        if not pointer in searched:
            searched.append(pointer)

            if pointer == target:
                return True

            dq += list(graph[pointer])

    return False

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

members = set([i for i in range(1, n+1)])
f_graph =  {i : set() for i in range(1, n+1)}
b_graph =  {i : set() for i in range(1, n+1)}
a_graph =  {i : set() for i in range(1, n+1)}

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

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

for member in range(1, n+1):
    other_members = members - f_graph[member] - b_graph[member] - {member}

    for target in other_members:
        if member in a_graph[target]:
            continue

        if dfs(member, f_graph, target):
            a_graph[member].add(target)
            a_graph[target].add(member)




for v in a_graph.values():
    print(len(v), end=" ")

Submission status: Time Limit Exceeded

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

n,m,k=map(int,input().split())
fr=[0 for _ in range(n)]
frl=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    fr[a-1]=fr[a-1]+1
    fr[b-1]=fr[b-1]+1
    frl[a-1].append(b)
    frl[b-1].append(a)

treelist=[]
hitobito=set()

def saiki(c):
    global treelist
    global hitobito
    global frl
    global bll
    global tmpset

    if frl[c-1] == []:
        hitobito.add(c)
        tmpset.add(c)
    
    for tsugi in frl[c-1]:
        if not tsugi in hitobito:
            hitobito.add(tsugi)
            tmpset.add(tsugi)
            saiki(tsugi)

for i in range(n):
    tmpset=set()
    saiki(i+1)
    if not tmpset == set():
        treelist.append(tmpset)


bll=[[] for i in range(n)]

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


output=[]
for i in range(n):
    for tree in treelist:
        if i+1 in tree:
            tmpsum=0
            for aaa in frl[i]:
                if aaa in tree:
                    tmpsum+=1
            for bbb in bll[i]:
                if bbb in tree:
                    tmpsum+=1 
            output.extend([str(len(tree)-tmpsum-1)," "])

print("".join(output))

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
INF = 10**9

class UnionFind():
    def __init__(self, n):
        self.n = n
        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

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    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()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


union_find = UnionFind(N)
friend_mat = [[None for _ in range(N)] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friend_mat[a][b] = True
    friend_mat[b][a] = True
    union_find.union(a, b)

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

ans_list = [0]*N
for i in range(N):
    for j in range(i+1, N):
        if friend_mat[i][j] is None and union_find.same(i, j):
            ans_list[i] += 1
            ans_list[j] += 1
print(*ans_list)

Submission status: Time Limit Exceeded

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

user=[0 for i in range(N+1)]
graph_ab=[[] for i in range(N+1)]
graph_cd=[[] for i in range(N+1)]
visit_list=[[] for i in range(N+1)]

for i in range(M):
    a,b=AB[i]
    graph_ab[a].append(b)
    graph_ab[b].append(a)

for j in range(1,N+1):
    stack=deque([j])
    visited=[None for i in range(N+1)]
    visited[j]='rd'
    while stack:
        x=stack.popleft()
        for i in graph_ab[x]:
            if visited[i] is None:
                visited[i]='rd'
                stack.append(i)
    visit_list[j]=visited
    
for i in range(K):
    c,d=CD[i]
    if visit_list[c][d]=='rd':
        graph_cd[c].append(d)
        graph_cd[d].append(c)

for i in range(1,N+1):
    user[i]=Counter(visit_list[i])['rd']-len(graph_ab[i])-len(graph_cd[i])-1

del user[0]
print(*user)

Submission status: Time Limit Exceeded

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

user=[0 for i in range(N+1)]
graph_ab=[[] for i in range(N+1)]
graph_cd=[[] for i in range(N+1)]
visit_list=[[] for i in range(N+1)]
for i in range(M):
    a,b=AB[i]
    graph_ab[a].append(b)
    graph_ab[b].append(a)

for j in range(1,N+1):
    stack=deque([j])
    visited=[-1 for i in range(N+1)]
    visited[j]=0
    while stack:
        x=stack.popleft()
        for i in graph_ab[x]:
            if visited[i]<0:
                visited[i]=1
                stack.append(i)
    visit_list[j]=visited
    
for i in range(K):
    c,d=CD[i]
    if visit_list[c][d]==1:
        graph_cd[c].append(d)
        graph_cd[d].append(c)

for i in range(1,N+1):
    user[i]=visit_list[i].count(1)-len(graph_ab[i])-len(graph_cd[i])

del user[0]
print(*user)

Submission status: Time Limit Exceeded

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

user=[0 for i in range(N+1)]
graph_ab=[[] for i in range(N+1)]
graph_cd=[[] for i in range(N+1)]
visit_list=[[] for i in range(N+1)]
for i in range(M):
    a,b=AB[i]
    graph_ab[a].append(b)
    graph_ab[b].append(a)
for i in range(K):
    c,d=CD[i]
    graph_cd[c].append(d)
    graph_cd[d].append(c)

for j in range(1,N+1):
    stack=deque([j])
    visited=[-1 for i in range(N+1)]
    visited[j]=0
    while stack:
        x=stack.popleft()
        for i in graph_ab[x]:
            if visited[i]<0:
                visited[i]=1
                stack.append(i)
    visit_list[j]=visited
for i in range(1,N+1):
    user[i]=visit_list[i].count(1)-len(graph_ab[i])
for i,value in enumerate(graph_cd):
    for j in value:
        if visit_list[i][j]==1:
            user[j]-=1
#     for i in range(j,N+1):
#         if visited[i]==1 and (i not in graph_ab[j]) and (i not in graph_cd[j]):
#             user[j]+=1
#             user[i]+=1
del user[0]
print(*user)

Submission status: Time Limit Exceeded

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

user=[0 for i in range(N+1)]
graph_ab=[[] for i in range(N+1)]
graph_cd=[[] for i in range(N+1)]
for i in range(M):
    a,b=AB[i]
    graph_ab[a].append(b)
    graph_ab[b].append(a)
for i in range(K):
    c,d=CD[i]
    graph_cd[c].append(d)
    graph_cd[d].append(c)
    
for j in range(1,N+1):
    stack=deque([j])
    visited=[-1 for i in range(N+1)]
    visited[j]=0
    while stack:
        x=stack.popleft()
        for i in graph_ab[x]:
            if visited[i]<0:
                visited[i]=1
                stack.append(i)
                
    for i in range(j,N+1):
        if visited[i]==1 and (i not in graph_ab[j]) and (i not in graph_cd[j]):
            user[j]+=1
            user[i]+=1
del user[0]
print(*user)

Submission status: Time Limit Exceeded

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

user=[0 for i in range(N+1)]
graph_ab=[[] for i in range(N+1)]
graph_cd=[[] for i in range(N+1)]
for i in range(M):
    a,b=AB[i]
    graph_ab[a].append(b)
    graph_ab[b].append(a)
for i in range(K):
    c,d=CD[i]
    graph_cd[c].append(d)
    graph_cd[d].append(c)
    
for j in range(1,N+1):
    stack=deque([j])
    visited=[-1 for i in range(N+1)]
    visited[j]=0
    while stack:
        x=stack.popleft()
        for i in graph_ab[x]:
            if visited[i]<0:
                visited[i]=1
                stack.append(i)
                
    for i in range(1,N+1):
        if visited[i]==1 and (i not in graph_ab[j]) and (i not in graph_cd[j]):
            user[j]+=1
del user[0]
print(*user)

Submission status: Time Limit Exceeded

Solution code:
N,M,K=list(map(int,input().split()))
AB=[list(map(int,input().split())) for i in range(M)]
CD=[list(map(int,input().split())) for i in range(K)]

user=[0 for i in range(N+1)]
graph_ab=[[] for i in range(N+1)]
graph_cd=[[] for i in range(N+1)]
for i in range(M):
    a,b=AB[i]
    graph_ab[a].append(b)
    graph_ab[b].append(a)
for i in range(K):
    c,d=CD[i]
    graph_cd[c].append(d)
    graph_cd[d].append(c)
for j in range(1,N+1):
    stack=[j]
    visited=[-1 for i in range(N+1)]
    visited[j]=0
    while stack:
        x=stack.pop(0)
        for i in graph_ab[x]:
            if visited[i]<0:
                visited[i]=1
                stack.append(i)
                
    for i in range(1,N+1):
        if visited[i]==1 and (i not in graph_ab[j]) and (i not in graph_cd[j]):
            user[j]+=1
del user[0]
print(*user)

Submission status: Time Limit Exceeded

Solution code:

from sys import setrecursionlimit 
setrecursionlimit(10**6)

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

fr = [set() for _ in range(n)]
bl = [set() for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    fr[a-1].add(b-1)
    fr[b-1].add(a-1)
    
for i in range(k):
    c ,d = map(int, input().split())
    bl[c-1].add(d-1)
    bl[d-1].add(c-1)
    

def connectedcomponents():
    visited = []
    cc = []
    for i in range(n):
        visited.append(False)
    for v in range(n):
        if visited[v] == False:
            temp = set()
            cc.append(dfs(fr,v,temp,visited))
    return cc
            

def dfs(fr, v, temp, visited):
    visited[v] = True
    temp.add(v)
    for i in fr[v]:
        if visited[i] == False:
            temp = dfs(fr, i, temp, visited)
    return temp

cc = connectedcomponents()

ans = []
for i in range(n):
    for component in cc:
        if i in component:
            aa = len(component) - len(component & fr[i]) - len(component & bl[i]) - 1
            ans.append(aa)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit 
setrecursionlimit(10**6)

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

fr = [set() for _ in range(n)]
bl = [set() for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    fr[a-1].add(b-1)
    fr[b-1].add(a-1)
    
for i in range(k):
    c ,d = map(int, input().split())
    bl[c-1].add(d-1)
    bl[d-1].add(c-1)
    

def connectedcomponents():
    visited = []
    cc = []
    for i in range(n):
        visited.append(False)
    for v in range(n):
        if visited[v] == False:
            temp = set()
            cc.append(dfs(fr,v,temp,visited))
    return cc
            

def dfs(fr, v, temp, visited):
    visited[v] = True
    temp.add(v)
    for i in fr[v]:
        if visited[i] == False:
            temp = dfs(fr, i, temp, visited)
    return temp

cc = connectedcomponents()

ans = []
for i in range(n):
    for component in cc:
        if i in component:
            aa = len(component) - len(component & fr[i]) - len(component & bl[i]) - 1
            ans.append(aa)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
CD = [tuple(map(int, input().split())) for _ in range(K)]


G = [[False]*(N+1) for _ in range(N+1)]   # 1-indexed
for A, B in AB:
    G[A][B] = True
    G[B][A] = True
for C, D in CD:
    G[C][D] = True
    G[D][C] = True


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


uf = UnionFind(N+1)

for a, b in AB:
    uf.Unite(a, b)

res = []
for i in range(1, N+1):
    ans = uf.Count(i)-1
    for x in range(1, N+1):
        if uf.isSameGroup(i, x) and G[i][x] is True:
            ans -= 1
    res.append(ans)
print(*res)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        self.friend = [[] for _ in range(n)]
        self.bad = [[] for _ in range(n)]
        
    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        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

    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    

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

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

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

ans_list = []
for i in range(n):
    ans = len(U.friend[i]) * (-1)
    for j in range(n):
        if i != j:
            if U.same_check(i, j):
                if j not in U.bad[i]:
                    ans += 1 
    ans_list.append(str(ans))

print(' '.join(ans_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')


class UnionFind():
    def __init__(self, n):
        self.n = n
        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

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    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()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def solve():
    n, m, k = MI()
    uf = UnionFind(n)

    friends = [0] * n
    for i in range(m):
        a, b = MI1()
        uf.union(a, b)
        friends[a] += 1
        friends[b] += 1
    # print(uf.__str__())
    # print(friends)

    blocks = [[0] * n for _ in range(n)]

    for i in range(k):
        c, d = MI1()
        blocks[c][d] += 1
        blocks[d][c] += 1

    # print(blocks)

    ans = [0] * n

    for i in range(n):
        # print(i, uf.size(i))
        block = 0
        # print('  bb', blocks[i])
        for idx, bb in enumerate(blocks[i]):
            if bb == 1 and uf.same(i, idx):
                # print(idx, bb, uf.find(idx), uf.same(idx, i))
                block += 1
        ans[i] = uf.size(i) - 1 - block - friends[i]
        # print(ans)

    print(' '.join(list(map(str, ans))))

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
import copy

N, M, K = map(int, input().split())
friend = [deque() for _ in range(N)]
status = [-1]*N
numList = [0]*N

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

def DFS(graph, v, num):
    global numList
    cnt = 1
    stack = [v]
    status[v] = num
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if status[w] == -1:
                status[w] = num
                cnt += 1
                stack.append(w) 
        else:
            stack.pop() 
    numList[num] = cnt

cnt = 0
for i in range(N):
    if status[i] == -1:
        DFS(copy.deepcopy(friend), i, cnt)
        cnt += 1

ans = [0]*N
for i in range(N):
    ans[i] = numList[status[i]] - 1 - len(friend[i])
for i in range(K):
    a, b = map(int, input().split())
    if status[a-1] == status[b-1]:
        ans[a-1] -= 1
        ans[b-1] -= 1
print(" ".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds



def root(x,par):
    px=par[x]
    while px!=x:
        x=px
        px=par[x]
    return px
def union(x,y,par):
    rx,ry=root(x,par),root(y,par)
    if rx!=ry:
        par[ry]=rx 


def main():
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N,M,K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    par=[i for i in range(N)]
    fl=[[] for _ in range(N)]
    counts=[0]*N
    for _ in range(M):
        a, b= map(int,input().split())
        counts[a-1]-=1
        counts[b-1]-=1
        union(a-1,b-1,par)
        
    #bl=tree_init(K)
    roots=[0]*N
    br=[root(i,par) for i in range(N)]
    
    for p in br:
        roots[p]+=1
    for i in range(N):
        r=br[i]
        count=roots[r]-1
        counts[i]+=count
    
    for _ in range(K):
        a, b= map(int,input().split())
        if br[a-1]==br[b-1]:
            counts[a-1]-=1
            counts[b-1]-=1

    print(*counts)
    



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

def tree_init(N):
    edgelist = [[] for _ in range(N)]
    for a, b in [map(int, input().split()) for i in range(N-1)]:#木じゃない場合N-1をNに変える
        edgelist[a-1].append(b-1)#ノードの番号が0から始まる場合-1を消す
        edgelist[b-1].append(a-1)
    return edgelist


def root(x,par):
    px=par[x]
    while px!=x:
        x=px
        px=par[x]
    return px
def union(x,y,par):
    rx,ry=root(x,par),root(y,par)
    if rx!=ry:
        par[ry]=rx 


def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N,M,K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    par=[i for i in range(N)]
    fl=[[] for _ in range(N)]
    for _ in range(M):
        a, b= map(int,input().split())
        fl[a-1].append(b-1)#ノードの番号が0から始まる場合-1を消す
        fl[b-1].append(a-1)
        union(a-1,b-1,par)
    #bl=tree_init(K)
    roots=[0]*N
    br=[0]*N
    counts=[0]*N
    for i in range(N):
        p=root(i,par)
        br[i]=p
        roots[p]+=1
    for i in range(N):
        r=br[i]
        count=roots[r]-1
        count-=len(fl[i])
        counts[i]=count
    
    for _ in range(K):
        a, b= map(int,input().split())
        if br[a-1]==br[b-1]:
            counts[a-1]-=1
            counts[b-1]-=1

    print(*counts)
    



if __name__ == "__main__":
    main()