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

tomodati=[[] for i in range(n+1)]

group=[0]*(n+1)

block=[0]*(n+1)

tansaku=[]

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

num=1

for i in range(1,n+1):
    if group[i]==0:
        tansaku.append(i)
        group[i]=num
    while len(tansaku)>0:
        for j in tomodati[tansaku[0]]:
            if group[j]==0:
                group[j]=num
                tansaku.append(j)
        tansaku.pop(0)
    num+=1

for i in range(k):
    c,d=map(int,input().split())
    if group[c]==group[d]:
        block[c]+=1
        block[d]+=1

ans=""

for i in range(1,n+1):
    ans+=str(group.count(group[i])-len(tomodati[i])-block[i]-1)+" "

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,M,K=map(int,input().split())

    G=[[] for i in range(N)]

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

    C=[]
    D=[]
    for i in range(K):
        c,d=map(int,input().split())
        C.append(c-1)
        D.append(d-1)
    trace=[-1 for i in range(N)]
    Group=[]

    for i in range(N):
        stack=[]
        if trace[i]==-1:
            trace[i]=0
            stack.append(i)
        Group_tmp=[]
        while len(stack)>0:
            index=stack.pop()
            Group_tmp.append(index)
            for j in G[index]:
                if trace[j]==-1:
                    trace[j]=0
                    stack.append(j)
        if len(Group_tmp)!=0:
            Group.append(Group_tmp)

    res=[0 for i in range(N)]
    GroupMarker=[-1 for i in range(N)]

    for i in range(len(Group)):
        for j in range(len(Group[i])):
            person=Group[i][j]
            GroupMarker[person]=i
            r=len(Group[i])-len(G[person])-1
            res[person]=r
    for i in range(K):
        if D[i] in Group[GroupMarker[C[i]]]:
            res[D[i]]-=1
            res[C[i]]-=1

    res=list(map(str,res))
    print(" ".join(res))

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k=map(int,input().split())
ka=[0]*(n+1)
ab=[set([]) for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    ab[a].add(b)
    ab[b].add(a)
cd=[set([]) for i in range(n+1)]
for i in range(k):
    c,d=map(int,input().split())
    cd[c].add(d)
    cd[d].add(c)

wk=deque()
wwk=deque()
hou=[0]*(n+1)
for i in range(1,n+1):
    if hou[i]==1:
        continue
    abw=ab[i]
    wk=deque(abw)
    jyo={i}|abw
    while wk:
        tgwk=wk.pop()
        for j in ab[tgwk]:
            if j not in jyo:
                wwk.append(j)
                jyo.add(j)
                hou[i]=1
                if j not in cd[i]:
                    ka[i]+=1
        if not wk:
            wk=wwk
            wwk=deque()
    print(ka[i],end=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k=map(int,input().split())
ka=[0]*(n+1)
ab=[set([]) for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    ab[a].add(b)
    ab[b].add(a)
cd=[set([]) for i in range(n+1)]
for i in range(k):
    c,d=map(int,input().split())
    cd[c].add(d)
    cd[d].add(c)

wk=deque()
wwk=deque()
hou=[0]*(n+1)
for i in range(1,n+1):
    if hou[i]==1:
        continue
    hou[i]=1
    abw=ab[i]
    wk=deque(abw)
    jyo={i}|abw
    while wk:
        tgwk=wk.pop()
        for j in ab[tgwk]:
            if j not in jyo:
                wwk.append(j)
                jyo.add(j)
                if j not in cd[i]:
                    ka[i]+=1
        if not wk:
            wk=wwk
            wwk=deque()
    print(ka[i],end=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k=map(int,input().split())
ka=[0]*(n+1)
ab=[set([]) for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    ab[a].add(b)
    ab[b].add(a)
cd=[set([]) for i in range(n+1)]
for i in range(k):
    c,d=map(int,input().split())
    cd[c].add(d)
    cd[d].add(c)

wk=deque()
wwk=deque()
for i in range(1,n+1):
    abw=ab[i]
    wk=deque(abw)
    jyo={i}|abw
    while wk:
        tgwk=wk.pop()
        for j in ab[tgwk]:
            if j not in jyo:
                wwk.append(j)
                jyo.add(j)
                if j not in cd[i]:
                    ka[i]+=1
        if not wk:
            wk=wwk
            wwk=deque()
    print(ka[i],end=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k=map(int,input().split())
ka=[0]*(n+1)
ab=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
cd=[[] for i in range(n+1)]
for i in range(k):
    c,d=map(int,input().split())
    cd[c].append(d)
    cd[d].append(c)

wk=deque()
wwk=deque()
for i in range(1,n+1):
    abw=ab[i]
    wk=deque(abw)
    jyo=[i]+abw
    while wk:
        tgwk=wk.pop()
        for j in ab[tgwk]:
            if j not in jyo:
                wwk.append(j)
                jyo.append(j)
                if j not in cd[i]:
                    ka[i]+=1
        if not wk:
            wk=wwk
            wwk=deque()
    print(ka[i],end=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k=map(int,input().split())
ka=[0]*(n+1)
ab=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
cd=[[] for i in range(n+1)]
for i in range(k):
    c,d=map(int,input().split())
    cd[c].append(d)
    cd[d].append(c)

wk=deque()
wwk=[]
for i in range(1,n+1):
    abw=ab[i]
    wk=deque(abw)
    jyo=[i]+abw
    while wk:
        tgwk=wk.pop()
        for j in ab[tgwk]:
            if j not in jyo:
                wwk.append(j)
                jyo.append(j)
                if j not in cd[i]:
                    ka[i]+=1
        if not wk:
            wk=deque(wwk)
            wwk=[]
    print(ka[i],end=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k=map(int,input().split())
ka=[0]*(n+1)
ab=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
cd=[[] for i in range(n+1)]
for i in range(k):
    c,d=map(int,input().split())
    cd[c].append(d)
    cd[d].append(c)

wk=deque()
wwk=[]
for i in range(1,n+1):
    wk=deque(ab[i])
    jyo=[i]+ab[i]
    while wk:
        tgwk=wk.pop()
        for j in ab[tgwk]:
            if j not in jyo:
                wwk.append(j)
                jyo.append(j)
                if j not in cd[i]:
                    ka[i]+=1
        if not wk:
            wk=deque(wwk)
            wwk=[]
for i in ka[1:]:
    print(i,end=' ')

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)

def resolve():
    N, M,K = map(int, input().split())
    frind = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x:int(x)-1, input().split())
        frind[a].append(b)
        frind[b].append(a)

    block = [[] for _ in range(N)]
    for _ in range(K):
        a, b = map(lambda x: int(x) - 1, input().split())
        block[a].append(b)
        block[b].append(a)


    D = {}
    parent = [-1]*N
    visited = [False]*N
    for root in range(N):
        if visited[root]:
            continue
        D[root] = set([root])
        stack = [root]
        while stack:
            n = stack.pop()
            visited[n] = True
            parent[n] = root
            for to in frind[n]:
                if visited[to]:
                    continue
                D[root].add(to)
                stack.append(to)

    ans = [0]*N
    for i in range(N):
        gr = D[parent[i]]
        tmp = len(gr)-len(frind[i]) - 1
        for bl in block[i]:
            if bl in gr:
                tmp -= 1
        ans[i] = tmp
    print(*ans)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

class UnionFind():
  def __init__(self, n):
    self.n = n                           # 要素数
    self.parents = [i for i in range(n)] # 要素の親
    self.rank = [0] * n                  # 木の深さ
    self.size = [1] * n                  # iを根とする集合の要素数

  def find(self, x):
    if self.parents[x] == x:
      return x
    else:
      # 経路圧縮
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]
    
  def union(self, x, y):
    root_x = self.find(x)
    root_y = self.find(y)
    
    if root_x != root_y:
      # 深さが小さい方を大きい方に併合する
      if self.rank[root_x] > self.rank[root_y]:
        self.parents[root_y] = root_x
        self.size[root_x] += self.size[root_y]
      else:
        self.parents[root_x] = root_y
        self.size[root_y] += self.size[root_x]
        if self.rank[root_x] == self.rank[root_y]:
          self.rank[root_y] += 1

N, M, K = map(int, input().split())
A = list()
B = list()
C = list()
D = list()
union_find = UnionFind(n=N)
direct_and_block_count = [0] * N
ans = ''
for i in range(M):
  a, b = map(int, input().split())
  A.append(a-1)
  B.append(b-1)
  union_find.union(a-1, b-1)
  direct_and_block_count[a-1] += 1
  direct_and_block_count[b-1] += 1
for i in range(K):
  c, d = map(int, input().split())
  C.append(c-1)
  D.append(d-1)
  if union_find.find(c-1) == union_find.find(d-1):
    # 同じ集合の場合
    direct_and_block_count[c-1] += 1
    direct_and_block_count[d-1] += 1
for i in range(N):
  # 直接の友達、ブロック、自分自身を除く
  ans += str(union_find.size[union_find.find(i)] - direct_and_block_count[i] - 1)
  if i != N-1:
     ans += ' '

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools


class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.par = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> None:
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


def resolve(in_):
    N, M, K = map(int, in_.readline().split())
    ab = tuple(tuple(map(int, line.split())) for line in itertools.islice(in_, M))
    cd = tuple(tuple(map(int, line.split())) for line in itertools.islice(in_, K))

    friends_tree = UnionFindTree(N + 1)
    friends = [set() for _ in range(N + 1)]
    blocks = [set() for _ in range(N + 1)]

    for a, b in ab:
        friends_tree.unite(a, b)
        friends[b].add(a)
        friends[a].add(b)
    for c, d in cd:
        blocks[c].add(d)
        blocks[d].add(c)
    # print(friends)
    # print(blocks)
    # print(friends_tree.par, friends_tree.rank)
    
    ans = [0] * (N + 1)
    for i, j in itertools.combinations(range(1, N + 1), 2):
        if i == j:
            continue
        if j in friends[i] or j in blocks[i]:
            continue
        if friends_tree.same(i, j):
            ans[i] += 1
            ans[j] += 1

    return ' '.join(map(str, ans[1:]))


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools


class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.par = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> None:
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


def resolve(in_):
    N, M, K = map(int, in_.readline().split())
    ab = tuple(tuple(map(int, line.split())) for line in itertools.islice(in_, M))
    cd = tuple(tuple(map(int, line.split())) for line in itertools.islice(in_, K))

    friends_tree = UnionFindTree(N + 1)
    friends = [set() for _ in range(N + 1)]
    blocks = [set() for _ in range(N + 1)]

    for a, b in ab:
        friends_tree.unite(a, b)
        friends[b].add(a)
        friends[a].add(b)
    for c, d in cd:
        blocks[c].add(d)
        blocks[d].add(c)
    # print(friends)
    # print(blocks)
    # print(friends_tree.par, friends_tree.rank)
    
    ans = [0] * (N + 1)
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if i == j:
                continue
            if j in friends[i] or j in blocks[i]:
                continue
            if friends_tree.same(i, j):
                ans[i] += 1

    return ' '.join(map(str, ans[1:]))


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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())


n, m, k = map(int, input().split())
fr = [0]*n
uf_fr = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    uf_fr.union(a-1, b-1)
    fr[a-1] += 1
    fr[b-1] += 1

for i in range(k):
    c, d = map(int, input().split())
    if uf_fr.find(c-1) == uf_fr.find(d-1):
        fr[c-1] += 1
        fr[d-1] += 1

ans_list = []
for i in range(n):
    ans_list.append(len(uf_fr.members(i)) - fr[i] - 1)
print(*ans_list)

Submission status: Time Limit Exceeded

Solution code:
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())


n, m, k = map(int, input().split())
fr = [0]*n
uf_fr = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    uf_fr.union(a-1, b-1)
    fr[a-1] += 1
    fr[b-1] += 1
for i in range(k):
    c, d = map(int, input().split())
    if uf_fr.find(c-1) == uf_fr.find(d-1):
        fr[c-1] += 1
        fr[d-1] += 1
ans_list = []
for i in range(n):
    ans_list.append(len(uf_fr.members(i)) - fr[i]-1)
print(*ans_list)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = list(map(int, input().split()))
p = [0] * N # p[][0] 友達リスト　p[][1] ブロックリスト p[][2] 所属グループ(-1はなし)
for i in range(N):
    p[i] = [0]*3
    p[i][0] = []
    p[i][1] = []
    p[i][2] = -1
g = [] # グループのサイズ
stack = []
groupNum = 0

for i in range(M):
    a, b = list(map(int, input().split()))
    p[a-1][0].append(b-1)
    p[b-1][0].append(a-1)

for i in range(K):
    c, d = list(map(int, input().split()))
    p[c-1][1].append(d-1)
    p[d-1][1].append(c-1)

def groupmake(person,group):
    groupSize = 0
    stack.append(person)
    p[person][2] = group
    while True:
        num = stack.pop()
        groupSize += 1
        for i in p[num][0]:
            if p[i][2] == -1:
                stack.append(i)
                p[i][2] = group
        if len(stack) == 0:
            return groupSize

for i in range(len(p)):
    if p[i][2] == -1:
        g.append(groupmake(i, groupNum))
        groupNum += 1

answer = ""

for person in p:
    fc = g[person[2]] - len(person[0]) -1
    for block in person[1]:
        if p[block][2] == person[2]:
            fc -= 1
    answer = answer + str(fc) + " "

print(answer.strip())

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())

friends = [set() for _ in range(N)]
for _ in range(M):
    a,b = map(lambda x: int(x)-1, input().split())
    friends[a].add(b)
    friends[b].add(a)

blocks = [set() for _ in range(N)]
for _ in range(K):
    c,d = map(lambda x: int(x)-1, input().split())
    blocks[c].add(d)
    blocks[d].add(c)

ans = [0]*N
visited = [False]*N
for i in range(N):
    if visited[i]: 
        continue
    d = [i]
    check = {i} 
    while len(d):
        tmp = d.pop()
        for k in friends[tmp]:
            if visited[k]:
                continue
            d.append(k) 
        visited[tmp] = True
        check.add(tmp)
    for j in check:
        ans[j] += len(check) - len(friends[j]&check) - len(blocks[j]&check) - 1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
friend = {}
for i in range(M):
    A, B = map(lambda x: x-1, map(int, input().split()))
    if A not in friend:
        friend[A] = []
    if B not in friend:
        friend[B] = []
    friend[A].append(B)
    friend[B].append(A)

block = {}
for i in range(K):
    C, D = map(lambda x: x-1, map(int, input().split()))
    if C not in block:
        block[C] = []
    if D not in block:
        block[D] = []
    block[C].append(D)
    block[D].append(C)

first = {}
for i in range(N):
    if i not in first:
        first[i] = i
        if i in friend:
            queue = []
            queue.extend(friend[i])
            counter = 0
            while counter < len(queue):
                item = queue[counter]
                first[item] = i
                if item in friend:
                    for n in friend[item]:
                        if n not in first:
                            queue.append(n)
                counter += 1

size = {}
for key in first:
    if first[key] not in size:
        size[first[key]] = 1
    else:
        size[first[key]] += 1

for i in range(N):
    if i not in friend:
        print(0)
        continue
    no_friend = 0
    if i in block:
        for b in block[i]:
            if first[b] == first[i]:
                no_friend += 1
    print(size[first[i]] - len(friend[i]) - no_friend - 1)

Submission status: Time Limit Exceeded

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

n,m,k =map(int,input().split())# nは頂点の数、mは辺の数
g = [[] for _ in range(n)] # 隣接リスト
g_sub = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)
for _ in range(k):
    c, d = [int(x) for x in input().split()]
    g_sub[c-1].append(d-1)
    g_sub[d-1].append(c-1)

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d
answer=[]
for i in range(0,n):
    d=bfs(i)
    for j in range(len(g_sub[i])):
        d[g_sub[i][j]]="#"
    s=0
    for l in range(len(d)):
        if (d[l]!=None and d[l]!="#"):
            if d[l]>=2:
                s+=1
    answer.append(s)
print(*answer)

Submission status: Time Limit Exceeded

Solution code:
nmk=input("").split(" ")
n=int(nmk[0])
m=int(nmk[1])
k=int(nmk[2])
listin=[-1]*n
listf=[]
listb=[]
for i in range(n):
    listf+=[[]]
    listb+=[[]]
for i in range(m):
    ab=input("").split(" ")
    a=int(ab[0])-1
    b=int(ab[1])-1
    listf[a]+=[b]
    listf[b]+=[a]
for i in range(k):
    ab=input("").split(" ")
    a=int(ab[0])-1
    b=int(ab[1])-1
    listb[a]+=[b]
    listb[b]+=[a]
s=-1
listff=[]

for i in range(n):
    if(listin[i]==-1):
        s+=1
        listin[i]=s
        listff+=[[i]]
        cnt=0
        
        while(len(listff[s])>cnt):
            for ii in listf[listff[s][cnt]]:
                if(listin[ii]==-1):
                    listin[ii]=s
                    listff[s]+=[ii]
                    
            cnt+=1
listans=[]

for i in range(n):
    
    listans+=[str(len(set(listff[listin[i]])-set(listb[i]))-1-len(listf[i]))]
print(" ".join(listans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

def cou(i,abwk,cdwk,wk):
    an=0
    tz=deque([i])+wk
    cd=0
    while wk:
        wwk=deque()
        j=wk.pop()
        wwwk=deque(abwk[j])
        while wwwk:
            k=wwwk.pop()
            if k not in tz:
                if i in cdwk[k]:
                    cd+=1
                wwk.append(k)
                an+=1
                tz.append(k)
            else:
                continue
        wk.extend(wwk) 
        
    return(an-cd)

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

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

an=[0]*n

for i in range(1,n+1):
    wk=deque(abwk[i])
    if wk:
        an[i-1]=cou(i,abwk,cdwk,wk)
    else:
        continue

for i in an:
    print(i,end=' ')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

import sys
sys.setrecursionlimit(10**9)
n,m,k=[int(i) for i in input().split()]
frends_num=[0 for i in range(n)]
def make_frends(m,n):
    data=[1 for i in range(m)]
    
    row=[]
    col=[]
    for k in range(m):
        i,j=[int(l) for l in input().split()]
        new_i=min(i,j)-1
        new_j=max(i,j)-1
        row.append(new_i)
        col.append(new_j)
        frends_num[new_i]+=1
        frends_num[new_j]+=1
    frend_sparce_matrix=csr_matrix((data, (row, col)),shape=(n,n))
    return frend_sparce_matrix


frends=make_frends(m,n)
l,labels=connected_components(frends)
labels
labels=list(labels)

class Group:
    def __init__(self,labels):
        self.group=[np.array([0]*n) for i in range(l)]
        self.labels=labels
        self.group_num=[0 for i in range(l)]
        for i in labels:
            self.group_num[i]+=1
    def get_group_num(self,i):
        return self.group_num[self.labels[i]]

group=Group(labels)


def get_frend_num(i):
    return frends_num[i]


def make_block(k,n):
    block_num=[0 for i in range(n)]
    for p in range(k):
        i,j =[int(l)-1 for l in input().split()]
        new_i=min(i,j)
        new_j=max(i,j)
        if labels[new_i]==labels[new_j]:
            block_num[i]+=1
            block_num[j]+=1
    return block_num
    
block=make_block(k,n)

def get_block_num(i):
    return block[i]    

ans=[]
for i in range(n):
    ans.append(str(group.get_group_num(i)-1-get_frend_num(i)-get_block_num(i)))
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def cou(i,abwk,cdwk,wk):
    an=0
    tz=deque([i])+wk
    cd=0
    while wk:
        wwk=deque()
        while wk:
            j=wk.pop()
            for k in abwk[j]:
                if k not in tz:
                    if i in cdwk[k]:
                        cd+=1
                    wwk.append(k)
                    an+=1
                    tz.append(k)
                else:
                    continue
        wk=wwk
    return(an-cd)

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

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

an=[0]*n

for i in range(1,n+1):
    wk=deque(abwk[i])
    if wk:
        an[i-1]=cou(i,abwk,cdwk,wk)
    else:
        continue

for i in an:
    print(i,end=' ')

Submission status: Time Limit Exceeded

Solution code:
def cou(i,abwk,cdwk,wk):
    an=0
    tz=[i]+wk
    cd=0
    while wk:
        wwk=[]
        for j in wk:
            for k in abwk[j]:
                if k not in tz:
                    if i in cdwk[k]:
                        cd+=1
                    wwk.append(k)
                    an+=1
                    tz.append(k)
                else:
                    continue
        wk=wwk
    return(an-cd)

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

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

an=[0]*n

for i in range(1,n+1):
    if abwk[i]:
        an[i-1]=cou(i,abwk,cdwk,abwk[i])
    else:
        continue

for i in an:
    print(i,end=' ')

Submission status: Time Limit Exceeded

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

if __name__ == '__main__':
    main()