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 queue
n,m,k=map(int,input().split())
root=[[0]*n for i in range(n)]
for i in range(n):
    root[i][i]=2
#print(root)
for i in range(m):
    a,b=map(int,input().split())
   # print("berfot",root[a-1][b-1])
    root[a-1][b-1]=1
    root[b-1][a-1]=1
  #  print("after",root[a-1][b-1])
for i in range(k):
    a,b=map(int,input().split())
 #   print(a,b)
    root[a-1][b-1]=-float("inf")
    root[b-1][a-1]=-float("inf")
#print(root)
toVis=queue.Queue()
Visted=[]
OK={}
checkVis=[0 for i in range(n)]
checkVinit=checkVis
for i in range(n):
    checkVis=checkVinit
    Visted=[i]
    checkVis[i]=5


    if i in OK.keys():
        continue
    toVis=queue.Queue()
    
    for j in range(len(root[i])):
        nex=root[i][j]
       # if j not in Visted and nex==1:
        if checkVis[j]!=5 and nex==1:
            toVis.put(j)

    while toVis.empty()==False:
    
        now=toVis.get()
        #if now in Visted:
        if checkVis[now]==5:
            continue
     #   print("now :" ,now)
        Visted.append(now)
        checkVis[now]=5
        for j in range(len(root[now])):
            nex=root[now][j]
            #if nex==1 and j not in Visted:
            if nex==1 and checkVis[j]!=5:
      #          print("apend",nex)
                toVis.put(j)
   
    for j in range(len(Visted)):
        OK[Visted[j]]=Visted
#print(OK)
ans=[]
for i in range(n):
    num=0
    for value in OK[i]:
        if root[i][value]==0:
            num+=1
    ans.append(num)
print(" ".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import queue
n,m,k=map(int,input().split())
root=[[0]*n for i in range(n)]
for i in range(n):
    root[i][i]=2
#print(root)
for i in range(m):
    a,b=map(int,input().split())
   # print("berfot",root[a-1][b-1])
    root[a-1][b-1]=1
    root[b-1][a-1]=1
  #  print("after",root[a-1][b-1])
for i in range(k):
    a,b=map(int,input().split())
 #   print(a,b)
    root[a-1][b-1]=-float("inf")
    root[b-1][a-1]=-float("inf")
#print(root)
toVis=queue.Queue()
Visted=[]
OK={}

for i in range(n):
    Visted=[i]

    if i in OK.keys():
        continue
    toVis=queue.Queue()
    
    for j in range(len(root[i])):
        nex=root[i][j]
        if j not in Visted and nex==1:
            toVis.put(j)

    while toVis.empty()==False:
    
        now=toVis.get()
        if now in Visted:
            continue
     #   print("now :" ,now)
        Visted.append(now)
        for j in range(len(root[now])):
            nex=root[now][j]
            if nex==1 and j not in Visted:
      #          print("apend",nex)
                toVis.put(j)
   
    for j in range(len(Visted)):
        OK[Visted[j]]=Visted
#print(OK)
ans=[]
for i in range(n):
    num=0
    for value in OK[i]:
        if root[i][value]==0:
            num+=1
    ans.append(num)
print(" ".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    friend = {e: set() for e in range(n)}
    foe = {e: set() for e in range(n)}
    par = [-1] * n
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        friend[a].add(b)
        friend[b].add(a)
    for _ in range(k):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        foe[c].add(d)
        foe[d].add(c)
    roots = {e: set() for e in range(n)}
    for i2 in range(n):
        roots[find(i2)].add(i2)


    for i in range(n):
        print(len(set(roots[find(i)]) - friend[i] - foe[i]) - 1, end=' ')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    friend = {e: set() for e in range(n)}
    foe = {e: set() for e in range(n)}
    par = [-1] * n
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        friend[a].add(b)
        friend[b].add(a)
    for _ in range(k):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        foe[c].add(d)
        foe[d].add(c)

    for i in range(n):
        print(len(set(members(i)) - friend[i] - foe[i]) - 1, end=' ')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

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

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

    for i1 in range(n):
        member = members(i1)
        for m in member:
            g[i1][m] ^= 1

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

    for i in range(n):
        print(sum(g[i]) - 1, end=' ')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
n, m, k = map(int,input().split())
frnd = [[] for i in range(n+1)]
blck = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    frnd[a].append(b)
    frnd[b].append(a)

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

#グラフをグループ化するやつ
def grouping(n,arr):
    gr = []
    al = [-1 for i in range(n+1)]
    q = queue.Queue()
    for i in range(1,n+1):
        if al[i] == 0:
            continue
        else:
            gi = []
            q.put(i)
            al[i] = 0
            while not q.empty():
                qi = q.get()
                gi.append(qi)
                for ai in arr[qi]:
                    if al[ai] < 0:
                        q.put(ai)
                        al[ai] = 0
            gr.append(gi)
    return gr

fg = grouping(n,frnd)

gn = [0 for i in range(n+1)]
for i,g in enumerate(fg):
    for p in g:
        gn[p] = i

ans = [0 for i in range(n)]
for i in range(1,n+1):
    num = 0
    for pi in fg[gn[i]]:
        if pi == i or pi in frnd[i] or pi in blck[i]:
            continue
        else:
            num += 1
    ans[i-1] = num

print(" ".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys

from collections import deque
input = sys.stdin.buffer.readline
def main():
    n, m, k = map(int, input().split())
    friends = {k: set() for k in range(1, n + 1)}
    foe = {k: set() for k in range(1, n + 1)}
    for _ in range(m):
        a, b = map(int, input().split())
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = map(int, input().split())
        foe[a].add(b)
        foe[b].add(a)

    belong_group = [-1] * (n + 1)
    groups = {}
    stack = deque()
    group_num = 1
    nodes_seen = set()
    for i1 in range(1, n + 1):
        if i1 in nodes_seen or friends[i1] == []:
            continue
        else:
            belong_group[i1] = group_num
            groups[group_num] = set()
            groups[group_num].add(i1)
            nodes_seen.add(i1)
            stack += friends[i1]
            while stack:
                next_node = stack.popleft()
                if next_node in nodes_seen:
                    continue
                else:
                    nodes_seen.add(next_node)
                    belong_group[next_node] = group_num
                    groups[group_num].add(next_node)
                    stack += friends[next_node]
            group_num += 1
    for i2 in range(1, n + 1):
        r = max(len(groups[belong_group[i2]] - friends[i2] - foe[i2]) - 1, 0)
        print(r, end=' ')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    n, m, k = map(int, input().split())
    friends = {k: set() for k in range(1, n + 1)}
    foe = {k: set() for k in range(1, n + 1)}
    for _ in range(m):
        a, b = map(int, input().split())
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = map(int, input().split())
        foe[a].add(b)
        foe[b].add(a)

    belong_group = [-1] * (n + 1)
    groups = {}
    stack = deque()
    group_num = 1
    nodes_seen = set()
    for i1 in range(1, n + 1):
        if i1 in nodes_seen or friends[i1] == []:
            continue
        else:
            belong_group[i1] = group_num
            groups[group_num] = set()
            groups[group_num].add(i1)
            nodes_seen.add(i1)
            stack += friends[i1]
            while stack:
                next_node = stack.popleft()
                if next_node in nodes_seen:
                    continue
                else:
                    nodes_seen.add(next_node)
                    belong_group[next_node] = group_num
                    groups[group_num].add(next_node)
                    stack += friends[next_node]
            group_num += 1
    for i2 in range(1, n + 1):
        r = max(len(groups[belong_group[i2]] - friends[i2] - foe[i2]) - 1, 0)
        print(r, end=' ')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    n, m, k = map(int, input().split())
    friends = {k: set() for k in range(1, n + 1)}
    foe = {k: set() for k in range(1, n + 1)}
    for _ in range(m):
        a, b = map(int, input().split())
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = map(int, input().split())
        foe[a].add(b)
        foe[b].add(a)

    belong_group = [-1] * (n + 1)
    groups = {}
    stack = deque()
    group_num = 1
    for i1 in range(1, n + 1):
        if belong_group[i1] != -1 or friends[i1] == []:
            continue
        else:
            belong_group[i1] = group_num
            groups[group_num] = set()
            groups[group_num].add(i1)
            stack += friends[i1]
            while stack:
                next_node = stack.popleft()
                if belong_group[next_node] != -1:
                    continue
                else:
                    belong_group[next_node] = group_num
                    groups[group_num].add(next_node)
                    stack += friends[next_node]
            group_num += 1
    for i2 in range(1, n + 1):
        r = max(len(groups[belong_group[i2]] - friends[i2] - foe[i2]) - 1, 0)
        print(r, end=' ')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

from collections import defaultdict, deque
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left

import sys
# sys.setrecursionlimit(1000000)
# list(map(int, input().split()))
mod = 10 ** 9 + 7
# https://atcoder.jp/contests/abc141/tasks/abc141_d

# Nは人、Mは関係の数
N, M, K = getNM()
friend = [[] for i in range(N)]
for i in range(M):
    a, b = getNM()
    friend[a - 1].append(b - 1)
    friend[b - 1].append(a - 1)
blocked = [[] for i in range(N)]
for i in range(K):
    a, b = getNM()
    blocked[a - 1].append(b - 1)
    blocked[b - 1].append(a - 1)
def matcher(n):
    ignore = [0] * (N + 1)
    ignore[n] = 1
    pos = deque([n])
    setfriend = set(friend[n])
    setblocked = set(blocked[n])
    res = set()
    while len(pos) > 0:
        u = pos.popleft()
        for i in friend[u]:
            if ignore[i] > 0:
                continue
            ignore[i] = 1
            if not i in (setfriend | setblocked):
                res.add(i)
            pos.append(i)
    return len(res)
ans = []
for i in range(N):
    ans.append(matcher(i))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M,K=map(int,input().split())
F,B=[[] for _ in range(N)],[[] 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
  B[c].append(d)
  B[d].append(c)
#print(F,B)
C=[[] for _ in range(N)]
finished = []
for i,f in enumerate(F):
  if i in finished: continue
  store = deque([i])
  c = []
  while len(store)>0:
    s = store.popleft()
    if s in c:continue
    c.append(s)
    store.extend(F[s])
  finished.extend(c)
  for c2 in c:
    C[c2] = [v for v in c if v!=c2 and v not in F[c2] and v not in B[c2]]
#print(F,B,C)
print(' '.join([str(len(v)) for v in C]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M,K=map(int,input().split())
F,B=[[] for _ in range(N)],[[] 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
  B[c].append(d)
  B[d].append(c)
#print(F,B)
C=[[] for _ in range(N)]
for i,f in enumerate(F):
  store = deque([i])
  c = []
  while len(store)>0:
    s = store.popleft()
    if s in c:continue
    c.append(s)
    store.extend(F[s])
  c = [v for v in c if v != i and v not in f and v not in B[i]]
  C[i]=c
#print(F,B,C)
print(' '.join([str(len(v)) for v in C]))

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


class UnionFind:
    # 初期化
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        # 親要素のノード番号を格納する.初めは全て親ノード.
        # self.parent[x] == x の時，そのノードは根.
        self.parent = [i for i in range(n_nodes)]
        # 木の高さを格納する．
        self.rank = [1] * n_nodes
        # 自分と同じグループの要素数を格納．親要素を参照するようにする
        self.size = [1] * n_nodes

    # 検索. 根を返す.
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 一度調べた値は，根に繋ぎ直す.
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    # 併合.
    # 木の高さが低くなるように.
    # 親要素の書き換えは少ない方がいい
    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.parent[y] = x
            self.size[x] += self.size[y]
        else:
            self.parent[x] = y
            self.size[y] += self.size[x]
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

    # 同一グループに所属する要素数を返す
    def get_size(self, x):
        return self.size[self.find(x)]

    # 親要素のリストを返す
    def get_parent_list(self):
        return [i for i in range(self.n_nodes) if self.find(i) == i]

    # グループの数を返す
    def get_n_groups(self):
        return len(self.get_parent_list())

    # 同じグループに所属する要素の集合を返す
    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

    # 全ての根に対する，グループのメンバーを返す．
    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


MOD = 10 ** 9 + 7


def main():
    N, M, K = map(int, input().split())
    UF = UnionFind(N)
    friend = [0] * N
    block = [0] * N
    for _ in range(M):
        a, b = map(int, input().split())
        UF.unite(a - 1, b - 1)
        friend[a - 1] += 1
        friend[b - 1] += 1
    m = UF.get_members_dict()
    for _ in range(K):
        c, d = map(int, input().split())
        if d - 1 in m[UF.find(c - 1)]:
            block[c - 1] += 1
            block[d - 1] += 1
    answer = []
    for i in range(N):
        answer.append(UF.get_size(i) - friend[i] - block[i] - 1)
    print(*answer, sep=" ")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def main():
    n, m, k = map(int, stdin.readline().split())
    g = [[[False, False] for _ in range(n)] for _ in range(n)]

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        g[a - 1][b - 1][0] = True
        g[b - 1][a - 1][0] = True

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

    def dfs(v, seen):
        seen[v] = True

        for nv in range(n):
            if g[v][nv][0]:
                if seen[nv]:
                    continue
                dfs(nv, seen)

    ans = [0] * n
    for i in range(n):
        gi = g[i]
        seen = [False] * n
        dfs(i, seen)
        for j in range(n):
            if not(gi[j][0]) and not(gi[j][1]) and i != j and seen[j]:
                ans[i] += 1

    print(*ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def main():
    n, m, k = map(int, stdin.readline().split())
    g = [[[False, False] for _ in range(n)] for _ in range(n)]

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        g[a - 1][b - 1][0] = True
        g[b - 1][a - 1][0] = True

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

    def dfs(v, seen):
        seen[v] = True

        for nv in range(n):
            if g[v][nv][0]:
                if seen[nv]:
                    continue
                dfs(nv, seen)

    ans = [0] * n
    for i in range(n):
        seen = [False] * n
        dfs(i, seen)
        for j in range(n):
            if g[i][j][0] == False and g[i][j][1] == False and i != j and seen[j]:
                ans[i] += 1

    print(*ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def dfs(n, g, v, seen):
    seen[v] = True

    for nv in range(n):
        if g[v][nv][0]:
            if seen[nv]:
                continue
            dfs(n, g, nv, seen)


def main():
    n, m, k = map(int, stdin.readline().split())
    ab = [list(map(int, stdin.readline().split())) for _ in range(m)]
    cd = [list(map(int, stdin.readline().split())) for _ in range(k)]

    g = [[[False, False] for _ in range(n)] for _ in range(n)]

    for a, b in ab:
        g[a - 1][b - 1][0] = True
        g[b - 1][a - 1][0] = True

    for c, d in cd:
        g[c - 1][d - 1][1] = True
        g[d - 1][c - 1][1] = True

    ans = [0] * n
    for i in range(n):
        seen = [False] * n
        dfs(n, g, i, seen)
        for j in range(n):
            if g[i][j][0] == False and g[i][j][1] == False and i != j and seen[j]:
                ans[i] += 1

    print(*ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(0, n+1)}
sizes = {i:1 for i in range(0, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, u):
	while (parent[u] != u):
		u = parent[u]
	return u
	return parent[u]

for a,b in friendships:
	if a != b:
		pa,pb = f(parent, a), f(parent, b)
		
		adj[a].add(b)
		adj[b].add(a)

		if pa != pb:
			parent[pb] = pa
			sizes[pa] += sizes[pb]

for c,d in disses:
	pc,pd = f(parent, c), f(parent, d)
	if (pc == pd):
		hd[c] += 1
		hd[d] += 1
"""
hd[u] = k
u has k disses in its connected component
"""

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+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)]
friend_edges = []
for _ in range(M):
  a, b = inputIL()
  friend_edges.append((a-1, b-1))
for a, b in friend_edges:
  friend[a].append(b)
  friend[b].append(a)
  
block = [[] for _ in range(N)]
block_edges = []
for _ in range(K):
  a, b = inputIL()
  block_edges.append((a-1, b-1))
for a, b in block_edges:
  block[a].append(b)
  block[b].append(a)

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

Q = list(range(N))
n = -1
while Q:
  n += 1
  q = deque([Q.pop()])
  memo = [q[0]]
  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.append(j)
        memo.append(j)
  count.append(c)
  Q = list(set(Q)-set(memo))

ans = [count[cluster[i]]-1 for i in range(N)]

for a, b in friend_edges:
  if cluster[a]==cluster[b]:
    ans[a] -= 1
    ans[b] -= 1

for a, b in block_edges:
  if cluster[a]==cluster[b]:
    ans[a] -= 1
    ans[b] -= 1
  

print(*ans,sep=" ")

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)]
friend_edges = []
for _ in range(M):
  a, b = inputIL()
  friend_edges.append((a-1, b-1))
for a, b in friend_edges:
  friend[a].append(b)
  friend[b].append(a)
  
block = [[] for _ in range(N)]
block_edges = []
for _ in range(K):
  a, b = inputIL()
  block_edges.append((a-1, b-1))
for a, b in block_edges:
  block[a].append(b)
  block[b].append(a)

  
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 = [count[cluster[i]]-1 for i in range(N)]

for a, b in friend_edges:
  if cluster[a]==cluster[b]:
    ans[a] -= 1
    ans[b] -= 1

for a, b in block_edges:
  if cluster[a]==cluster[b]:
    ans[a] -= 1
    ans[b] -= 1
  

print(*ans,sep=" ")