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:
import sys
def input(): return sys.stdin.readline().rstrip()

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

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



def main():
    N, M, K = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(M)]
    CD = [tuple(map(int, input().split())) for _ in range(K)]

    friend_or_block = [set() for _ in range(N+1)]
    friendsGroup = UnionFind(N)
    for a, b in AB:
        friendsGroup.union(a, b)
        friend_or_block[a].add(b)
        friend_or_block[b].add(a)

    for c, d in CD:
        friend_or_block[c].add(d)
        friend_or_block[d].add(c)

    ans = [0] * (N + 1)
    for i in range(1, N+1):
        ans[i] = len([v for v in friendsGroup.members(i) if v not in friend_or_block[i]]) - 1
    print(*ans[1:])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m,k = map(int, input().split())
class UnionFind:
    def __init__(self, n):
        #親ノードの番号を格納
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)
        self.group = [set([i]) for i in range(n)]
    def find(self, x):
        #根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self, x, y):
        #同じかどうかの確認
        return self.find(x) == self.find(y)
    def union(self, x, y):
        #統合する
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
            self.group[y] = self.group[x] | self.group[y]

        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            self.group[x] = self.group[x] | self.group[y]

        else:
            self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            self.group[x] = self.group[x] | self.group[y]

    def getsize(self, x):
        p = self.find(x)
        return self.size[p]
u = UnionFind(n+1)
li = []
for i in range(m):
    a, b = map(int, input().split())
    u.union(a,b)
    li.append([a,b])
for i in range(k):
    a,b = map(int, input().split())
    li.append([a,b])
li.sort()
index = 0
ans_li = [-1 for i in range(n+1)]
for i in range(1,n+1):
    p = u.find(i)
    ans_li[i] += len(u.group[p])
    group = u.group[p]
    while index < k+m and li[index][0] == i:
        if li[index][1] in group:
            ans_li[i] -= 1
            ans_li[li[index][1]] -= 1
        index += 1
for i in range(1,n+1):
    print(ans_li[i], end = " ")

Submission status: Time Limit Exceeded

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

s = [['0' for i in range(n)] for j in range(n)]
t = [[False for i in range(n)] for j in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    s[a-1][b-1] = 'f' # 友達(frend)
    s[b-1][a-1] = 'f'
    t[a-1][b-1] = True
    t[b-1][a-1] = True

for i in range(k):
    a, b = map(int, input().split())
    s[a-1][b-1] = 'b' # ブロック(brock)
    s[b-1][a-1] = 'b'

for i in range(n):
    s[i][i] = 'm' # i am

for aa  in range(n):
    for i in range(n):
        for j in range(n):
            if s[i][j] == 'f':
                for x in range(n):
                    if t[x][i]: t[x][j] = True

for i in range(n):
    ans = 0
    for j in range(n):
        if s[i][j] == '0' and t[i][j]: ans += 1
    if i != n - 1:
        print(ans, '', end='')
    else:
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

from bisect import bisect

def resolve():
    def find(i):
        x = S[i]
        while True:
            k = S[i][0]
            if k == i:
                x[0] = i
                return i
            S[i] = x
            i = k
    def join(i, j):
        ai = find(i)
        aj = find(j)
        if ai != aj:
            #S[aj][0] = S[ai][0]
            S[aj] = S[ai]
    def same(i, j):
        ai = find(i)
        aj = find(j)
        return ai == aj

    N, M, K = iim()
    S = [[i] for i in range(N+1)]
    mk = [set() for i in range(N+1)]
    for i in range(M):
        ai, bi = iim()
        if ai > bi:
            ai, bi = bi, ai
        join(ai, bi)
        mk[ai].add(bi)
    for i in range(K):
        ai, bi = iim()
        if ai > bi:
            ai, bi = bi, ai
        mk[ai].add(bi)

    ans = [0] * (N+1)
    #print(S)
    for i in range(1, N):
        aa = 0
        mki = mk[i]
        for j in range(i+1, N+1):
            if j in mki:
                continue
            if same(i, j):
                ans[i] += 1
                ans[j] += 1
    print(*ans[1:])


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
A = set([tuple(map(int, input().split())) for _ in range(M)])
C = set([tuple(map(int, input().split())) for _ in range(K)])
tmpX = set()

def mySearch(i):
  global tmpX
  tmp = set()
  for a in A:
    if a[0] == i:
      if a[1] not in tmpX:
        tmp.add(a[1])
    elif a[1] == i:
      if a[0] not in tmpX:
        tmp.add(a[0])
  tmpX = tmpX | tmp
  for t in tmp:
    mySearch(t)

def main():
  global tmpX
  ans = [None]*N
  
  for i in range(N):
    tomo = set()
    for a in A:
      if a[0] == i+1:
        tomo.add(a[1])
      elif a[1] == i+1:
        tomo.add(a[0])
        
    block = set()
    for c in C:
      if c[0] == i+1:
        block.add(c[1])
      elif c[1] == i+1:
        block.add(c[0])
    
    tmpX = set()
    mySearch(i+1)
    ans[i] = len(tmpX - tomo - block - set([i+1]))
  print(*ans)
  
main()

Submission status: Time Limit Exceeded

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

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())
	#S=input().rstrip()
	#N=int(input())
	#vA=list(map(int,input().split()))
	vAB=[tuple(map(int,input().split()))
		 for _ in [0,]*M]
	vCD=[tuple(map(int,input().split()))
		 for _ in [0,]*K]
	
	uf = UnionFind(N)
	vF = [set() for _ in [0,]*N] # friend
	vB = [set() for _ in [0,]*N] # block
	
	for a,b in vAB:
		uf.union(a-1,b-1)
		vF[a-1] |= {b-1}
		vF[b-1] |= {a-1}
	
	for c,d in vCD:
		vB[c-1] |= {d-1}
		vB[d-1] |= {c-1}
	
	#vR = [uf.size(i)-1-vF[i]-vB[i]
	#      for i in range(N)]
	
	vR = []
	for i in range(N):
		g = uf.size(i)
		gm = uf.members(i)
		sgm = set(gm)
		#f = sum(gmm in vF[i] for gmm in gm)
		#b = sum(gmm in vB[i] for gmm in gm)
		f = sum(ff in sgm for ff in vF[i])
		b = sum(bb in sgm for bb in vB[i])
		
		vR.append(g - 1 - f - b)
		
	print(*vR)
	
main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
 
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        return len(self.roots())
 
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
 
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
 
N, M, K = map(int, input().split())
F = [input().split() for i in range(M)]
bdict = {}
for i in range(K):
  a,b = map(int,input().split())
  a = a - 1
  b = b - 1
  if a not in bdict:
    bdict[a] = set()
  if b not in bdict:
    bdict[b] = set()
  bdict[a].add(b)
  bdict[b].add(a)
u = UnionFind(N)
 
fdict = {}
for f in F:
  a = int(f[0])-1
  b = int(f[1])-1
  u.union(a, b)
  if a not in fdict:
    fdict[a] = set()
  if b not in fdict:
    fdict[b] = set()
  fdict[a].add(b)
  fdict[b].add(a)
ans = ""
for i in range(N):
  mems = set(u.members(i))
  bnum = 0
  if i in bdict:
    for b in bdict[i]:
      if b in mems:
        bnum += 1
  if i in fdict:
    fnum = len(fdict[i])
  else:
    fnum = 0
  ans += str(len(mems) -1-fnum-bnum) + " "
print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
# Code for D - Friend Suggestions
# Use input() to fetch data from STDIN

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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

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

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

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

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

[N, M, K] = [int(x) for x in input().split()]
A = []
B = []
C = []
D = []

blockHash = {}
friendHash = {}

for i in range(M):
    [x, y] = [int(x) for x in input().split()]
    A.append(x)
    B.append(y)

    friendHash[(x, y)] = True
    friendHash[(y, x)] = True

for i in range(K):
    [x, y] = [int(x) for x in input().split()]
    C.append(x)
    D.append(y)

    blockHash[(x, y)] = True
    blockHash[(y, x)] = True

uf = UnionFind(N)
for x, y in zip(A, B):
    uf.union(x-1, y-1)

groups = {}
for i in range(N):
    j = uf.find(i)
    groups[j] = groups.get(j, [])
    groups[j].append(i)

result = []
for i in range(N):
    total = 0
    for m in groups.get(uf.find(i), []):
        if i == m:
            continue
        if not blockHash.get(( i + 1, m + 1 ), False) and not friendHash.get(( i + 1, m + 1 ), False):
            total += 1
    result.append(str( total ))

print(" ".join(result))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N, M, K = map(int, input().split())
    fri = [[] for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        fri[a-1].append(b-1)
        fri[b-1].append(a-1)
    blo = [[] for _ in range(N)]
    for i in range(K):
        c, d = map(int, input().split())
        blo[c-1].append(d-1)
        blo[d-1].append(c-1)

    can = [[] for _ in range(N)]
    for i in range(N):
        vis = [False for _ in range(N)]
        s = [i]
        while len(s) > 0:
            v = s.pop()
            vis[v] = True
            for j in fri[v]:
                if vis[j]:
                    continue
                s.append(j)
                if j not in fri[i] and j not in blo[i] and j not in can[i]:
                    can[i].append(j)
    ans = []
    for i in range(N):
        ans.append(len(can[i]))
    print(*ans, sep=' ')
resolve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from collections import deque, defaultdict
import bisect
from math import factorial


def update_cluster(cluster, cluster_index, a, b):
    remain_index = cluster[a]
    delete_index = cluster[b]
    if remain_index == delete_index:
        return

    if len(cluster_index[remain_index]) < len(cluster_index[delete_index]):
        remain_index, delete_index = delete_index, remain_index

    movers = cluster_index[delete_index]
    for mover in movers:
        cluster[mover] = remain_index
    cluster_index[remain_index] |= movers

    del cluster_index[delete_index]


def find_connected(node, edges, visited):
    visited.add(node)

    connected = edges[node] - visited
    for c in connected:
        connected_nodes = find_connected(c, edges, visited)
        for n in connected_nodes:
            visited.add(n)
    return visited


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

    blocks = defaultdict(set)
    cluster = {i+1: i+1 for i in range(N)}
    cluster_index = {i+1: set([i+1]) for i in range(N)}

    for _ in range(M):
        a, b = map(int, input().split())
        update_cluster(cluster, cluster_index, a, b)
        blocks[a].add(b)
        blocks[b].add(a)

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

    friends = []
    for p, index in cluster.items():
        candidates = cluster_index[index]
        num = len(candidates - blocks[p]) - 1
        friends.append(str(num))

    print(" ".join(friends))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/bin/bash
import sys
from copy import deepcopy


def _ia(offset=0): return [int(x) + offset for x in sys.stdin.readline().strip().split()]


def main():
    n, m, k = _ia()
    ab = [set([i]) for i in range(n)]
    for _ in range(m):
        i, j = _ia(-1)
        ab[i].add(j)
        ab[j].add(i)
    cd = [set() for _ in range(n)]
    for _ in range(k):
        i, j = _ia(-1)
        cd[i].add(j)
        cd[j].add(i)

    flag = [[False] * n for _ in range(n)]
    for i in range(n):
        flag[i][i] = True
    p = deepcopy(ab)
    for _ in range(17):
        for i, pi in enumerate(p):
            if len(pi) == n: continue
            for j in list(pi):
                if flag[i][j]: continue
                pi |= p[j]

    for i in range(n):
        p[i] -= cd[i]
        p[i] -= ab[i]
    return " ".join(map(str, [len(pi) for pi in p]))


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import collections

import queue

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

friends = collections.defaultdict(list)

for i in range(M):
    a, b = map(int, input().split())

    friends[a].append(b)
    friends[b].append(a)

exist_path = {}

def width_first(neighbor, start):
    visited = []
    queue = []
    queue.append(start)
    result = []
    while len(queue) > 0:
        next_city = queue.pop(0)
        if next_city in visited:
            continue
        result.append(next_city)
        visited.append(next_city)
        for nei in neighbor[next_city]:
            queue.append(nei)
    return result


for i in range(1, N+1):
    result = width_first(friends, i)
    exist_path[i] = result

blocks = collections.defaultdict(list)

for i in range(K):
    a, b = map(int, input().split())

    blocks[a].append(b)
    blocks[b].append(a)


import itertools

combis = list(itertools.combinations(range(1, N+1), 2))

new_friends = collections.defaultdict(int)

for combi in combis:
    if combi[0] in friends[combi[1]] or combi[0] in blocks[combi[1]]:
        continue

    # flag = 0
    # for i in range(min(combi[0], combi[1]), max(combi[0], combi[1])):
    #     if i+1 not in friends[i]:
    #         flag = 1
    #         break
    # if not flag:
    if combi[0] in exist_path[combi[1]]:
        new_friends[combi[0]] += 1
        new_friends[combi[1]] += 1

ans = []
for i in range(N):
    if i+1 in new_friends:
        ans.append(new_friends[i+1])
    else:
        ans.append(0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
 
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        return len(self.roots())
 
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
 
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
 
N, M, K = map(int, input().split())
F = [input().split() for i in range(M)]
bdict = {}
for i in range(K):
  a,b = map(int,input().split())
  a = a - 1
  b = b - 1
  if a not in bdict:
    bdict[a] = set()
  if b not in bdict:
    bdict[b] = set()
  bdict[a].add(b)
  bdict[b].add(a)
u = UnionFind(N)
 
fdict = {}
for f in F:
  a = int(f[0])-1
  b = int(f[1])-1
  u.union(a, b)
  if a not in fdict:
    fdict[a] = set()
  if b not in fdict:
    fdict[b] = set()
  fdict[a].add(b)
  fdict[b].add(a)
ans = ""
for i in range(N):
  mems = set(u.members(i))
  if i in bdict:
    mems = mems - bdict[i]
  if i in fdict:
    fnum = len(fdict[i])
  else:
    fnum = 0
  ans += str(len(mems) -1-fnum) + " "
print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

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 and not i in self.block[x] and not i in self.friend[x]]

    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 = LI()
    uf = UnionFind(N)
    G = [[] for _ in range(N)]
    block = [set() for _ in range(N)]
    friend = [set() for _ in range(N)]

    for _ in range(M):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)
        uf.union(a, b)
        friend[a].add(b)
        friend[b].add(a)

    for _ in range(K):
        a, b = LI_()
        block[a].add(b)
        block[b].add(a)
    ans = [0 for _ in range(N)]
    for i in range(N):
        q = [i]
        visited = [0 for _ in range(N)]
        visited[i] = 1
        _ans = 0
        while q:
            v = q.pop()
            for next_v in G[v]:
                if visited[next_v]:
                    continue
                if next_v in block[i] or next_v in friend[i]:
                    pass
                else:
                    _ans += 1
                visited[next_v] = 1
                q.append(next_v)
        ans[i] = _ans
    for i in range(N):
        print(ans[i], end=' ')
    print()

    '''
    uf.block = block
    uf.friend = friend
    for i in range(N):
        print(len(uf.members(i)) - 1, end=' ')
    print()
    '''
main()

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

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

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

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

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


n, m, k = map(int, input().split())
friend = UnionFind(n)
dataf = [set() for _ in range(n)]
datab = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    dataf[a-1].add(b-1)
    dataf[b-1].add(a-1)
    friend.union(a-1, b-1)

for _ in range(k):
    a, b = map(int, input().split())
    datab[a-1].add(b-1)
    datab[b-1].add(a-1)

for i in range(n):
    kouho = set(friend.members(i))
    print(len(kouho-dataf[i]-datab[i])-1, end=' ')

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1] * (n + 1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0] * (n + 1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if (self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if (x == y):
            return
            # 違う木に属していた場合rnkを見てくっつける方を決める
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if (self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


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

    def roots(self):
        return [i for i, x in enumerate(self.root) 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())

uf = UnionFind(n)
fd = dict()
directcount = [0] * n

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

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

res = [0] * n
ures = uf.all_group_members()

for k in ures:
    cnt = len(ures[k]) - 1
    for node in ures[k]:
        res[node] = cnt - directcount[node]

for i in range(len(blist)):
    c, d = blist[i]
    if uf.isSameGroup(c, d):
        res[c] -= 1
        res[d] -= 1

#print(directcount)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, M, K = map(int, input().split())
F = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(M)]
B = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(K)]


class DisjointSet():
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, 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 = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


d = DisjointSet(N)
friends = defaultdict(list)
for Ai, Bi in F:
    d.unite(Ai, Bi)
    friends[Ai].append(Bi)
    friends[Bi].append(Ai)
group = defaultdict(int)
for i in range(N):
    group[d.find(i)] |= 1 << i
blocking = defaultdict(int)
for Ci, Di in B:
    blocking[Ci] |= 1 << Di
    blocking[Di] |= 1 << Ci

ans = [0] * N
for i in range(N):
    bit_g = group[d.find(i)] & ~blocking[i]
    while bit_g:
        ans[i] += bit_g & 1
        bit_g >>= 1
    ans[i] -= len(friends[i]) + 1
print(' '.join(list(map(str, ans))))