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:
#!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(M):
        ai, bi = iim()
        if ai > bi:
            ai, bi = bi, ai
        join(ai, bi)
        mk.add((ai, bi))
    for i in range(K):
        ai, bi = iim()
        if ai > bi:
            ai, bi = bi, ai
        mk.add((ai, bi))

    ans = [0] * (N+1)
    #print(S)
    for i in range(1, N+1):
        aa = 0
        for j in range(i+1, N+1):
            if (i, j) in mk:
                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:
# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import connected_components
from scipy.sparse import lil_matrix
import collections

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

friend_mtx = lil_matrix((n, n))

friend_cnt = dict()
blocked_cnt = dict()

for i in range(m):
    a, b = map(int, input().split())
    friend_mtx[a-1, b-1] = 1
    friend_mtx[b-1, a-1] = 1
    if a-1 in friend_cnt:
        friend_cnt[a-1] = friend_cnt[a-1] + 1
    else:
        friend_cnt[a-1] = 1
    if b-1 in friend_cnt:
        friend_cnt[b-1] = friend_cnt[b-1] + 1
    else:
        friend_cnt[b-1] = 1

csr_mtx = friend_mtx.tocsr()
num, labels = connected_components(csr_mtx)

for i in range(k):
    c, d = map(int, input().split())
    if labels[c-1] == labels[d-1]:
        if c-1 in blocked_cnt:
            blocked_cnt[c-1] = blocked_cnt[c-1] + 1
        else:
            blocked_cnt[c-1] = 1
        if d-1 in blocked_cnt:
            blocked_cnt[d-1] = blocked_cnt[d-1] + 1
        else:
            blocked_cnt[d-1] = 1

renketsu_cnt = collections.Counter(labels)

for i in range(n):
    i_label = labels[i]
    renketsu_cnt_i = renketsu_cnt[i_label]
    num_friend = 0
    if i in friend_cnt:
        num_friend = friend_cnt[i]
    num_blocked = 0
    if i in blocked_cnt:
        num_blocked = blocked_cnt[i]
    print(renketsu_cnt_i - num_friend - num_blocked - 1, end="")
    if i != (n-1):
        print(' ', end="")
    else:
        print()

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)

result = []
for i in range(N):
    total = 0
    for m in uf.members(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:
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
import collections
N,M,K = map(int,input().split())
G = [[0 for i in range(N)] for j in range(N)]
ans=[0 for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  G[a-1][b-1]=1;G[b-1][a-1]=1
  ans[a-1]-=1;ans[b-1]-=1
  
a = np.array(G)
n, labels = connected_components(a)
c = collections.Counter(labels)

for i in range(N):
  ans[i]+=c[labels[i]]-1
  
for i in range(K):
  c,d=map(int,input().split())
  c-=1;d-=1
  if labels[c]==labels[d]:
    ans[c]-=1;ans[d]-=1
for i in range(N):
  print(ans[i],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()}

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

    u = UnionFind(n)

    ans = [0 for i in range(n)]

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

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


    for y in u.all_group_members().values():
        x = len(y)
        for j in y:
            ans[j] += x - 1


    print(" ".join(map(str, ans)))

main()

Submission status: Time Limit Exceeded

Solution code:
class Person:
    def __init__(self, i):
        self.friends = set()
        self.blocks = set()
        self.index = i


def list_nets(persons, visited, current):
    visited.append(current)
    for p in persons[current].friends:
        if p not in visited:
            list_nets(persons, visited, p)


def main():
    N, M, K = map(int, input().split())
    persons = [Person(i) for i in range(N)]

    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        persons[a].friends.add(b)
        persons[b].friends.add(a)
    for i in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        persons[c].blocks.add(d)
        persons[d].blocks.add(c)

    result = []
    for p in persons:
        visited = list()
        list_nets(persons, visited, p.index)
        f = list(filter(lambda x: x not in p.blocks, visited))
        f = list(filter(lambda x: x not in p.friends, f))
        result.append(str(len(f) - 1))

    print(' '.join(result))

    return 0


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10**6)
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
from pprint import pprint

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, sys.stdin.readline().strip().split())
friends_set = [set() for _ in range(N)]
block_set = [set() for _ in range(N)]

uf = UnionFind(N)

for _ in range(M):
    a, b = map(int, sys.stdin.readline().strip().split())
    uf.union(a-1, b-1)
    friends_set[a-1].add(b-1)
    friends_set[b-1].add(a-1)

for _ in range(K):
    c, d = map(int, sys.stdin.readline().strip().split())
    block_set[c-1].add(d-1)
    block_set[d-1].add(c-1)

# print(uf)
for i in range(N):
    n = uf.find(i)
    # print(len(uf.members(n)), len(friends_set[i]), len(block_set[i]))
    # print(uf.members(n), friends_set[i], block_set[i])
    print(len(set(uf.members(n)) - set([i]) - friends_set[i] - block_set[i]), end = " ")

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F



def make_cluster(N, friend):
    import queue
    C = []
    already = [False] * N
    for i in range(N):
        if already[i]:
            continue
        already[i] = True
        s = {i}
        q = queue.Queue()
        q.put(i)
        while not q.empty():
            k = q.get()
            out = friend[k]
            for l in out:
                if already[l]:
                    continue
                s.add(l)
                q.put(l)
                already[l] = True
        C.append(s)

    return C


def main():
    import queue
    N, M, K = read_values()

    friend = [set() for _ in range(N)]
    for _ in range(M):
        a, b = read_index()
        friend[a].add(b)
        friend[b].add(a)
    
    block = [set() for _ in range(N)]
    for _ in range(K):
        a, b = read_index()
        block[a].add(b)
        block[b].add(a)

    already = [False] * N
    C = [0] * N
    for i in range(N):
        if already[i]:
            continue
        s = {i}
        q = queue.Queue()
        already[i] = True
        q.put(i)
        while not q.empty():
            k = q.get()
            out = friend[k]
            for l in out:
                if already[l]:
                    continue
                s.add(l)
                q.put(l)
                already[l] = True
        for j in s:
            C[j] = len(s.difference(block[j]))
    res = [str(C[i] - len(friend[i]) - 1) for i in range(N)]
    print(" ".join(res))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100001)
N, M, K = map(int, input().split())

All = set()
F_candidate = [0] * N
F, B = {}, {}
for i in range(N):
    F[i] = set()
    B[i] = set()
    All.add(i)

for _ in range(M):
    x, y = map(int, input().split())
    F[x - 1].add(y - 1)
    F[y - 1].add(x - 1)

for _ in range(K):
    x, y = map(int, input().split())
    B[x - 1].add(y - 1)
    B[y - 1].add(x - 1)


def dfs(v, visited):

    visited.add(v)

    for n in F[v]:
        if n in visited:
            continue
        dfs(n, visited)


for i in range(N):

    if i in All:
        C = set()   # connected graph
        dfs(i, C)
        All = All - C
        for j in C:
            D = C - {j}
            D = D - B[j]
            D = D - F[j]
            F_candidate[j] = len(D)

for i in range(N):
    print(F_candidate[i], end='')
    if i != N - 1:
        print(' ', end='')
    else:
        print('')

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
        self.group = [set([i]) for i in range(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
        self.group[x] = self.group[x] | self.group[y]
    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())
u = UnionFind(n+1)
li = []
adjacent_list = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    u.union(a,b)
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
    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):
    ans_li[i] += u.size(u.find(i))
    group = u.group[u.find(i)]
    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:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d=[float("inf")]*n #各頂点への距離
    used=[False]*n
    d[s]=0
    
    while True:
        v=-1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v==-1): #その頂点が使われたかチェック
                v=i			            #まだなら仮確定
            elif (not used[i]) and d[i]<d[v]: #より距離が近いのがあればそちらから
                v=i
        if v==-1:
             break
        used[v]=True
               
        for j in range(n):
            d[j]=min(d[j],d[v]+cost[v][j])
    return d

################################
def main():
    n,m,k=map(int,input().split()) #n:頂点数　m:辺の数 k:ブロック関係の数

    cost=[[float("inf") for i in range(n)] for i in range(n)] 
    #cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
    block=[[None for i in range(n)] for i in range(n)] 
    for i in range(m): #友人関係
        x,y=map(int,input().split())
        cost[x-1][y-1]=1
        block[x-1][y-1]=True
        cost[y-1][x-1]=1
        block[y-1][x-1]=True

    for i in range(k): #ブロック関係
        x,y=map(int,input().split())
        block[x-1][y-1]=False
        block[y-1][x-1]=False

    ans=[]
    for i in range(n):
        dijk=dijkstra(i,n,m,cost)
        for x,j in enumerate(block[i]): #blockから各リスト取り出す
            if j==False or j==True:
                dijk[x]=0
        cnt=0
        for i in dijk:
            if i>0 and i!=float('inf'):
                cnt+=1
        ans.append(cnt)
    print(*ans)

if __name__ =="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
N, M, K = map(int, input().split())
tomodachi  = [ [i] for i in range(N+1)]
for _ in range(M):
  a, b  = map(int, input().split())
  tomodachi[a].append(b)
  tomodachi[b].append(a)
dupli = copy.deepcopy(tomodachi)

for n in range(1, N+1):
  kouho = set()
  for friend in tomodachi[n]:
    if friend == n:
      continue
    else:
      kouho.add(friend)
  while kouho:
    f = kouho.pop()
    for g in tomodachi[f]:
      if g in tomodachi[n]:
        continue
      else:
        kouho.add(g)
        tomodachi[n].append(g)


for _ in range(K):
  c, d  = map(int, input().split())
  if c in tomodachi[d]:
    tomodachi[d].remove(c)
    tomodachi[c].remove(d)

ans = [ str(len(t)-len(s)) for s, t in zip(dupli[1:], tomodachi[1:]) ]
print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

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

es_friend = [[False for _ in range(N)] for _ in range(N)]
es_block = [[False for _ in range(N)] for _ in range(N)]

for i in range(M):
    uf_friend.union(AB[i][0]-1, AB[i][1]-1)
    es_friend[AB[i][0]-1][AB[i][1]-1] = True
    es_friend[AB[i][1]-1][AB[i][0]-1] = True
for i in range(K):
    es_block[CD[i][0]-1][CD[i][1]-1] = True
    es_block[CD[i][1]-1][CD[i][0]-1] = True

ans = [0 for _ in range(N)]
for root in uf_friend.roots():
    m = uf_friend.members(root)
    l = len(uf_friend.members(root))
    for i in range(l):
        for j in range(i+1, l):
            if es_friend[m[i]][m[j]] == es_block[m[i]][m[j]] == False:
                ans[m[i]] += 1
                ans[m[j]] += 1
print(" ".join(list(map(str, ans))))

Submission status: Time Limit Exceeded

Solution code:
# UnionFindでつなげていく
# [所属する木の頂点数]-[1（自分）]-[自分とブロック関係にある人の数]

# UnionFind
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 show_parents(self):
      print(self.parents)

# ここまでUnionFind
N,M,K=map(int,input().split())

UF=UnionFind(N)
from collections import defaultdict
dic=defaultdict(set)
friends=defaultdict(set)
for i in range(M):
  a,b=map(int,input().split())
  UF.union(a-1,b-1)
  friends[a-1].add(b-1)
  friends[b-1].add(a-1)

for i in range(N):
  dic[UF.find(i)].add(i)

block=defaultdict(set)
for i in range(K):
  c,d=map(int,input().split())
  block[c-1].add(d-1)
  block[d-1].add(c-1)

# UF.show_parents()
# 同じ木に所属する人数のうち、ブロック関係にない人数
ans=[0]*N
for i in range(N):
  candi=dic[UF.find(i)]
  #print("i",candi,"block",block[i])
  ans[i]=max(len(candi-friends[i]-block[i])-1,0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M, K = (int(i) for i in input().split())
    par = [i for i in range(N)]
    rank = [0 for i in range(N)]

    def find_root(x):
        if par[x] == x:
            return x
        else:
            par[x] = find_root(par[x])
            return par[x]

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    fre = [set() for _ in range(N)]
    blo = [set() for _ in range(N)]
    mem = {i for i in range(N)}
    for i in [0]*M:
        a, b = (int(i) for i in input().split())
        fre[a-1].add(b-1)
        fre[b-1].add(a-1)
        unite(a-1, b-1)
    for i in [0]*K:
        a, b = (int(i) for i in input().split())
        blo[a-1].add(b-1)
        blo[b-1].add(a-1)
    for i in range(N):
        cur = 0
        for j in mem - fre[i] - {i} - blo[i]:
            if is_same_group(i, j):
                cur += 1
        print(cur, end=" ")
    print()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.ranks = [0] * 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.ranks[x] < self.ranks[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x]+=1

        # 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 tup(a,b):
    return (min(a,b),max(a,b))

def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    friends = set()
    group = UnionFind(N)
    for i in range(M):
        friends.add(tup(A[i]-1,B[i]-1))
        group.union(A[i]-1,B[i]-1)
    for i in range(K):
        friends.add(tup(C[i]-1,D[i]-1))
    result = ""
    isFirst = True
    roots = group.roots()
    rootSets = {r: set() for r in roots }
    for i in range(N):
        r = group.find(i)
        rootSets[r].add(i)
    for i in range(N):
        c = 0
        r = group.find(i)
        for g in rootSets[r]:
            if g != i and tup(i,g) not in friends:
                c+= 1
        if not isFirst:
            result+=" "
        else:
            isFirst = False
        result+=str(c)
    print(result)
    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]

    def root(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return False
        self.parent[ry] = rx
        return True


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

uf = UnionFind(N)

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

# root num
friend = [set() for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    AB[a].add(a)
    AB[a].add(b)
    AB[b].add(a)
    AB[b].add(b)
    ra = uf.root(a)
    rb = uf.root(b)
    uf.unite(a, b)
    friend[ra].add(a)
    friend[ra].add(b)
    friend[ra] = friend[ra] | friend[rb]

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

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

res = [0 for _ in range(N)]
for i in range(N):
    tmp = friend[uf.root(i)] - AB[i]
    tmp = tmp - CD[i]
    res[i] = len(tmp)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

N, M, K = map(int, input().split())
# F = [list(map(int, input().split())) for _ in range(M)]
# B = [list(map(int, input().split())) for _ in range(K)]

F = defaultdict(set)
for _ in range(M):
    u, v = map(int, input().split())
    F[u].add(v)
    F[v].add(u)
B = defaultdict(set)
for _ in range(K):
    u, v = map(int, input().split())
    B[u].add(v)
    B[v].add(u)

res = []
for i in range(N):
    cand = 0
    visited = [0]*N
    q = deque()
    q.append((i+1, 0))
    visited[i] = 1

    while q:
        curNode, lv = q.popleft()
        for node in F[curNode]:
            if visited[node-1] == 0:
                visited[node-1] = 1
                q.append((node, lv+1))
                if lv >= 1 and i+1 not in B[node]:
                    cand += 1

    res.append(cand)

print(' '.join(map(str, res)))