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 deque
N, M, K = map(int, input().split())
A = [set() for i in range(N)]
B = [set() for i in range(N)]
for i in range(M):
  a, b = map(lambda x:int(x)-1, input().split())
  A[a].add(b)
  A[b].add(a)
for i in range(K):
  a, b = map(lambda x:int(x)-1, input().split())
  B[a].add(b)
  B[b].add(a)
P = [-1 for i in range(N)]
Q = []
k = -1
for i in range(N):
  if P[i] == -1:
    q = {i}
    k += 1
    P[i] = k
    d = deque([i])
    while len(d):
      s = d.pop()
      for t in A[s]:
        if P[t] == -1:
          P[t] = k
          q.add(t)
          d.append(t)
    Q.append(q)
for i in range(N):
  print(len(Q[P[i]] - A[i] - B[i]) - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M, K = map(int, input().split())
A = [[] for i in range(N)]
B = [[] for i in range(N)]
for i in range(M):
  a, b = map(lambda x:int(x)-1, input().split())
  A[a].append(b)
  A[b].append(a)
for i in range(K):
  a, b = map(lambda x:int(x)-1, input().split())
  B[a].append(b)
  B[b].append(a)
P = [-1 for i in range(N)]
k = 0
for i in range(N):
  if P[i] == -1:
    k += 1
    P[i] = k
    d = deque([i])
    while len(d):
      s = d.pop()
      for t in A[s]:
        if P[t] == -1:
          P[t] = k
          d.append(t)
for i in range(N):
  ans = 0
  for j in range(N):
    if P[i] == P[j] and i != j and j not in A[i] and j not in B[i]:
      ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

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

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

seen = [0 for i in range(N+1)]
num_connect = [0 for i in range(N+1)]
cluster = [0 for i in range(N+1)]

def bfs(u, c):
    visited = [0 for i in range(N+1)]
    stack = deque([u])
    seen[u] = 1
    count = 1

    while len(stack) > 0:
        v = stack.popleft()
        visited[v] = 1
        cluster[v] = c
        for w in al[v]:
            if seen[w] == 0:
                stack.append(w)
                count += 1
                seen[w] = 1

    for i in range(1,N+1):
        if visited[i] == 1:
            num_connect[i] = count

c = 1
for i in range(1,N+1):
    if seen[i] == 0:
        bfs(i, c)
        c += 1

for i in range(1,N+1):
    bl = 0
    for d in block[i]:
        if cluster[i] == cluster[d]:
            bl += 1
    print(num_connect[i] - 1 - len(al[i]) - bl, end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    from collections import deque

    N, M, K = map(int, input().split())
    friends = [set() for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        friends[a].add(b)
        friends[b].add(a)
    blocks = [set() for _ in range(N + 1)]
    for _ in range(K):
        c, d = map(int, input().split())
        blocks[c].add(d)
        blocks[d].add(c)

    friends_chain = []
    seen = [-1] * (N + 1)
    cnt = 0
    for person in range(1, N + 1):
        if seen[person] != -1:
            continue
        q = deque([person])
        friends_chain.append(set(q))
        while q:
            now = q.pop()
            seen[now] = cnt
            for next in friends[now]:
                if seen[next] != -1:
                    continue
                friends_chain[-1].add(next)
                q.append(next)
        cnt += 1

    ans = [0] * (N + 1)
    for person in range(1, N + 1):
        res = friends_chain[seen[person]]
        tmp_ans = len(res) - len(friends[person]) - 1
        for block in blocks[person]:
            tmp_ans -= 1 if block in res else 0
        ans[person] = (tmp_ans)
    print(*ans[1:], sep=' ')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    from collections import deque

    N, M, K = map(int, input().split())
    friends = [set() for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        friends[a].add(b)
        friends[b].add(a)
    blocks = [set() for _ in range(N + 1)]
    for _ in range(K):
        c, d = map(int, input().split())
        blocks[c].add(d)
        blocks[d].add(c)

    friends_chain = []
    seen = [-1] * (N + 1)
    cnt = 0
    for person in range(1, N + 1):
        if seen[person] != -1:
            continue
        q = deque([person])
        friends_chain.append(set(q))
        while q:
            now = q.pop()
            seen[now] = cnt
            for next in friends[now]:
                if seen[next] != -1:
                    continue
                friends_chain[-1].add(next)
                q.append(next)
        cnt += 1

    ans = []
    for person in range(1, N + 1):
        res = friends_chain[seen[person]]
        tmp_ans = len(res) - len(friends[person]) - 1
        for block in blocks[person]:
            tmp_ans -= 1 if block in res else 0
        ans.append(tmp_ans)
    print(*ans, sep=' ')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    import sys

    sys.setrecursionlimit(10 ** 5)
    
    def dfs(now: int, glaph: set):
        """nowを現在の頂点として，つながっている頂点をglaphに集合として記録"""
        if seen[now]:
            return glaph
        seen[now] = True
        # print(now, glaph)
        for next in friends[now]:
            glaph.add(now)
            dfs(next, glaph)

    N, M, K = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in [0] * M]
    CD = [tuple(map(int, input().split())) for _ in [0] * K]

    friends = [set() for _ in [0] * (N + 1)]
    for f in AB:
        friends[f[0]].add(f[1])
        friends[f[1]].add(f[0])
    blocks = [set() for _ in [0] * (N + 1)]
    for b in CD:
        blocks[b[0]].add(b[1])
        blocks[b[1]].add(b[0])
    # print(friends)
    # print(blocks)

    friends_chain = []
    seen = [False] * (N + 1)
    for i in range(1, N + 1):
        if not seen[i]:
            glaph = set()
            dfs(i, glaph)
            friends_chain.append(glaph)
    # print(friends_chain)

    ans = [0] * (N + 1)
    for person in range(1, N + 1):
        for chain in friends_chain:
            if person in chain:
                res = set(chain)
                # print(person, res)
                for block in blocks[person]:
                    res.discard(block)
                for friend in friends[person]:
                    res.discard(friend)
                ans[person] = len(res) - 1
                # print(res)
                # print()
    
    for hoge in ans[1:]:
        print(hoge, end=' ')


if __name__ == '__main__':
    main()

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 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())
uf=UnionFind(n)
arr=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int, input().split())
    uf.union(a-1,b-1)
    arr[a-1].append(b-1)
    arr[b-1].append(a-1)
for i in range(k):
    c,d=map(int, input().split())
    arr[c-1].append(d-1)
    arr[d-1].append(c-1)
ans=[0]*n
for i in range(n):
    print(len(list(set(uf.members(i))-set(arr[i])))-1)

Submission status: Time Limit Exceeded

Solution code:
def makeRelation():
  for n in range(1,N+1):
    visited=set((n,))
    D[n].add(n)
    while visited:
      v=visited.pop()
      for i in F[v]:
        if i not in D[n]:
          visited.add(i)
          D[n].add(i)
    for i in D[n]:
      D[i]|=D[n]


def main():
  makeRelation()
  #print(D)
  ans=[0]*(N+1)
  for n in range(1, N+1):
  	ans[n]=len(D[n]) - len(F[n]) - len(D[n]&B[n]) - 1
  print(*ans[1:])


if __name__=='__main__':
  N, M, K = map(int, input().split())
  F=[set() for n in range(N+1)]
  AB=[list(map(int, input().split())) for m in range(M)]
  for a,b in AB:
    F[a].add(b)
    F[b].add(a)
  B=[set() for n in range(N+1)]
  CD=[list(map(int, input().split())) for k in range(K)]
  for c,d in CD:
    B[c].add(d)
    B[d].add(c)
  D=[set() for n in range(N+1)]
  #print(F)
  #print(B)
  main()

Submission status: Time Limit Exceeded

Solution code:
def makeRelation():
  for n in range(1,N+1):
    visited=set((n,))
    D[n].add(n)
    while visited:
      v=visited.pop()
      for i in F[v]:
        if i not in D[n]:
          visited.add(i)
          D[n].add(i)
          #D[i].add(n)


def main():
  makeRelation()
  #print(D)
  ans=[0]*(N+1)
  for n in range(1, N+1):
  	ans[n]=len(D[n]) - len(F[n]) - len(D[n]&set(B[n])) - 1
  print(*ans[1:])


if __name__=='__main__':
  N, M, K = map(int, input().split())
  F=[[] for n in range(N+1)]
  for m in range(M):
    a, b = map(int, input().split())
    F[a]+=[b]
    F[b]+=[a]
  B=[[] for n in range(N+1)]
  for k in range(K):
    c, d = map(int, input().split())
    B[c]+=[d]
    B[d]+=[c]
  D=[set() for n in range(N+1)]
  #print(F)
  #print(B)
  main()

Submission status: Time Limit Exceeded

Solution code:
def makenetwork():
  for n in range(1,N+1):
    visited=set((n,))
    while visited:
      v=visited.pop()
      D[n].append(v)
      for i in F[v]:
        if i not in D[n]:
          visited.add(i)

        
def main():
  makenetwork()
  #print(D)
  ans=[0]*(N+1)
  for n in range(1, N+1):
  	ans[n]=len(D[n]) - len(F[n]) - len(set(D[n])&set(B[n])) - 1
  print(*ans[1:])


if __name__=='__main__':
  N, M, K = map(int, input().split())
  F=[[] for n in range(N+1)]
  for m in range(M):
    a, b = map(int, input().split())
    F[a]+=[b]
    F[b]+=[a]
  B=[[] for n in range(N+1)]
  for k in range(K):
    c, d = map(int, input().split())
    B[c]+=[d]
    B[d]+=[c]
  D=[[] for n in range(N+1)]
  #print(F)
  #print(B)
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


def isFRIEND(a, b):
  return b in F[a] if a in F.keys() else False


def isBLOCK(c,d):
  return d in B[c] if c in B.keys() else False


def isFtoF(a, b, chk):
  #print(chk, a, b)
  chk.append(a)
  if a not in F.keys():
    return False
  for i in F[a]: # search for friends
    if not i in F.keys():
      continue
    if i in chk: # completed
      continue
    if i==b: # Friend to Friend
      return True
    else:
      if isFtoF(i, b, chk):
        return True
  return False


def calc():
  for n1 in range(1,N+1):
    for n2 in range(n1+1,N+1):
      #print(0,n1,n2,D)
      if not isBLOCK(n1,n2) and not isFRIEND(n1,n2) and isFtoF(n1,n2, []):
        D[n1]+=1
        D[n2]+=1


def main():
  calc()
  print(*D[1:])


if __name__=='__main__':
  N, M, K = map(int, input().split())
  F={}
  for m in range(M):
    a, b = map(int, input().split())
    F[a]=F.get(a, []) + [b]
    F[b]=F.get(b, []) + [a]
  B={}
  for k in range(K):
    c, d = map(int, input().split())
    B[c]=B.get(c, []) + [d]
    B[d]=B.get(d, []) + [c]
  D=[0]*(N+1)
  #print(F)
  #print(B)
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

class union_find():
    def __init__(self,n):
        self.n=n
        ##親要素のノード番号を格納。par[x]==xのときそのノードは根
        ##親とはその上にノードなし！！　
        self.par=[-1 for i in range(n)]
        self.rank=[0]*(n)

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

    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)

        ##木の高さを比較し、低い方から高い方へ辺をはる
        if x==y:
          return

        elif self.rank[x]>self.rank[y]:
          self.par[y]=x
        else:
          self.par[x]=y
          ##同じなら片方を伸ばす
          if self.rank[x]==self.rank[y]:
            self.rank[y]+=1

    def same(self,x,y):
        return self.find(x) == self.find(y)
    
    def size(self,x):
      return -self.par[self.find(x)]
      
    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.par) if x<0]
    
    def all_group_member(self):
      return {r:self.members(r) for r in self.roots()}
      
n,m,k=map(int,input().split())
uf=union_find(n)
good=[0 for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
  good[a-1]+=1
  good[b-1]+=1
  
  
ans=[0  for _ in range(n)]
D=list(uf.all_group_member().keys())

for j in D:
  A=uf.all_group_member()[j]
  for h in A:
    ans[h]=j
    
    
bad=[0 for _ in range(n)]
for _ in range(k):
  p,q=map(int,input().split())
  if ans[p-1]==ans[q-1]:
    
    bad[p-1]+=1
    bad[q-1]+=1
  
ans=[0  for _ in range(n)]
D=list(uf.all_group_member().keys())

for j in D:
  A=uf.all_group_member()[j]
  for h in A:
    ans[h]=j
  
ans1=[]
G=Counter(ans)
for u in range(n):
  F=ans[u]
  C=G[F]
  
  ans1.append(str(C-1-bad[u]-good[u]))
  
print(' '.join(ans1))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

class union_find():
    def __init__(self,n):
        self.n=n
        ##親要素のノード番号を格納。par[x]==xのときそのノードは根
        ##親とはその上にノードなし！！　
        self.par=[-1 for i in range(n)]
        self.rank=[0]*(n)

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

    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)

        ##木の高さを比較し、低い方から高い方へ辺をはる
        if x==y:
          return

        elif self.rank[x]>self.rank[y]:
          self.par[y]=x
        else:
          self.par[x]=y
          ##同じなら片方を伸ばす
          if self.rank[x]==self.rank[y]:
            self.rank[y]+=1

    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.par) if x<0]
    
    def all_group_member(self):
      return {r:self.members(r) for r in self.roots()}
      
n,m,k=map(int,input().split())
uf=union_find(n)
good=[0 for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
  good[a-1]+=1
  good[b-1]+=1
  
  
bad=[[]for _ in range(n)]
for _ in range(k):
  p,q=map(int,input().split())
  bad[p-1].append(q-1)
  bad[q-1].append(p-1)
  
ans=[0  for _ in range(n)]
D=list(uf.all_group_member().keys())

for j in D:
  A=uf.all_group_member()[j]
  for h in A:
    ans[h]=j
  
ans1=[]
G=Counter(ans)
for u in range(n):
  F=ans[u]
  C=G[F]
  ch=0
  for T in bad[u]:
    if ans[T]==F:
      ch+=1
  ans1.append(str(C-1-ch-good[u]))
  
print(' '.join(ans1))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

class union_find():
    def __init__(self,n):
        self.n=n
        ##親要素のノード番号を格納。par[x]==xのときそのノードは根
        ##親とはその上にノードなし！！　
        self.par=[-1 for i in range(n)]
        self.rank=[0]*(n)

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

    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)

        ##木の高さを比較し、低い方から高い方へ辺をはる
        if x==y:
          return

        elif self.rank[x]>self.rank[y]:
          self.par[y]=x
        else:
          self.par[x]=y
          ##同じなら片方を伸ばす
          if self.rank[x]==self.rank[y]:
            self.rank[y]+=1

    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.par) if x<0]
    
    def all_group_member(self):
      return {r:self.members(r) for r in self.roots()}
      
n,m,k=map(int,input().split())
uf=union_find(n)
good=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
  good[a-1].append(b-1)
  good[b-1].append(a-1)
  
  
bad=[[]for _ in range(n)]
for _ in range(k):
  p,q=map(int,input().split())
  bad[p-1].append(q-1)
  bad[q-1].append(p-1)
  
ans=[0  for _ in range(n)]
D=list(uf.all_group_member().keys())

for j in D:
  A=uf.all_group_member()[j]
  for h in A:
    ans[h]=j
  
ans1=[]
G=Counter(ans)
for u in range(n):
  F=ans[u]
  C=G[F]
  ch=0
  for T in bad[u]:
    if ans[T]==F:
      ch+=1
  ans1.append(str(C-1-ch-len(good[u])))
  
print(' '.join(ans1))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k=map(int,input().split())
ka=[0]*(n+1)
gu=[[]]
guwk=[]
gur=[0]*(n+1)
gurn=0
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()
hou=[0]*(n+1)
for i in range(1,n+1):
    if hou[i]==0:
        hou[i]=1
        guwk.append(i)
        wk=deque(ab[i])
        while wk:
            tgwk=wk.pop()
            if hou[tgwk]==0:
                guwk.append(tgwk)
                hou[tgwk]=1
            for j in ab[tgwk]:
                if j not in guwk:
                    wwk.append(j)
#                    guwk.append(j)
            if not wk:
                wk=deque(wwk)
                wwk=[]
        gu.append(guwk)
        guwk=[]
    else:
        continue

for i in range(1,len(gu)):
    for j in gu[i]:
        ka[j]=len(gu[i])-len(ab[j])-len(set(cd[j]) & set(gu[i]))-1
for i in range(1,n+1):
    print(ka[i],end=' ')

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int,input().split())
G=[]
F=[set([]) for _ in range(N)]
B=[set([]) for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  F[a-1].add(b)
  F[b-1].add(a)
  p,i=True,0
  for g in G:
    if (a in g or b in g) and p:
      g|={a,b}
      j=i
      p=False
    elif a in g or b in g:
      G[j]|=g|{a,b}
      G.remove(g)
    i+=1
  if p:
    G.append({a,b})
for _ in range(K):
  a,b=map(int,input().split())
  B[a-1].add(b)
  B[b-1].add(a)
ans=[0]*N
for g in G:
  for i in g:
    ans[i-1]=len(g-F[i-1]-B[i-1]-{i})
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int,input().split())
G=[]
F=[set([]) for _ in range(N)]
B=[set([]) for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  F[a-1].add(b)
  F[b-1].add(a)
  p,i=True,0
  for g in G:
    if (a in g or b in g) and p:
      g|={a,b}
      j=i
      p=False
    elif a in g or b in g:
      G[j]|=g|{a,b}
      G.remove(g)
    i+=1
  if p:
    G.append({a,b})
for _ in range(K):
  a,b=map(int,input().split())
  B[a-1].add(b)
  B[b-1].add(a)
ans=[0]*N
for g in G:
  for i in g:
    ans[i-1]=len(g-F[i-1]-B[i-1]-{i})
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

n, m, k = map(int, input().split())
F = [[] for _ in range(n)]
B = [[0] for _ in range(n)]

sys.setrecursionlimit(10**9)

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

rks = [0]*(n)

def dfs(s,r):
    if rks[s] == 0:
        rks[s] = r
    else:
        return
    for i in F[s]:
        dfs(i-1,r)

r = 0
for i in range(n):
    if rks[i] == 0:
        r += 1
        dfs(i,r)

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

counter = Counter(rks)
for i in range(n):
    print(counter[rks[i]] - len(F[i]) - (B[i][0]) - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

n, m, k = map(int, input().split())
F = [[] for _ in range(n+1)]
B = [[] for _ in range(n+1)]

sys.setrecursionlimit(10**9)
for _ in range(m):
    a, b = map(int, input().split())
    F[a].append(b)
    F[b].append(a)

rks = [0]*(n+1)

def dfs(s,r):
    if rks[s] == 0:
        rks[s] = r
    else:
        return
    for i in F[s]:
        dfs(i,r)

r = 0
for i in range(1,n+1):
    if rks[i] == 0:
        r += 1
        dfs(i,r)

for _ in range(k):
    c, d = map(int, input().split())
    if rks[c] == rks[d]:
        B[c].append(d)
        B[d].append(c)

counter = Counter(rks)
for i in range(1,n+1):
    print(counter[rks[i]] - len(F[i]) - len(B[i]) - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter, defaultdict
import sys
n, m, k = map(int, input().split())
F = [[] for _ in range(n+1)]
B = [[] for _ in range(n+1)]

sys.setrecursionlimit(10**9)
for _ in range(m):
    a, b = map(int, input().split())
    F[a].append(b)
    F[b].append(a)

rks = [0]*(n+1)

def dfs(s,r):
    if rks[s] == 0:
        rks[s] = r
    else:
        return
    for i in F[s]:
        dfs(i,r)

r = 0
for i in range(1,n+1):
    if rks[i] == 0:
        r += 1
        dfs(i,r)

for _ in range(k):
    c, d = map(int, input().split())
    if rks[c] == rks[d]:
        B[c].append(d)
        B[d].append(c)

counter = Counter(rks)
for i in range(1,n+1):
    print(counter[rks[i]] - len(F[i]) - len(B[i]) - 1)

Submission status: Time Limit Exceeded

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

def main():
    
    N, M, K = map(int, input().split())
    G = {v: deque([]) for v in range(N)}
    G_original = {v: deque([]) for v in range(N)}
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
        G_original[a].append(b)
        G_original[b].append(a)

    Block = {v: set() for v in range(N)}
    for _ in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        Block[c].add(d)
        Block[d].add(c)

    # seen = [0]*(N)
    stack = []
    color = {v: -1 for v in range(N)}
    col2v = {}
    
    def dfs(j, col):
        if color[j] != -1:
            return
        # seen[j] = 1
        col2v[col] = set()
        stack.append(j)
        color[j] = col
        col2v[col].add(j)
        while stack:
            s = stack[-1]
            if not G[s]:
                stack.pop()
                continue
            g_NO  = G[s].popleft()
            if color[g_NO] != -1:
                continue
            color[g_NO] = col
            col2v[col].add(g_NO)
            # color[g_NO] = 1
            stack.append(g_NO)
        
    c = 0
    for start in range(N):
        if color[start]!=-1:
            continue
        dfs(start, c)
        c += 1
    
    ans = []
    for v in range(N):
        kouho = col2v[color[v]]
        # print(kouho)
        block = Block[v]
        # print(block)
        friend = G_original[v]
        # print(friend)
        tmp = kouho - block - set(friend)
        ans.append(len(tmp)-1)
        
        # print("##############")
    print(*ans)
main()

Submission status: Time Limit Exceeded

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

def main():
    
    N, M, K = map(int, input().split())
    G = {v: deque([]) for v in range(N)}
    G_original = {v: deque([]) for v in range(N)}
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
        G_original[a].append(b)
        G_original[b].append(a)

    Block = {v: deque([]) for v in range(N)}
    for _ in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        Block[c].append(d)
        Block[d].append(c)

    # seen = [0]*(N)
    stack = []
    color = {v: -1 for v in range(N)}
    col2v = {}
    
    def dfs(j, col):
        if color[j] != -1:
            return
        # seen[j] = 1
        col2v[col] = set()
        stack.append(j)
        color[j] = col
        col2v[col].add(j)
        while stack:
            s = stack[-1]
            if not G[s]:
                stack.pop()
                continue
            g_NO  = G[s].popleft()
            if color[g_NO] != -1:
                continue
            color[g_NO] = col
            col2v[col].add(g_NO)
            # color[g_NO] = 1
            stack.append(g_NO)
        
    c = 0
    for start in range(N):
        if color[start]!=-1:
            continue
        dfs(start, c)
        c += 1
    
    ans = []
    for v in range(N):
        kouho = col2v[color[v]]
        # print(kouho)
        block = Block[v]
        # print(block)
        friend = G_original[v]
        # print(friend)
        tmp = kouho.difference(block).difference(friend)
        ans.append(len(tmp)-1)
        
        # print("##############")
    print(*ans)
main()

Submission status: Time Limit Exceeded

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

def main():
    
    N, M, K = map(int, input().split())
    G = {v: deque([]) for v in range(N)}
    G_original = {v: deque([]) for v in range(N)}
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
        G_original[a].append(b)
        G_original[b].append(a)

    Block = {v: deque([]) for v in range(N)}
    for _ in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        Block[c].append(d)
        Block[d].append(c)

    # seen = [0]*(N)
    stack = []
    color = {v: -1 for v in range(N)}
    col2v = {color: set() for color in range(N+4)}
    
    def dfs(j, col):
        if color[j] != -1:
            return
        # seen[j] = 1
        stack.append(j)
        color[j] = col
        col2v[col].add(j)
        while stack:
            s = stack[-1]
            if not G[s]:
                stack.pop()
                continue
            g_NO  = G[s].popleft()
            if color[g_NO] != -1:
                continue
            color[g_NO] = col
            col2v[col].add(g_NO)
            # color[g_NO] = 1
            stack.append(g_NO)
        
    c = 0
    for start in range(N):
        if color[start]!=-1:
            continue
        dfs(start, c)
        c += 1
    
    ans = []
    for v in range(N):
        kouho = col2v[color[v]]
        # print(kouho)
        block = Block[v]
        # print(block)
        friend = G_original[v]
        # print(friend)
        tmp = kouho.difference(block).difference(friend)
        ans.append(len(tmp)-1)
        
        # print("##############")
    print(*ans)
main()

Submission status: Time Limit Exceeded

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

def main():
    
    N, M, K = map(int, input().split())
    G = {v: deque([]) for v in range(N)}
    G_original = {v: deque([]) for v in range(N)}
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
        G_original[a].append(b)
        G_original[b].append(a)

    Block = {v: deque([]) for v in range(N)}
    for _ in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        Block[c].append(d)
        Block[d].append(c)

    # seen = [0]*(N)
    stack = []
    color = {v: -1 for v in range(N)}
    col2v = {color: [] for color in range(N+4)}
    
    def dfs(j, col):
        if color[j] != -1:
            return
        # seen[j] = 1
        stack.append(j)
        color[j] = col
        col2v[col].append(j)
        while stack:
            s = stack[-1]
            if not G[s]:
                stack.pop()
                continue
            g_NO  = G[s].popleft()
            if color[g_NO] != -1:
                continue
            color[g_NO] = col
            col2v[col].append(g_NO)
            # color[g_NO] = 1
            stack.append(g_NO)
        
    c = 0
    for start in range(N):
        if color[start]!=-1:
            continue
        dfs(start, c)
        c += 1

    ans = []
    for v in range(N):
        kouho = col2v[color[v]]
        # print(kouho)
        block = Block[v]
        # print(block)
        friend = G_original[v]
        # print(friend)
        tmp = set(kouho).difference(block).difference(friend)
        ans.append(len(tmp)-1)
        
        # print("##############")
    print(*ans)
main()