Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

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

f_set = {tuple(map(int,input().split())) for _ in range(m)}

b_set = {tuple(map(int,input().split())) for _ in range(k)}


friends_counts = {key:[] for key in range(1,n+1)}
blocks_counts = {key:[] for key in range(1,n+1)}

for f in f_set:
    friends_counts[f[0]].append(f[1])
    friends_counts[f[1]].append(f[0])

for b in b_set:
    blocks_counts[b[0]].append(b[1])
    blocks_counts[b[1]].append(b[0])



friends_groups_dict = defaultdict(list)

#dfs
que = deque()
groups_count = 0
checked_dict = {key:0 for key in range(1,n+1)}
#que.appendleft(1)

for i in range(1,n+1):
    if checked_dict[i] == 1:
        continue
    que.appendleft(i)
    checked_dict[i] = 1

    while que:
        x = que.popleft()
        friends_groups_dict[groups_count].append(x)
        for i in range(len(friends_counts[x])):
            if checked_dict[friends_counts[x][i]] == 0:
                que.appendleft(friends_counts[x][i])
            checked_dict[friends_counts[x][i]] = 1

    groups_count += 1


result_list=[0]*n

for i in range(len(friends_groups_dict)):
    mini_list = friends_groups_dict[i]
    for j in range(len(mini_list)):
        result_list[mini_list[j]-1] = len(mini_list) - 1 - len(friends_counts[mini_list[j]])
        
        block_counter_in_minilist = 0

        for k in range(len(blocks_counts[mini_list[j]])):
            if blocks_counts[mini_list[j]][k] in set(mini_list):
                block_counter_in_minilist += 1
        
        result_list[mini_list[j]-1] -= block_counter_in_minilist
 
print(" ".join(map(str,result_list)))



#cの配列の解釈が違ったらしい。。。
#f_set = {tuple(map(int,input().split())) for _ in range(m)}
#
#b_set = {tuple(map(int,input().split())) for _ in range(k)}
#
#c_list = [0] * (n-1)
#
#result_dict = {key:0 for key in range(1,n+1)}
#
#for f in f_set:
#    if abs(f[0]-f[1]) == 1:
#        c_list[min(f[0],f[1]) - 1] = 1
#    #ここでelseで飛び石での友達のsetを作ってもよいが、そもそもsetなのでinでの探索にそんなに時間かからないし、いったんこのままやってみる。
#
#for start in range(0,n-2):
#    if c_list[start] == 0:
#        #c[start]が1になるまで飛ばす
#        continue
#
#    for end in range(start+1,n-1):
#        if c_list[end] == 0:
#            #友人同士ではないペアまできたらstartをインクリメント
#            break
#        
#        #もし「友人候補」の候補者が、「友人関係でない」かつ「ブロック関係でない」ことをチェックしている。
#        if not (start+1,end+2) in f_set and not (end+2,start+1) in f_set and not (start+1,end+2) in b_set and not (end+2,start+1) in b_set:
#            result_dict[start+1] += 1
#            result_dict[end+2] += 1
#
#for i in range(1,n+1):
#    print(result_dict[i])
#
#print(c_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 members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]    

N, M, K = map(int,input().split())
uf = UnionFind(N)
frend = [set() for _ in range(N)]
block = [set() for _ in range(N)]
ans = []
for i in range(M):
    A, B = map(int,input().split())
    A -= 1
    B -= 1
    uf.union(A, B)
    uf.find(A)
    frend[A].add(B)
    frend[B].add(A)
    
for i in range(K):
    C, D = map(int,input().split())
    C -= 1
    D -= 1
    block[C].add(D)
    block[D].add(C)    

for i in range(N):
    temp = uf.size(i) - 1
    for j in uf.members(i):
        if (j in frend[i]) or (j in block[i]):
            temp -= 1
    ans.append(temp)
print(*ans)

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 members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]    

N, M, K = map(int,input().split())
uf = UnionFind(N)
frend = [set() for _ in range(N)]
block = [set() for _ in range(N)]
ans = []
for i in range(M):
    A, B = map(int,input().split())
    A -= 1
    B -= 1
    uf.union(A, B)
    frend[A].add(B)
    frend[B].add(A)
    
for i in range(K):
    C, D = map(int,input().split())
    C -= 1
    D -= 1
    block[C].add(D)
    block[D].add(C)    

for i in range(N):
    temp = uf.size(i) - 1
    for j in uf.members(i):
        if (j in frend[i]) or (j in block[i]):
            temp -= 1
    ans.append(temp)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def wf(m, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                m[i][j] = min(m[i][j], m[i][k] + m[k][j])
    return m


def main():
    n, m, k, *abcd = map(int, open(0).read().split())
    ab, cd = abcd[:2 * m], abcd[2 * m:]
    m = [[float("Inf")] * n for _ in range(n)]
    for i in range(n):
        m[i - 1][i - 1] = 0
    for i, j in zip(*[iter(ab)] * 2):
        m[i - 1][j - 1] = 1
        m[j - 1][i - 1] = 1
    w = wf(m, n)
    for i, j in zip(*[iter(ab)] * 2):
        m[i - 1][j - 1] = -1
        m[j - 1][i - 1] = -1
    for i, j in zip(*[iter(cd)] * 2):
        w[i - 1][j - 1] = -1
        w[j - 1][i - 1] = -1

    ans = ""
    for x in w:
        c = sum([0 < i < n for i in x])
        ans += str(c) + ' '

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,m,k=map(int,input().split())
  ab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(k)]
  friend=[[]for _ in range(n)]
  block=[[]for _ in range(n)]
  for a,b in ab:
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
  for c,d in cd:
    block[c-1].append(d-1)
    block[d-1].append(c-1)
  # 友達連結内でかつ友達でもブロックでもない。
  # 友達連結グループわけ
  ans=[0]*n
  seen=[0]*n
  for t in range(n):
    if seen[t]==1:
      continue
    member=[]
    todo=[t]
    seen[t]=1
    while todo:
      t=todo.pop()
      member.append(t)
      f=friend[t]
      for fi in f:
        if seen[fi]==0:
          todo.append(fi)
          seen[fi]=1
    mn=len(member)
    for m in member:
      ans[m]=mn-len(set(block[m]).intersection(set(member)))-len(friend[m])-1
  print(' '.join(map(str,ans)))
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,m,k=map(int,input().split())
  ab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(k)]
  friend=[[]for _ in range(n)]
  block=[[]for _ in range(n)]
  for a,b in ab:
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
  for c,d in cd:
    block[c-1].append(d-1)
    block[d-1].append(c-1)
  # 友達連結内でかつ友達でもブロックでもない。
  # 友達連結グループわけ
  ans=[0]*n
  seen=[0]*n
  for t in range(n):
    if seen[t]==1:
      continue
    member=[]
    todo=[t]
    seen[t]=1
    while todo:
      t=todo.pop()
      member.append(t)
      f=friend[t]
      for fi in f:
        if seen[fi]==0:
          todo.append(fi)
          seen[fi]=1
    mn=len(member)
    for m in member:
      ans[m]=mn-len([mi for mi in block[m] if mi in member])-len(friend[m])-1
  print(' '.join(map(str,ans)))
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
cd=[list(map(int,input().split())) for _ in range(k)]
friend=[[]for _ in range(n)]
block=[[]for _ in range(n)]
for a,b in ab:
  friend[a-1].append(b-1)
  friend[b-1].append(a-1)
for c,d in cd:
  block[c-1].append(d-1)
  block[d-1].append(c-1)
# 友達連結内でかつ友達でもブロックでもない。
# 友達連結グループわけ
ans=[0]*n
seen=[0]*n
while 0 in seen:
  member=[]
  t=seen.index(0)
  todo=[t]
  seen[t]=1
  while todo:
    t=todo.pop()
    member.append(t)
    f=friend[t]
    for fi in f:
      if seen[fi]==0:
        todo.append(fi)
        seen[fi]=1
  for m in member:
    ans[m]=len([mi for mi in member if mi not in block[m]])-len(friend[m])-1
print(' '.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
cd=[list(map(int,input().split())) for _ in range(k)]
friend=[[]for _ in range(n)]
block=[[]for _ in range(n)]
for a,b in ab:
  friend[a-1].append(b-1)
  friend[b-1].append(a-1)
for c,d in cd:
  block[c-1].append(d-1)
  block[d-1].append(c-1)
# 友達連結内でかつ友達でもブロックでもない。
# 友達連結グループわけ
friend_group=[[] for _ in range(n)]
seen=[0]*n
while 0 in seen:
  member=[]
  t=seen.index(0)
  todo=[t]
  seen[t]=1
  while todo:
    t=todo.pop()
    member.append(t)
    f=friend[t]
    for fi in f:
      if seen[fi]==0:
        todo.append(fi)
        seen[fi]=1
  mn=len(member)
  for m in member:
    friend_group[m]=len([mi for mi in member if mi!=m and mi not in friend[m]+block[m]])
print(' '.join(map(str,friend_group)))

Submission status: Time Limit Exceeded

Solution code:
import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
# import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


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


def main():
    n, m, k = ns()

    friend = UnionFind(n)

    myfriend = [0 for _ in range(n)]
    blocks = {}
    for i in range(n):
        blocks[i] = set()

    for _ in range(m):
        ai, bi = ns()
        ai -= 1
        bi -= 1
        friend.union(ai, bi)
        myfriend[ai] += 1
        myfriend[bi] += 1

    for _ in range(k):
        ci, di = ns()
        ci -= 1
        di -= 1

        blocks[ci].add(di)
        blocks[di].add(ci)

    tmp = 0
    for i in range(n):
        tmp_block = 0
        for j in blocks[i]:
            if friend.same(i, j):
                tmp_block += 1

        ans = len(friend.members(i)) - 1 - myfriend[i] - tmp_block
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
# import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


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


def main():
    n, m, k = ns()

    friend = UnionFind(n)

    myfriend = {}
    brock = {}
    for i in range(n):
        myfriend[i] = set()
        brock[i] = set()

    for _ in range(m):
        ai, bi = ns()
        ai -= 1
        bi -= 1
        friend.union(ai, bi)
        myfriend[ai].add(bi)
        myfriend[bi].add(ai)

    for _ in range(k):
        ci, di = ns()
        ci -= 1
        di -= 1

        brock[ci].add(di)
        brock[di].add(ci)

    tmp = 0
    for i in range(n):
        ans = {}
        tmp = set(friend.members(i))
        ans = tmp - brock[i] - myfriend[i]
        print(len(ans) - 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


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


def main():
    n, m, k = ns()

    friend = UnionFind(n)

    myfriend = {}
    brock = {}
    for i in range(n):
        myfriend[i] = set()
        brock[i] = set()

    for _ in range(m):
        ai, bi = ns()
        ai -= 1
        bi -= 1
        friend.union(ai, bi)
        myfriend[ai].add(bi)
        myfriend[bi].add(ai)

    for _ in range(k):
        ci, di = ns()
        ci -= 1
        di -= 1

        brock[ci].add(di)
        brock[di].add(ci)

    tmp = 0
    for i in range(n):
        ans = {}
        tmp = set(friend.members(i))
        ans = tmp - brock[i] - myfriend[i]
        print(len(ans) - 1)


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())
uf=UnionFind(N)

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

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

for i in range(N):
    res=len(set(uf.members(i))-set(blocks[i])-set(friends[i]))-1
    print(res,end=" ")

Submission status: Time Limit Exceeded

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

def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}

    for i in range(n):
        root[i]=[]
        ng[i]=[]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    
    Vstd=[]
    v_append=Vstd.append
    checkVst=[False]*n
    num=[0]*n
    ToVst=queue.Queue()
    for i in range(n):
        if checkVst[i]:
            continue
        Vstd=[]
        v_append=Vstd.append
        now=i
        v_append(now)
        checkVst[now]=True

        for kouho in root[now]:
            if checkVst[kouho]:
                continue
            ToVst.put(kouho)
            checkVst[kouho]=True

        while ToVst.empty()==False:
            now=ToVst.get()
            v_append(now)
            checkVst[now]=True
           
            for kouho in root[now]:
                if checkVst[kouho]:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=True
                
        lengh=len(Vstd)
        for v in Vstd:
            num[v]=lengh-1
            num[v]-=len((set(ng[v]) | set(root[v]))&set(Vstd))
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}

    for i in range(n):
        root[i]=[]
        ng[i]=[]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
     #   ng[a-1].append(b-1)
      #  ng[b-1].append(a-1)
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    
    Vstd=[]
    v_append=Vstd.append
    checkVst=[False]*n
    num=[0]*n
    ToVst=queue.Queue()
    for i in range(n):
        if checkVst[i]:
            continue
        Vstd=[]
        v_append=Vstd.append
        now=i
        v_append(now)
        checkVst[now]=True

        for kouho in root[now]:
            if checkVst[kouho]:
                continue
            ToVst.put(kouho)
            checkVst[kouho]=True

        while ToVst.empty()==False:
            now=ToVst.get()
            v_append(now)
            checkVst[now]=True
           
            for kouho in root[now]:
                if checkVst[kouho]:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=True
                
        lengh=len(Vstd)
        for v in Vstd:
            num[v]=lengh-1
            num[v]-=len((set(ng[v]) | set(root[v]))&set(Vstd))
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}

    for i in range(n):
        root[i]=[]
        ng[i]=[]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    
    Vstd=[]
    v_append=Vstd.append
    checkVst=[False]*n
    num=[0]*n
    ToVst=queue.Queue()
    for i in range(n):
        if checkVst[i]:
            continue
        Vstd=[]
        v_append=Vstd.append
        now=i
        v_append(now)
        checkVst[now]=True

        for kouho in root[now]:
            if checkVst[kouho]:
                continue
            ToVst.put(kouho)
            checkVst[kouho]=True

        while ToVst.empty()==False:
            now=ToVst.get()
            v_append(now)
            checkVst[now]=True
           
            for kouho in root[now]:
                if checkVst[kouho]:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=True
                
        lengh=len(Vstd)
        for v in Vstd:
            num[v]=lengh-1
            num[v]-=len(set(ng[v])&set(Vstd))
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys 
input=sys.stdin.readline
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    for i in range(n):
        root[i]=[]
        ng[i]=[]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    
    Vstd=[]
    checkVst=[False]*n
    num=[0]*n
    ToVst=queue.Queue()
   
    for i in range(n):
        if checkVst[i]:
            continue
        Vstd=[]
        now=i
        Vstd.append(now)
        checkVst[now]=True

        for kouho in root[now]:
            if checkVst[kouho]:
                continue
            ToVst.put(kouho)
            checkVst[kouho]=True

        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=True
           
            for kouho in root[now]:
                if checkVst[kouho]:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=True
                
        lengh=len(Vstd)
        for v in Vstd:
            num[v]=lengh-1
            num[v]-=len(set(ng[v])&set(Vstd))
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    for i in range(n):
        root[i]=[]
        ng[i]=[]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    
    Vstd=[]
    checkVst=[False]*n
    num=[0]*n
    ToVst=queue.Queue()
   
    for i in range(n):
        
        Vstd=[]
        if checkVst[i]:
            continue
        now=i
        Vstd.append(now)
        checkVst[now]=True
        

        for kouho in root[now]:
            if checkVst[kouho]:
                continue
            ToVst.put(kouho)
            checkVst[kouho]=True
            #if checkVst[kouho]!=1:
             #   ToVst.put(kouho)
              #  checkVst[kouho]=1
              
        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=True
           
            for kouho in root[now]:
                if checkVst[kouho]:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=True
                
        lengh=len(Vstd)
        for v in Vstd:
            num[v]=lengh-1
            num[v]-=len(set(ng[v])&set(Vstd))
            


    
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    for i in range(n):
        root[i]=[]
        ng[i]=[]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    
    Vstd=[]
    checkVst=[0]*n
    num=[0]*n
    ToVst=queue.Queue()
   
    for i in range(n):
        
        Vstd=[]
        if checkVst[i]!=0:
            continue
        now=i
        Vstd.append(now)
        checkVst[now]=1
        

        for kouho in root[now]:
            if checkVst[kouho]!=1:
                ToVst.put(kouho)
                checkVst[kouho]=1
              
        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=1
           
            for kouho in root[now]:
                if checkVst[kouho]!=0:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=1
                
        lengh=len(Vstd)
        for v in Vstd:
            num[v]=lengh-1
            num[v]-=len(set(ng[v])&set(Vstd))
            


    
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    for i in range(n):
        root[i]=[]
        ng[i]=[]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    
    Vstd=[]
    checkVst=[0]*n
    num=[0]*n
    ToVst=queue.Queue()
    Thisturn=[0 for i in range(n)]
    for i in range(n):
        Thisturn=[0 for i in range(n)]
        Vstd=[]
        if checkVst[i]!=0:
            continue
        now=i
        Vstd.append(now)
        checkVst[now]=1
        Thisturn[now]=1

        for kouho in root[now]:
            if checkVst[kouho]!=1:
                ToVst.put(kouho)
                checkVst[kouho]=1
                Thisturn[kouho]=1
        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=1
            Thisturn[now]=1
            for kouho in root[now]:
                if checkVst[kouho]!=0:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=1
                Thisturn[kouho]=1
        lengh=len(Vstd)
        for v in Vstd:
            num[v]=lengh-1
            for j in ng[v]:
                if Thisturn[j]==1:
                    num[v]-=1


    
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()