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())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

F = [[[] for _ in range(2)] for _ in range(N)]
for m in AB:
    F[m[0] - 1][0].append(m[1] - 1)
    F[m[1] - 1][0].append(m[0] - 1)
for k in CD:
    F[k[0] - 1][1].append(k[1] - 1)
    F[k[1] - 1][1].append(k[0] - 1)

for i in range(N):
    c = 0
    d = [0] * N
    d[i] = 1
    Q = deque()
    Q.append(i)
    while len(Q) > 0:
        q = Q.pop()
        for j in range(len(F[q][0])):
            a = F[q][0][j]
            if d[a] == 1:
                continue
            d[a] = 1
            c += 1
            Q.append(a)
    for j in range(len(F[i][1])):
        a = F[i][1][j]
        if d[a] == 1:
            c -= 1            
    print(c -len(F[i][0]), end=' ')

print('')

Submission status: Time Limit Exceeded

Solution code:
def BFS(x):
  cnt=1
  v=deque([x])
  k=0
  zu[x]=k
  lis=[x]
  
  while len(v)>0:
    a=v.popleft()
    for i in fr[a]:
      if zu[i]==-1:
        zu[i]=zu[a]+1
        v.append(i)
        cnt += 1
        lis.append(i)
          
  return lis

##############################

from collections import deque
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K
fr=[ [] for _ in range(N)]
bl=[ set() for _ in range(N)]
zu=[ -1 for _ in range(N)] #訪問済みリスト

for i in range(M):
  A[i],B[i]= map(int,input().split())
  fr[A[i]-1].append(B[i]-1)
  fr[B[i]-1].append(A[i]-1)
for k in range(K):
  C[k],D[k]= map(int,input().split())
  bl[C[k]-1].add(D[k]-1)
  bl[D[k]-1].add(C[k]-1)
    
size=[0]*N
pena=[0]*N
for i in range(N):
  if zu[i]==-1:
    kumi=BFS(i) #リスト
    for k in range(len(kumi)):
      size[kumi[k]]=len(kumi)
      for l in range(len(kumi)):
        if l==k:
          pass
        else:
          if (kumi[l] in bl[kumi[k]]) or (kumi[l] in fr[kumi[k]]):
            #print(kumi[k],kumi[l],bl[kumi[k]],fr[kumi[k]])
            pena[kumi[k]] += 1
#print(size)
#print(pena)
ans=[]
for i in range(N):
  ans.append(size[i]-pena[i]-1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def BFS(x):
  cnt=0
  v=deque([x])
  zu=[ -1 for _ in range(N)] #訪問済みリスト
  k=0
  zu[x]=k
  
  while len(v)>0:
    a=v.popleft()
    for i in fr[a]:
      if zu[i]==-1:
        zu[i]=zu[a]+1
        v.append(i)
        if zu[i]>1 and (i not in bl[x]):
          cnt +=1            
  return cnt

##############################

from collections import deque
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K
fr=[ [] for _ in range(N)]
bl=[ set() for _ in range(N)]

for i in range(M):
  A[i],B[i]= map(int,input().split())
  fr[A[i]-1].append(B[i]-1)
  fr[B[i]-1].append(A[i]-1)
for k in range(K):
  C[k],D[k]= map(int,input().split())
  bl[C[k]-1].add(D[k]-1)
  bl[D[k]-1].add(C[k]-1)

ans=[]  
for i in range(N):
  ans.append(BFS(i))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

class UnionFind():
    def __init__(self, n):      #初期化
        self.n = n
        # 親
        self.parents = [i for i in range(n)]
        # 木の深さ
        self.ranks = [0] * n
        # グループの要素数
        self.sizes = [1] * n

    def find(self, x):          #親を出力
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.ranks[x] < self.ranks[y]:
            self.parents[x] = y
            self.sizes[y] += self.sizes[x]
        else:
            self.parents[y] = x
            self.sizes[x] += self.sizes[y]
            if self.ranks[x]==self.ranks[y]:
                self.ranks[x] += 1

    def same(self, x, y):       #xとyが同じグループかどうか
        return self.find(x) == self.find(y)

    def members(self, x):       #xと同じグループの要素
        root = self.find(x)
        return {i for i in range(self.n) if self.find(i) == root}

    def size(self, x):          #グループの要素数
        root = self.find(x)
        return self.sizes[root]

    def roots(self):            #親の要素一覧
        return {i for i, x in enumerate(self.parents) if i == x}

    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 = map(int, input().split())
    uf = UnionFind(N)
    dic = {i:set([i]) for i in range(N)}

    for i in range(M):
        a,b = map(int,input().split())
        uf.unite(a-1, b-1)
        dic[a-1].add(b-1)
        dic[b-1].add(a-1)

    for j in range(K):
        a,b = map(int,input().split())
        dic[a-1].add(b-1)
        dic[b-1].add(a-1)

    ret = [len(uf.members(i) - dic[i]) for i in range(N)]
    print(" ".join(map(str,ret)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def BFS(x):
  cnt=0
  v=deque([x])
  zu=[ -1 for _ in range(N)] #訪問済みリスト
  k=0
  zu[x]=k
  
  while len(v)>0:
    a=v.popleft()
    for i in fr[a]:
      if zu[i]==-1:
        zu[i]=zu[a]+1
        v.append(i)
        if zu[i]>1 and (i not in bl[x]):
          cnt +=1            
  return cnt

##############################

from collections import deque
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K
fr=[ [] for _ in range(N)]
bl=[ [] for _ in range(N)]

for i in range(M):
  A[i],B[i]= map(int,input().split())
  fr[A[i]-1].append(B[i]-1)
  fr[B[i]-1].append(A[i]-1)
for k in range(K):
  C[k],D[k]= map(int,input().split())
  bl[C[k]-1].append(D[k]-1)
  bl[D[k]-1].append(C[k]-1)

ans=[]  
for i in range(N):
  ans.append(BFS(i))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

class UnionFind():
    def __init__(self, n):      #初期化
        self.n = n
        # 親
        self.parents = [i for i in range(n)]
        # 木の深さ
        self.ranks = [0] * n
        # グループの要素数
        self.sizes = [1] * n

    def find(self, x):          #親を出力
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.ranks[x] < self.ranks[y]:
            self.parents[x] = y
            self.sizes[y] += self.sizes[x]
        else:
            self.parents[y] = x
            self.sizes[x] += self.sizes[y]
            if self.ranks[x]==self.ranks[y]:
                self.ranks[x] += 1

    def same(self, x, y):       #xとyが同じグループかどうか
        return self.find(x) == self.find(y)

    def members(self, x):       #xと同じグループの要素
        root = self.find(x)
        return {i for i in range(self.n) if self.find(i) == root}

    def size(self, x):          #グループの要素数
        root = self.find(x)
        return self.sizes[root]

    def roots(self):            #親の要素一覧
        return {i for i, x in enumerate(self.parents) if i == x}

    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 = map(int, input().split())
    uf = UnionFind(N)
    dic = {i:set([i]) for i in range(N)}

    for i in range(M):
        a,b = map(int,input().split())
        uf.unite(a-1, b-1)
        dic[a-1].add(b-1)
        dic[b-1].add(a-1)

    for j in range(K):
        a,b = map(int,input().split())
        dic[a-1].add(b-1)
        dic[b-1].add(a-1)

    ret = [None]*N
    for i in range(N):
        cnt = 0
        for x in uf.members(i):
            cnt += not x in dic[i]
        ret[i]=cnt
    print(" ".join(map(str,ret)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M, K = map(int, input().split())

friend_graph = [set() for _ in range(N)]
block_graph = [set()for _ in range(N)]

#group = [set() for _ in range(N)]
group_label = [ 0 for _ in range(N)]

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

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

label_num = 1
old_set = set()
for i in range(N):
    if i in old_set:
        pass
    else:
        #print("group", group)
        que = deque([i])
        while que:
            now = que.popleft()
            #group[i].add(now)
            group_label[now] = label_num
            old_set.add(now)
            for j in friend_graph[now]:
                #if j in group[i]:
                if group_label[j] == 0:
                    #pass
                #else:
                    que.append(j)
        label_num += 1

#print("friend", friend_graph)
#print("group", group)

for i in range(N):
    #ans = len(group[i]) - len(friend_graph[i]) - 1
    ans = len([j for j,x in enumerate(group_label) if x == group_label[i]]) - len(friend_graph[i]) - 1
    for j in block_graph[i]:
        if j in [j for j,x in enumerate(group_label) if x == group_label[i]]:
            ans -= 1
    print(ans, end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M, K = map(int, input().split())

friend_graph = [set() for _ in range(N)]
block_graph = [set()for _ in range(N)]

#group = [set() for _ in range(N)]
group_label = [ 0 for _ in range(N)]

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

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

label_num = 1
for i in range(N):
    if group_label[i] != 0:
        pass
    else:
        #print("group", group)
        que = deque([i])
        while que:
            now = que.popleft()
            #group[i].add(now)
            group_label[now] = label_num
            for j in friend_graph[now]:
                #if j in group[i]:
                if group_label[j] == 0:
                    #pass
                #else:
                    que.append(j)
        label_num += 1

#print("friend", friend_graph)
#print("group", group)

for i in range(N):
    #ans = len(group[i]) - len(friend_graph[i]) - 1
    ans = len([j for j,x in enumerate(group_label) if x == group_label[i]]) - len(friend_graph[i]) - 1
    for j in block_graph[i]:
        if j in [j for j,x in enumerate(group_label) if x == group_label[i]]:
            ans -= 1
    print(ans, end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M, K = map(int, input().split())

friend_graph = [set() for _ in range(N)]
block_graph = [set()for _ in range(N)]

group = [set() for _ in range(N)]


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

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

for i in range(N):

    #print("group", group)
    que = deque([i])
    while que:
        now = que.popleft()
        group[i].add(now)
        for j in friend_graph[now]:
            if j in group[i]:
                pass
            else:
                que.append(j)

#print("friend", friend_graph)
#print("group", group)

for i in range(N):
    ans = len(group[i]) - len(friend_graph[i]) - 1
    for j in block_graph[i]:
        if j in group[i]:
            ans -= 1
    print(ans, end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M, K = map(int, input().split())

friend_graph = [set() for _ in range(N)]
block_graph = [set()for _ in range(N)]

group = [set() for _ in range(N)]


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

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

for i in range(N):

    #print("group", group)
    que = deque([i])
    while que:
        now = que.popleft()
        group[i].add(now)
        for j in friend_graph[now]:
            if j in group[i]:
                pass
            else:
                que.append(j)

#print("friend", friend_graph)
#print("group", group)


ans_str = ''
for i in range(N):
    ans = len(group[i]) - len(friend_graph[i]) - 1
    for j in block_graph[i]:
        if j in group[i]:
            ans -= 1
    ans_str  = ans_str  + str(ans)+ ' '

print(ans_str)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

friends = [[0] * n for _ in range(n)]

blocks = [[0] * n for _ in range(n)]

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

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

for i in range(n):
    q = deque()
    q.append(i)
    cnt = [-1] * n
    cnt[i] = 0
    total = 0
    while q:
        k = q.popleft()
        for j in range(n):
            if friends[k][j] and cnt[j] == -1:
                q.append(j)
                cnt[j] = cnt[k] + 1
                if cnt[j] > 1 and not blocks[i][j]:
                    total += 1
    print(total)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k=map(int,input().split())
fre=[[]for _ in range(n)]
blo=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    fre[a-1].append(b-1)
    fre[b-1].append(a-1)
for i in range(k):
    c,d=map(int,input().split())
    blo[c-1].append(d-1)
    blo[d-1].append(c-1)

for i in range(n):
    l=deque([i])
    ans=0
    cnt=[0]*n
    cnt[i]=1
    for b in blo[i]:
        cnt[b]=-1
    while l:
        now=l.popleft()
        for to in fre[now]:
            if cnt[to]==0:
                cnt[to]=1
                l.append(to)
                ans+=1
            if cnt[to]==-1:
                l.append(to)
    ans-=len(fre[i])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
n, m, k = map(int, input().split())
friends = defaultdict(list)
block = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    friends[a].append(b)
    friends[b].append(a)
for _ in range(k):
    c, d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)
#print(friends)
#print(block)

roopname = []
roop = defaultdict(list)
seen = [0]*n


for i in range(n):
    if not seen[i]==0:
        continue
    seen[i] = i+1
    roopname.append(i+1)
    roop[i+1].append(i+1)
    queue = deque(friends[i+1])
    while queue:
        p = queue.popleft()
        if  not seen[p-1]==0:continue
        seen[p-1] = i+1
        roop[i+1].append(p)
        for j in friends[p]:
            if seen[j-1]==0:
                queue.append(j)
#print(roopname)
#print(roop)
#print(seen)
ans = []
for i in range(n):
    fsum = 0
    for j in friends[i+1]:
        if j in roop[seen[i]]:
            fsum += 1
            
    bsum = 0
    for j in block[i+1]:
        if j in roop[seen[i]]:
            bsum += 1
    
    ans.append(len(roop[seen[i]])-bsum-fsum-1)

L=[str(a) for a in ans]
L=" ".join(L)
print(L)

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 ''.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(n)

from collections import defaultdict
direct_f = defaultdict(set)
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    direct_f[a].add(b)
    direct_f[b].add(a)
    uf.union(a, b)
brock = defaultdict(set)
for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    brock[c].add(d)
    brock[d].add(c)
print(*[uf.size(i) - len(direct_f[i]) - len(set(uf.members(i))&brock[i])-1 for i in range(n)])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m, k = map(int, read().split())
    friend = [[] for _ in range(n)]
    block = [set() for _ in range(n)]
    potential = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        friend[a].append(b)
        friend[b].append(a)
    for _ in range(k):
        c, d = [int(i) - 1 for i in read().split()]
        block[c].add(d)
        block[d].add(c)
    sd = set()
    for u in range(n):
        if u in sd:
            continue
        sn = deque([u])
        pf = set()
        while sn:
            p = sn.pop()
            if p in sd:
                continue
            sd.add(p)
            pf.add(p)
            for f in friend[p]:
                sn.append(f)
        for pfi in pf:
            potential[pfi] = pf
    print(*[len(potential[i] - block[i]) - len(friend[i]) - 1 for i in range(n)])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m, k = map(int, read().split())
    friend = [set() for _ in range(n)]
    block = [set() for _ in range(n)]
    potential = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        friend[a].add(b)
        friend[b].add(a)
    for _ in range(k):
        c, d = [int(i) - 1 for i in read().split()]
        block[c].add(d)
        block[d].add(c)
    sd = set()
    for u in range(n):
        if u in sd:
            continue
        sn = deque([u])
        pf = set()
        while sn:
            p = sn.pop()
            if p in sd:
                continue
            sd.add(p)
            pf.add(p)
            for f in friend[p]:
                sn.append(f)
        for pfi in pf:
            potential[pfi] |= pf
    print(*[len(potential[i] - friend[i] - block[i] - {i}) for i in range(n)])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m, k = map(int, read().split())
    friend = [set() for _ in range(n)]
    block = [set() for _ in range(n)]
    potential = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        friend[a].add(b)
        friend[b].add(a)
    for _ in range(k):
        c, d = [int(i) - 1 for i in read().split()]
        block[c].add(d)
        block[d].add(c)
    sd = set()
    for u in range(n):
        if u in sd:
            continue
        sn = [u]
        pf = set()
        while sn:
            p = sn.pop()
            if p in sd:
                continue
            sd.add(p)
            pf.add(p)
            for f in friend[p]:
                sn.append(f)
        for pfi in pf:
            potential[pfi] |= pf
    print(*[len(potential[i] - friend[i] - block[i] - {i}) for i in range(n)])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m, k = map(int, read().split())
    friend = [set() for _ in range(n)]
    block = [set() for _ in range(n)]
    potential = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        friend[a].add(b)
        friend[b].add(a)
    for _ in range(k):
        c, d = [int(i) - 1 for i in read().split()]
        block[c].add(d)
        block[d].add(c)
    sd = set()
    for u in range(n):
        sn = [u]
        pf = set()
        while sn:
            p = sn.pop()
            if p in sd:
                continue
            sd.add(p)
            pf.add(p)
            for f in friend[p]:
                sn.append(f)
        for pfi in pf:
            potential[pfi] |= pf
    print(*[len(potential[i] - friend[i] - block[i] - {i}) for i in range(n)])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
friends = {i: set() for i in range(1, n + 1)}
blocks = {i: set() for i in range(1, n + 1)}
candidates = {i: set() for i in range(1, n + 1)}
nums = []
for _ in range(m):
    a, b = map(int, input().split())
    friends[a].add(b)
    friends[b].add(a)
for _ in range(k):
    a, b = map(int, input().split())
    blocks[a].add(b)
    blocks[b].add(a)

def dfs(a):
    visited = [0] * n
    visited[a - 1] = 1
    if len(friends[a]) == 0:
        return
    q = list(friends[a])
    while q:
        next = q.pop()
        visited[next - 1] = 1
        for i in friends[next]:
            if visited[i - 1] == 0:
                q.append(i)
                if i not in friends[a]:
                    candidates[a].add(i)

for i in range(1, n + 1):
    dfs(i)
    b = set(blocks[i])
    c = set(candidates[i])
    nums.append(len((b | c) - b))
print(*nums)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import copy
sys.setrecursionlimit(200000)
N,M,K=list(map(int,input().split()))
counter=[[None,None] for i in range(N+1)]
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color :
            friend_tansaku(i,friend)





for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):

    color =set()
    if counter[i][0] is None:
        friend_tansaku(i,i)
        cnt=len(color)
        color=tuple(color)
        for aa in color:
            counter[aa]=[color,cnt]
    color,cnt =set(counter[i][0]),counter[i][1]
    for k in block_list[i]:
        if k not in color:
            cnt+=1

    count=cnt-(len(friend_list[i])+len(block_list[i]))-1
    if i==N:print(count)
    else:print(count,end=" ")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import copy
sys.setrecursionlimit(200000)
N,M,K=list(map(int,input().split()))
counter=[None]*(N+1)
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color :
            friend_tansaku(i,friend)





for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):

    color =set()
    if counter[i] is None:
        friend_tansaku(i,i)
        for aa in color:
            counter[i]=tuple(color)
    color =set(counter[i])
    for k in block_list[i]:
        color.add(k)
    count=len(color)-(len(friend_list[i])+len(block_list[i]))-1
    if i==N:print(count)
    else:print(count,end=" ")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import copy
sys.setrecursionlimit(200000)
N,M,K=list(map(int,input().split()))
counter=[None]*(N+1)
friend_list=[[] for _ in range(N+1)]
block_list=[[] for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color :
            friend_tansaku(i,friend)





for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].append(b)
   friend_list[b].append(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].append(b)
    block_list[b].append(a)
for i in range(1,N+1):
    color =set()
    if counter[i] is None:
        friend_tansaku(i,i)
        for j in color:
            counter[j]=copy.copy(color)
    color =counter[i]
    for k in block_list[i]:
        color.add(k)
    count=len(color)-(len(friend_list[i])+len(block_list[i]))-1
    if i==N:print(count)
    else:print(count,end=" ")

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

for a, b in ab:
    uf.union(a-1, b-1)
     
ans = [len(uf.members(i))-1 for i in range(N)]
    
for a, b in ab:
    if(uf.same(a-1, b-1)):
        ans[a-1] -= 1
        ans[b-1] -= 1
    
for c, d in cd:
    if(uf.same(c-1, d-1)):
        ans[c-1] -= 1
        ans[d-1] -= 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# import sys
# import math
# import itertools
# from collections import deque
# from collections import defaultdict
# import heapq
# import copy
# import bisect
# import numpy as np
# from scipy.special import comb

# def my_input(): return sys.stdin.readline().rstrip()
# sys.setrecursionlimit(100000)
# INF = 1001001001001
# MOD = 1000000007

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 = map(int, input().split())

    uf = UnionFind(N)
    friends = [set() for _ in range(N)]

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

    blocks = [set() for _ in range(N)]
    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c - 1, d - 1
        if uf.same(c, d):
            blocks[c] |= set([d])
            blocks[d] |= set([c])

    # print(uf)
    # print(friends)
    # print(blocks)

    for i in range(N - 1):
        ans = uf.size(i) - 1 - len(friends[i]) - len(blocks[i])
        print(str(ans) + " ", end="")

    ans = uf.size(N - 1) - 1 - len(friends[N - 1]) - len(blocks[N - 1])
    print(ans)


if __name__ == '__main__':
    main()