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
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        self.roots = [{i} for i in range(size)]
    def getRootID(self, i):
        r = self.roots[i]
        if isinstance(r, set):
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return len(self.getGroupSet(i))
    def getGroupSet(self, i):
        return self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] |= self.roots[r2]
        self.roots[r2] = r1
        return True

def main():
    N,M,K=mis()
    uf = UnionFindEx(N)
    frs = tuple(set() for _ in range(N))
    bls = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = mis()
        uf.connect(a-1, b-1)
        frs[a-1].add(b-1)
        frs[b-1].add(a-1)
    for _ in range(K):
        a, b = mis()
        bls[a-1].add(b-1)
        bls[b-1].add(a-1)
    print(*(len(uf.getGroupSet(i) - frs[i] - bls[i]) - 1 for i in range(N)))


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra

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

friend = np.array([[0 for i in range(n)] for j in range(n)])
for i in range(n):
  friend[i][i] = 0

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

dist = dijkstra(friend)

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

ans = np.sum((dist < 10 ** 10) & (dist > 1), axis = 1)

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

Submission status: Time Limit Exceeded

Solution code:
import collections

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

friends = collections.defaultdict(set)

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

    friends[a].add(b)
    friends[b].add(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] = set(result)

blocks = collections.defaultdict(set)

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

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


import itertools

new_friends = collections.OrderedDict({i: 0 for i in range(1, N+1)})

for combi in itertools.combinations(range(1, N+1), 2):
    if combi[0] in friends[combi[1]] or combi[0] in blocks[combi[1]]:
        continue

    if combi[0] in exist_path[combi[1]]:
        new_friends[combi[0]] += 1
        new_friends[combi[1]] += 1

print(*new_friends.values())

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

class UnionFind(object):
    "https://www.kumilog.net/entry/union-find"
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

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


uf = UnionFind(N)
fr = {}
for _ in range(M):
    a, b = map(int, input().split(" "))
    a -= 1
    b -= 1
    uf.union(a, b)
    if fr.get(a) is not None:
        fr[a] += 1
    else:
        fr[a] = 1

    if fr.get(b) is not None:
        fr[b] += 1
    else:
        fr[b] = 1

bl = {}
for _ in range(K):
    c, d = map(int, input().split(" "))
    c -= 1
    d -= 1
    if not uf.is_same(c, d):
        continue

    if bl.get(c) is not None:
        bl[c] += 1
    else:
        bl[c] = 1

    if bl.get(d) is not None:
        bl[d] += 1
    else:
        bl[d] = 1


for i in range(N):
    s = uf.get_size(i) - 1

    s -= bl.get(i, 0)

    s -= fr.get(i, 0)
    print(s)

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

uf = UnionFind(N)
for a, b in friends:
    uf.union(a-1, b-1)

ans = ""
for i in range(N):
    count = 0
    for c in uf.members(i):
        if {i+1, c+1} not in friends and {i+1, c+1} not in blocks and i != c:
            count += 1
    ans += str(count) + " "
print(ans.strip())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N, M, K  = (int(i) for i in input().split())
graph = [[0] * (N+1) for i in range(N+1)]
graph2 = [[0] * (N+1) for i in range(N+1)]

#ABC = [[int(i) for i in input().split()] for i in range(N)]
for i in range(M):
    A, B =  (int(i) for i in input().split())
    graph[A][B] = 1
    graph[B][A] = 1
    graph2[A][B] = 1
    graph2[B][A] = 1

for j in range(K):
    A, B =  (int(i) for i in input().split())
    graph2[A][B] = -1
    graph2[B][A] = -1

graph = np.array(graph)
#print(graph)
#print(graph2)
n, labels = connected_components(graph)

#print(n)
# 2
#print(labels)

for i in range(1, N+1):
    count = 0
    for j in range(1,N+1):
        if i == j:
            continue
        if graph2[i][j] == 0 and labels[i] == labels[j]:
            #print(i, j)
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    AB = [tuple(map(int, ab)) for ab in map(str.split, args[1:1+m])]
    CD = [tuple(map(int, cd)) for cd in map(str.split, args[1+m:1+m+k])]

    friends = [set() for _ in range(n+1)]
    blocked = [set() for _ in range(n+1)]

    for a, b in AB:
        friends[a].add(b)
        friends[b].add(a)

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

    ret = [0]*(n+1)
    for a in range(1, n+1):
        checked = set((a,))
        stack = list(friends[a])
        while stack:
            b = stack.pop()
            if b in checked:
                continue

            checked.add(b)
            if b not in blocked[a] and b not in friends[a]:
                ret[a] += 1

            stack.extend(friends[b])

    return ' '.join(map(str, ret[1:]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, M, K = map(int, input().split())

# 人iの友達関係リスト
set_Friend = [set() for i in range(N)]
for j in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  set_Friend[A].add(B)
  set_Friend[B].add(A)

# 人iのブロック関係リスト
set_Block = [set() for i in range(N)]
for j in range(K):
  C, D = map(int, input().split())
  C -= 1
  D -= 1
  set_Block[C].add(D)
  set_Block[D].add(C)

# 友達関係による連結成分
cluster_id = 0
clusters = []
clustering = [-1 for i in range(N)]
remaining_user = N
for i in range(N):
  if clustering[i]!=-1:
    continue
  cluster_prev = set([i])
  cluster_diff = set([i])
  while len(cluster_diff)>0:
    cluster_next = set()
    for j in cluster_diff:
      cluster_next = cluster_next | set_Friend[j]
    cluster_diff = cluster_next - cluster_prev
    cluster_prev = cluster_next | cluster_prev
  for k in cluster_prev:
    clustering[k] = cluster_id
  clusters.append(cluster_prev)
  remaining_user -= len(cluster_prev)
  if remaining_user==0:
    break
  cluster_id += 1

# 友達候補の人数を計算して出力
for i in range(N):
  id = clustering[i]
  print(len(clusters[id]-set_Friend[i]-set_Block[i]-set([i])), end='')
  if i<N-1:
    print(' ', end='')

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(50000)
from collections import defaultdict

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

con = defaultdict(list)
block = defaultdict(set)
friend = defaultdict(set)
for _ in range(M):
    A, B = list(map(int, input().split()))
    con[A].append(B)
    con[B].append(A)
    friend[A].add(B)
    friend[B].add(A)
for _ in range(K):
    C, D = list(map(int, input().split()))
    block[C].add(D)
    block[D].add(C)

visited = set()
group = defaultdict(set)

def dfs(node, visited, key):
    if node in visited:
        return
    group[key].add(node)
    visited.add(node)
    for next in con[node]:
        if next not in visited:
            dfs(next, visited, key)


for i in range(1, N + 1):
    dfs(i, visited, i)

ret = {}
for g in group.values():
    if not g:
        continue
    size = len(g)
    for node in g:
        exclude = 0
        for blocked in block[node]:
            if blocked in g:
                exclude += 1
        for friended in friend[node]:
            if friended in g:
                exclude += 1
        ret[node - 1] = size - exclude - 1

for i in range(N):
    print(ret.get(i, 0), end='')
    if i != N - 1:
        print(' ', end='')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000000)
N,M,K=map(int,input().split())
F=[set() for i in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    F[a-1].add(b-1)
    F[b-1].add(a-1)
B=[set() for i in range(N)]
for _ in range(K):
    c,d=map(int,input().split())
    B[c-1].add(d-1)
    B[d-1].add(c-1)

def dps(i, j, c, fr, bl):
    s=0
    con=False
    for f in F[j]:
        if f not in c:
            con=True
            c.add(f)
            if f not in fr and f not in bl:
                s+=1
            s+=dps(i,f,c, fr, bl)
    if not con:
        return 0
    else:
        return s
for i in range(0,N):
    checked=set([i])
    print(dps(i, i, checked, F[i], B[i]), end=" ")

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
        self.group = [set() for _ 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

    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)
        if not self.group[root]:
            for i in range(self.n):
                if self.find(i) == root:
                    self.group[root].add(i)
        return self.group[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 main():
    N, M, K = map(int, input().split())
    friends = [set() for _ in range(N)]
    block = [set() for _ in range(N)]
    uni = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        friends[A].add(B)
        friends[B].add(A)
        uni.union(A,B)
 
    for _ in range(K):
        C, D = map(int, input().split())
        C -= 1
        D -= 1
        block[C].add(D)
        block[D].add(C)
    
    ans = [0] * N
    for i in range(N):
        ans[i] = len((uni.members(i) - friends[i]) - block[i]) - 1
 
    print(*ans)
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    N, M, K = map(int, input().split())
    ans = [0] * N
    table = [[] for i in range(N)]
    visited = [0] * N
    block = [[] for i in range(N)]

    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        table[a].append(b)
        table[b].append(a)
    for i in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        block[c].append(d)
        block[d].append(c)

    for i in range(N):
        if visited[i] == 0:
            Q = deque()
            Q.append(i)
            visited[i] = 1
            group = deque()
            group.append(i)
            while Q:
                x = Q.popleft()
                for y in table[x]:
                    if visited[y] == 0:
                        Q.append(y)
                        visited[y] = 1
                        group.append(y)
            n = len(group)
            for i in range(n):
                x = group[i]
                ans[x] += n - len(table[x]) - 1
                for j in range(i + 1, n):
                    y = group[j]
                    if y in block[x]:
                        ans[x] -= 1
                        ans[y] -= 1
    print(" ".join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n, m, k = list(map(int, input().split()))
ab_list = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    ab_list[a-1][b-1] = 1
    ab_list[b-1][a-1] = 1
cd_list = [set() for _ in range(n)]
for _ in range(k):
    c, d = list(map(int, input().split()))
    cd_list[c-1].add(d)
    cd_list[d-1].add(c)

csr = csr_matrix(ab_list)
shortest = shortest_path(csr, method='J', directed=False)

result = [0 for _ in range(n)]

for i in range(1, n+1):
    count = 0
    for j, ele in enumerate(shortest[i-1]):
        if i == j+1 or ele == np.inf or ele == 1:
            continue
        if j+1 not in cd_list[i-1]:
            count += 1
    result[i-1] = count

print(' '.join(str(ele) for ele in result))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

def root(uft, x):
    if uft[x] == x: return x
    uft[x] = root(uft, uft[x])
    return uft[x]

def union(uft, x, y):
    x = root(uft, x)
    y = root(uft, y)
    if x == y:
        return
    uft[x] = y

def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(set)
    block = defaultdict(set)
    group = defaultdict(set)
    uft = [i for i in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        friend[a].add(b)
        friend[b].add(a)
    for j in range(k):
        c, d = map(int, input().split())
        block[c].add(d)
        block[d].add(c)
    for i in range(1, n+1):
        for j in friend[i]:
            union(uft, j, i)
    for i in range(1, n+1):
        group[root(uft, i)].add(i)
    return ' '.join(str(len(group[uft[i]]-block[i])-len(friend[i])-1) for i in range(1, n+1))

print(answer())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
import queue
import numpy as np
import sys
input = sys.stdin.readline
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)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(b)
    dic[str(b)].append(a)
seen = set()
def BFS(dic,node):
    cc = set()
    q = queue.Queue()
    q.put(node)
    cc.add(node)
    while not q.empty():
        now_node = q.get()
        cc.add(now_node)
        target = set(dic[str(now_node)]) - cc
        for tgt in target:
            q.put(tgt)
    return cc
c_comp=np.zeros((N),dtype='int32')
len_ls = []
var = 1
for i in range(1,N+1):
    if c_comp[i-1] == 0:
        # 連結判定
        tmp = BFS(dic,i)
        c_comp[np.array(list(tmp))-1] = var
        len_ls.append(len(tmp)-1)
        var += 1

for (a,b) in cd:
    if c_comp[a-1] == c_comp[b-1]:
        dic[str(a)].append(b)
        dic[str(b)].append(a)
res = [len_ls[c_comp[i]-1] - len(dic[str(i+1)]) for i in range(N)]
print(*res)

Submission status: Time Limit Exceeded

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

graph = [[] for _ in range(n + 1)]
friends = [set() for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    friends[a].add(b)
    friends[b].add(a)

block = [set() for _ in range(n + 1)]

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

def dfs(graph, start):
    visited = set([start])
    stack = []
    for f in graph[start]:
        stack.append(f)
    can_reach = set()
    while stack:
        friend = stack.pop()
        visited.add(friend)
        candidates = graph[friend]
        for c in candidates:
            if c not in visited:
                if c not in block[start] and c not in friends[start]:
                    can_reach.add(c)
                stack.append(c)
    return can_reach

ans = []
for i in range(1, n + 1):
    c = dfs(graph, i)
    ans.append(len(c))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N,M,K = MI()
	frend = [[] for _ in range(N)]
	block = [[] for _ in range(N)]
	for _ in range(M):
		A,B = map(int1, sys.stdin.readline().split())
		frend[A].append(B)
		frend[B].append(A)
	group = []
	que = deque()
	cnt = 0
	N_ch = [-1]*N
	g = -1
	while cnt < N:
		i = N_ch.index(-1)
		que.append(i)
		g+=1
		N_ch[i]=g
		group.append(0)
		while len(que)>0:
			i = que[-1]
			cnt += 1
			que.pop()
			group[g]+=1
			fr = frend[i]
			for f in fr:
				if(N_ch[f]==-1):
					que.appendleft(f)
					N_ch[f]=g

	for _ in range(K):
		C,D = map(int1, sys.stdin.readline().split())
		if(N_ch[C]==N_ch[D]):
			block[C].append(D)
			block[D].append(C)

	ans_v = []
	for i in range(N):
		ans = group[N_ch[i]]-len(frend[i])-len(block[i])
		ans_v.append(ans-1)
	printH(ans_v)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

n,m,k= map(int, input().split())
a= [list(map(int, input().split())) for i in range(m)]
c= [list(map(int, input().split())) for i in range(k)]

x= [[] for i in range(n)] # 友達関係のグラフ
y= [[] for i in range(n)] # ブロック関係のグラフ


for i in range(m):
    x[a[i][0]-1].append(a[i][1]-1)
    x[a[i][1]-1].append(a[i][0]-1)

for i in range(k):
    y[c[i][0]-1].append(c[i][1]-1)
    y[c[i][1]-1].append(c[i][0]-1)



# ユニオンファインド
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

uf=UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1,a[i][1]-1)

ans=[]
for i in range(n):
    ans.append(uf.size(i)-len(x[i])-len(set(uf.members(i))&set(y[i]))-1)

print(*ans)

Submission status: Time Limit Exceeded

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

class UnionFind():
    """ Union-Find木の実装（ランクあり） """
    def __init__(self, n):
        self.n = n
        self.parent = [-1]*(n+1)    # parent 親
        self.rank   = [0]*(n+1)     # rank 深さ

    def root(self, x):
        """ 木の根を求める """
        if self.parent[x] < 0:      # xが根
            return x
        else:
            self.parent[x] = self.root(self.parent[x])  # 経路圧縮
            return self.parent[x]
            
    def unite(self, x, y):
        """ xとyの属する集合を併合 """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return 0
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def isSame(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.root(x) == self.root(y) or x==y

N, M, K = map(int, input().split())
friend = [[0]*N for _ in range(N)]
block = [[0]*N for _ in range(N)]
uf = UnionFind(N)
for i in range(M):
    A, B = map(int, input().split())
    friend[A-1][B-1] = 1
    friend[B-1][A-1] = 1
    uf.unite(A-1, B-1)
for j in range(K):
    C, D = map(int, input().split())
    block[C-1][D-1] = 1
    block[D-1][C-1] = 1

for i in range(N):
    ans = 0
    for j in range(N):
        if i == j:
            continue
        elif uf.isSame(i,j) and friend[i][j] == 0 and block[i][j] == 0:
            ans += 1
    print(ans, end= ' ')

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

def main():
    N, M, K = map(int, input().split())
    friend_or_block = [set() for _ in range(N+1)]
    friendsGroup = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        friendsGroup.union(a, b)
        friend_or_block[a].add(b)
        friend_or_block[b].add(a)

    for _ in range(K):
        c, d = map(int, input().split())
        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:
N,M,K = map(int,input().split())
d = [[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  d[a][b] = 1
  d[b][a] = 1
for i in range(N):
  d[i][i] = 0
for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][j],d[i][k]+d[k][j])
for i in range(K):
  c,e = map(int,input().split())
  c -= 1
  e -= 1
  d[c][e] = float('inf')
  d[e][c] = float('inf')
ans =[]
for i in range(N):
  cnt = 0
  for j in range(N):
    if i != j and d[i][j] > 1 and d[i][j] != float('inf'):
      cnt += 1
  ans.append(cnt)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys

readline = sys.stdin.buffer.readline


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ 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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


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

    E = UnionFind(N)

    for a, b in AB:
        a -= 1
        b -= 1
        E.unite(a, b)

    for i in range(N):
        E.find(i)

    ans = [0 for _ in range(N)]
    for i, j in itertools.combinations(list(range(N)), 2):
        if i != j:
            if E.same(i, j):
                ans[i] += 1
                ans[j] += 1

    for i, j in CD:
        i -= 1
        j -= 1
        if E.same(i, j):
            ans[i] -= 1
            ans[j] -= 1
    for i, j in AB:
        i -= 1
        j -= 1
        ans[i] -= 1
        ans[j] -= 1

    print(*ans)


main()