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:
#!/usr/bin/env python3
import sys
import collections

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # 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, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]

    def group_members(self, x):  # x が属する集合の要素を返す
        root = self.find(x)
        return set(i for i in range(self.n) if self.find(i) == root)

    def roots(self):  # すべての根をリストで返す
        return [i for i, x in enumerate(self.parent) if i == x]

    def group_count(self):  # 木の数を返す
        return len(self.roots())

    def all_group_members(self):  # すべての木の要素を辞書で返す
        return {r: self.group_members(r) for r in self.roots()}


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    uf = UnionFind(N)
    block = collections.defaultdict(set)
    follow = collections.defaultdict(set)
    for a, b in zip(A, B):
        uf.unite(a, b)
        follow[a].add(b)
        follow[b].add(a)
    for c, d in zip(C, D):
        block[c].add(d)
        block[d].add(c)

    result = [len(uf.group_members(i) - block[i] - follow[i]) - 1 for i in range(N)]
    result = [str(x) for x in result]
    print(' '.join(result))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens)) - 1
        B[i] = int(next(tokens)) - 1
    C = [int()] * (K)  # type: "List[int]"
    D = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        C[i] = int(next(tokens)) - 1
        D[i] = int(next(tokens)) - 1
    solve(N, M, K, A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# D - Friend Suggestions

from queue import Queue

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

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

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

Q = Queue()
cnt = [0] * N
for i in range(N):
    visited = [False] * N
    Q.put(friends[i])
    visited[i] = True
    while not Q.empty():
        q = Q.get()
        if (q[0] != i and
                q[0] not in friends[i][1] and
                q[0] not in blocks[i][1]):
            cnt[i] += 1
        for j in q[1]:
            if not visited[j]:
                visited[j] = True
                Q.put(friends[j])

print(*cnt)

Submission status: Time Limit Exceeded

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

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 set(i for i in range(self.n) if self.find(i) == root)

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    uf = UnionFind(N)
    block = collections.defaultdict(set)
    follow = collections.defaultdict(set)
    for a, b in zip(A, B):
        uf.union(a, b)
        follow[a].add(b)
        follow[b].add(a)
    for c, d in zip(C, D):
        block[c].add(d)
        block[d].add(c)

    result = ''
    for i in range(0, N):
        result += '%d '%(len(uf.members(i) - block[i] - follow[i]) - 1)
    print(result[:-1])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens)) - 1
        B[i] = int(next(tokens)) - 1
    C = [int()] * (K)  # type: "List[int]"
    D = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        C[i] = int(next(tokens)) - 1
        D[i] = int(next(tokens)) - 1
    solve(N, M, K, A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    A = [a-1 for a in A]
    B = [b - 1 for b in B]
    C = [c - 1 for c in C]
    D = [d - 1 for d in D]
    uf = UnionFind(N)
    block = collections.defaultdict(set)
    follow = collections.defaultdict(set)
    for a, b in zip(A, B):
        uf.union(a, b)
        follow[a].add(b)
        follow[b].add(a)
    for c, d in zip(C, D):
        block[d].add(c)
        block[c].add(d)
    result = []
    for i in range(N):
        result.append(len(set(uf.members(i)) - block[i] - follow[i]) -1)
    result = [str(x) for x in result]
    print(' '.join(result))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  # type: "List[int]"
    D = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#Union Find
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

N,M,K = map(int,input().split())
#初期化
#根なら-size,子なら親の頂点
par = [-1]*(N+1)

friends = [[]for i in range(0,N+1,1)]
block = [[]for i in range(0,N+1,1)]
for i in range(0,M,1):
    a,b = map(int,input().split())
    friends[a].append(b)
    friends[b].append(a)
    unite(a,b)
for i in range(0,K,1):
    a,b=map(int,input().split())
    block[a].append(b)
    block[b].append(a)

countmem = [0]*N
for i in range(1,N+1,1):
    count = size(i)-1
    mem = []
    ma = mem.append
    for j in range(0,len(friends[i]),1):
        if same(i,friends[i][j]):
            count -=1
            ma(friends[i][j])
    for j in range(0,len(block[i]),1):
        if same(i,block[i][j]) and not(block[i][j] in mem):
            count -=1
    countmem[i-1]=count

print(*countmem)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

friend = defaultdict(set)
block  = defaultdict(set)
dp = {}

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

for i in range(m):
  a, b = map(int, input().split())
  friend[a] |= {b}
  friend[b] |= {a}
for i in range(k):
  a, b = map(int, input().split())
  block[a] |= {b}
  block[b] |= {a}

def find(node):
  if node in dp:
    seen = dp[node]
  else:
    seen = set([node])
    q = set([node])
    while q != set():
      next_q = set()
      for i in q:
        for n in filter(lambda x: x not in seen, friend[i]):
          next_q |= {n}
        seen |= friend[i]
      q = next_q
    for n in seen:
      dp[n] = seen
  cands = seen - {node} - block[node] - friend[node]
  return len(cands)

print(' '.join(str(find(i)) for i in range(1, n+1)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter

N, M, K = map(int, input().split())
Friend = [[]for i in range(N)]
Block = [[] for i in range(N)]

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

for i in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    Block[c].append(d)
    Block[d].append(c)
Group = [0] * N
Q = deque()
for i in range(1, N):
    if 0 not in Group:
        break
    else:
        z = Group.index(0)
        Group[z] = i
        Q.append(z)
        while len(Q) > 0:
            now = Q.popleft()
            for j in Friend[now]:
                if Group[j] != 0:
                    continue
                else:
                    Group[j] = i
                    Q.append(j)
G_ = Counter(Group)
for i in range(N):
    ans = G_[Group[i]] - 1
    for j in Friend[i]:
        if Group[i] == Group[j]:
            ans -= 1
    for j in Block[i]:
        if Group[i] == Group[j]:
            ans -= 1
    print(ans, end=' ')

Submission status: Time Limit Exceeded

Solution code:
def main():
    class unionfind():
        def __init__(self,n):
            self.par = [i for i in range(n)]
            self.size = [1 for i in range(n)]
            self.rank = [0 for i in range(n)]
 
        def root(self,x):
            if self.par[x] == x:
                return x
            else:
                self.par[x] = self.root(self.par[x])
                return self.par[x]
 
        def same(self,x,y):
            return self.root(x) == self.root(y)
 
        def unite(self,x,y):
            x = self.root(x)
            y = self.root(y)
            if x==y:return
            else:
                if self.rank[x] < self.rank[y]:
                     x,y = y,x
                if self.rank[x] < self.rank[y]:
                    self.rank[x]+=1
                self.par[y] = x
                self.size[x] +=self.size[y]
        def get_size(self,x):
            x = self.root(x)
            return self.size[x]
 
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    n,m,k = map(int,input().split())
    uff = unionfind(n)
    fr = [0 for i in range(n)]
 
 
    for i in range(m):
        a,b = map(int,input().split())
        uff.unite(a-1,b-1)
        fr[a-1]+=1
        fr[b-1]+=1
 
 
    ans = [uff.get_size(i) -fr[i]-1 for i in range(n)]
 
    for i in range(k):
        c,d = map(int,input().split())
        if uff.same(c-1,d-1):
            ans[c-1] -=1
            ans[d-1] -=1
    print(*ans)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

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


par=[index for index in range(N+1)]

def root(x):
    global par

    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]


def same(x,y):
    global par

    if root(x)==root(y):
        return True
    else:
        return False

def unite(x,y):
    global par

    if root(x)!=root(y):
        par[root(x)]=root(y)


friends=[[] for index1 in range(N+1)]
for index2 in range(M):
    a,b=map(int,input().split())
    unite(a,b)
    friends[a].append(b)
    friends[b].append(a)


block=[[] for index3 in range(N+1)]
for index4 in range(K):
    c,d=map(int,input().split())
    block[c].append(d)
    block[d].append(c)


relates=[0]*(N+1)
for i in range(1,N+1):
    relates[root(i)]+=1


Ans=[]
for j in range(1,N+1):
    ans=relates[root(j)]-1    #高速化可能   #1
    for k in friends[j]:
        if same(j,k):
            ans-=1
    for l in block[j]:
        if same(j,l):   #まとめられる
            ans-=1

    Ans.append(ans)

print(*Ans)

Submission status: Time Limit Exceeded

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

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

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

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

ans = str( len( set( uf.members( 1 )) - set( block[ 1 ] + friends[ 1 ]))  - 1 )
for i in range( 2, N + 1 ):
  ans += " " + str( len( set( uf.members( i )) - set( block[ i ] + friends[ i ]))  - 1 )
print( ans )

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

from collections import Counter

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

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return graph_g[s]

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        dfs(edge, graph_cnt)


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

for i in range(N):
    if is_visited[i]:
        continue
    dfs(i, None)

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

ct = Counter(graph_g)

ret = []
for i in range(N):
    cand = ct[graph_g[i]]
    fri = len(to[i])
    tmp_block = len(block[i])

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10**7)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    n_to = [0 for _ in range(N + 1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        #a,b = AB[i]
        to[a].append(b)
        n_to[a] += 1
        to[b].append(a)
        n_to[b] += 1

    stack = defaultdict(lambda:0)
    visited = [False] * (N+1)
    belong = [None] * (N+1)


    def dfs(n):
        _stack = [n]
        visited[n] = True
        while _stack:
            node = _stack.pop()
            stack[n] += 1
            belong[node] = n
            for next in to[node]:
                if not visited[next]:
                    _stack.append(next)
                    visited[next] = True
        return None


    for i in range(1,N+1):
        if not visited[i]:
            dfs(i)

    block = [0 for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        #c, d = CD[i]
        if belong[c] == belong[d]:
            block[c] += 1
            block[d] += 1

    candidates = [0] * (N+1)

    for tree in stack.keys():
        for k in range(1,N+1):
            tr = belong[k]
            candidates[k] = stack[tr] - 1 - n_to[k] - block[k]

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return graph_g[s]

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        dfs(edge, graph_cnt)


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

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

for i in range(N):
    if is_visited[i]:
        continue
    dfs(i, None)

group_to_idx = [set() for i in range(graph_cnt+1)]
if len(group_to_idx) != 0:
    for i in range(N):
        group_to_idx[graph_g[i]].add(i)

ret = []
for i in range(N):
    cand = len(group_to_idx[graph_g[i]])
    fri = len(to[i])
    tmp_block = len(group_to_idx[graph_g[i]] & set(block[i]))

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return graph_g[s]

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        dfs(edge, graph_cnt)


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

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

for i in range(N):
    dfs(i, None)

group_to_idx = [set() for i in range(graph_cnt+1)]
if len(group_to_idx) != 0:
    for i in range(N):
        group_to_idx[graph_g[i]].add(i)

ret = []
for i in range(N):
    cand = len(group_to_idx[graph_g[i]])
    fri = len(to[i])
    tmp_block = len(group_to_idx[graph_g[i]] & set(block[i]))

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    n_to = [0 for _ in range(N + 1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        #a,b = AB[i]
        to[a].append(b)
        n_to[a] += 1
        to[b].append(a)
        n_to[b] += 1

    stack = defaultdict(lambda:0)
    visited = [False] * (N+1)
    belong = [None] * (N+1)


    def dfs(n):
        _stack = [n]
        visited[n] = True
        while _stack:
            node = _stack.pop()
            stack[n] += 1
            belong[node] = n
            for next in to[node]:
                if not visited[next]:
                    _stack.append(next)
                    visited[next] = True
        return None


    while True:
        k = -1
        for i in range(1,N+1):
            if not visited[i]:
                k = i
                break
        if k == -1:break
        dfs(k)



    block = [0 for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        #c, d = CD[i]
        if belong[c] == belong[d]:
            block[c] += 1
            block[d] += 1

    candidates = [0] * (N+1)

    for tree in stack.keys():
        for k in range(1,N+1):
            tr = belong[k]
            candidates[k] = stack[tr] - 1 - n_to[k] - block[k]

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    n_to = [0 for _ in range(N + 1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        #a,b = AB[i]
        to[a].append(b)
        n_to[a] += 1
        to[b].append(a)
        n_to[b] += 1

    stack = defaultdict(lambda:[])
    visited = [False] * (N+1)
    belong = [None] * (N+1)


    def dfs(n):
        _stack = [n]
        visited[n] = True
        while _stack:
            node = _stack.pop()
            stack[n].append(node)
            belong[node] = n
            for next in to[node]:
                if not visited[next]:
                    _stack.append(next)
                    visited[next] = True
        return None


    while True:
        k = -1
        for i in range(1,N+1):
            if not visited[i]:
                k = i
                break
        if k == -1:break
        dfs(k)



    block = [0 for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        #c, d = CD[i]
        if belong[c] == belong[d]:
            block[c] += 1
            block[d] += 1

    candidates = [0] * (N+1)

    for tree in stack.keys():
        length = len(stack[tree])
        for k in stack[tree]:
            candidates[k] = length - 1 - n_to[k] - block[k]

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**6)
def run():
    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    n_to = [0 for _ in range(N + 1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        to[a].append(b)
        n_to[a] += 1
        to[b].append(a)
        n_to[b] += 1

    stack = defaultdict(lambda:[])
    visited = [False] * (N+1)
    belong = [None] * (N+1)

    def dfs(n, tree= None):
        visited[n] = True
        if tree==None:
            tree = n
        stack[tree].append(n)
        belong[n] = tree
        for next in to[n]:
            if not visited[next]:
                dfs(next, tree)
        return None

    while True:
        k = -1
        for i in range(1,N+1):
            if not visited[i]:
                k = i
                break
        if k == -1:break
        dfs(k)

    block = [0 for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        if belong[c] == belong[d]:
            block[c] += 1
            block[d] += 1

    candidates = [0] * (N+1)

    for tree in stack.keys():
        length = len(stack[tree])
        for k in stack[tree]:
            candidates[k] = length - 1 - n_to[k] - block[k]

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**6)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        to[a].append(b)
        to[b].append(a)


    stack = defaultdict(lambda:[])
    visited = [False] * (N+1)
    belong = [None] * (N+1)

    def dfs(n, tree= None):
        visited[n] = True
        if tree==None:
            tree = n
        stack[tree].append(n)
        belong[n] = tree
        for next in to[n]:
            if not visited[next]:
                dfs(next, tree)
        return None

    while True:
        k = -1
        for i in range(1,N+1):
            if not visited[i]:
                k = i
                break
        if k == -1:break
        dfs(k)

    block = [[] for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        if belong[c] == belong[d]:
            block[c].append(d)
            block[d].append(c)

    candidates = [0] * (N+1)

    for tree in stack.keys():
        length = len(stack[tree])
        for k in stack[tree]:
            candidates[k] = length - 1 - len(to[k]) - len(block[k])

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**6)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        to[a].append(b)
        to[b].append(a)


    stack = defaultdict(lambda:[])
    visited = [False] * (N+1)
    belong = [None] * (N+1)

    def dfs(n, tree= None):
        visited[n] = True
        if tree==None:
            tree = n
        stack[tree].append(n)
        belong[n] = tree
        for next in to[n]:
            if not visited[next]:
                dfs(next, tree)
        return None

    block = [[] for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        if belong[c] == belong[d]:
            block[c].append(d)
            block[d].append(c)

    while True:
        k = -1
        for i in range(1,N+1):
            if not visited[i]:
                k = i
                break
        if k == -1:break
        dfs(k)

    candidates = [0] * (N+1)

    for tree in stack.keys():
        for k in stack[tree]:
            check_list = to[k] + block[k] + [k]
            s = [k_ for k_ in stack[tree] if not k_ in check_list]
            candidates[k] = len(s)

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()