Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class Graph:
    # n is the number of N
    # E is a set of edges where each edge is a two tuple (u, v)
    def __init__(self, n, E):
        self.N = n # number of vertices
        self.V = list(range(0, n)) # V = [0, 1, ..., n-1]
        self.AL = [set() for i in range(n)] # adjacency list
        for e in E:
            self.add_edge(e[0], e[1])

    def add_edge(self, u, v): # u is head, v is tail
        self.AL[u].add(v)
        self.AL[v].add(u)

# 入力
N, M, K = [int(x) for x in input().split()]
Ef = [-1] * M
Eb = [-1] * K

for i in range(M):
    Ef[i] = [int(x) - 1 for x in input().split()]

for i in range(K):
    Eb[i] = [int(x) - 1 for x in input().split()]

Gf = Graph(N, Ef)   # 友達
Gb = Graph(N, Eb)   # ブロック
ans = [0] * N
visited = [False] * N

for root in range(N):
    if visited[root]: continue
    que = deque()
    que.append(root)
    tree_nodes = set()

    while len(que) > 0:
        u = que.pop()
        visited[u] = True
        tree_nodes.add(u)
        
        for v in Gf.AL[u]:
            if visited[v] or v in que:
                continue
            que.append(v)

    for v in tree_nodes:
        ans[v] = max(0, len(tree_nodes) - 1 - len(Gb.AL[v] & tree_nodes)- len(Gf.AL[v]))

print(" ".join([str(f) for f in ans]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy

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())
UF = UnionFind(N+1)
direct_connect = [0]*(N+1)
for _ in range(M):
  a, b = map(int, input().split())
  UF.union(a, b)
  direct_connect[a] += 1
  direct_connect[b] += 1
for _ in range(K):
  a, b = map(int, input().split())
  if UF.same(a, b):
    direct_connect[a] += 1
    direct_connect[b] += 1
ans = ""
for i in range(1, N+1):
  ans += "%d "%(UF.size(i)-direct_connect[i]-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited


if __name__ == "__main__":
    n, m, k = map(int, input().split())
    AB = [map(int, input().split()) for _ in range(m)]
    CD = [map(int, input().split()) for _ in range(k)]

    graph_f = defaultdict(set)
    graph_b = defaultdict(set)

    for a, b in AB:
        graph_f[a - 1].add(b - 1)
        graph_f[b - 1].add(a - 1)

    for c, d in CD:
        graph_b[c - 1].add(d - 1)
        graph_b[d - 1].add(c - 1)

    searched = set()
    conns = []
    for i in range(n):
        if i not in searched:
            conn = dfs(graph_f, i)
            searched |= conn
            conns.append(conn)

    res = [0] * n
    for conn in conns:
        for i in conn:
            res[i] = len(conn - graph_f[i] - graph_b[i]) - 1

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

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 = list(map(int, input().split()))
from collections import defaultdict

fr_bl = defaultdict(set)
ans = [0] * n
uf = UnionFind(n+1)


for _ in range(1, m+1):
    a, b = list(map(int, input().split()))
    fr_bl[a].add(b)
    fr_bl[b].add(a)
    uf.union(a, b)
for _ in range(1, k+1):
    c, d = list(map(int, input().split()))
    fr_bl[c].add(d)
    fr_bl[d].add(c)


# print(fr_bl)
# print(uf)

for i in range(1, n+1):
    # fr_bl[i].add(i)
    # print(i, set(uf.members(i)))
    # print(i, fr_bl[i])
    # print(i, set(uf.members(i)) - fr_bl[i])
    ans[i-1] = len(set(uf.members(i)) - fr_bl[i]) - 1


print(" ".join([str(i) for i in ans]))

Submission status: Time Limit Exceeded

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

# https://note.nkmk.me/python-union-find/
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())
uf = UnionFind(N)

n_friend = [0]*N
for i in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    n_friend[a-1] += 1
    n_friend[b-1] += 1

n_block_in_friend_cluster = [0]*N
for i in range(K):
    c, d = map(int, input().split())
    if uf.same(c-1, d-1):
        n_block_in_friend_cluster[c-1] += 1
        n_block_in_friend_cluster[d-1] += 1

ans = [len(uf.members(i)) - n_friend[i] -n_block_in_friend_cluster[i] - 1 for i in range(N)]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy

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())
UF = UnionFind(N+1)
SNS = [[0 for _ in range(N+1)] for __ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  SNS[a][b] = 1
  SNS[b][a] = 1
  UF.union(a, b)
for _ in range(K):
  a, b = map(int, input().split())
  SNS[a][b] = -1
  SNS[b][a] = -1
ans = ""
i = 1
while i <= N:
  chain = UF.members(i)
  n = 0
  for m in chain:
    n += 0 if SNS[i][m] == 0 else 1
  ans += "%d "%(len(chain)-n-1)
  i += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://note.nkmk.me/python-union-find/
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())
uf = UnionFind(N)

n_friend = [0]*N
for i in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    n_friend[a-1] += 1
    n_friend[b-1] += 1

n_block_in_friend_cluster = [0]*N
for i in range(K):
    c, d = map(int, input().split())
    if uf.same(c-1, d-1):
        n_block_in_friend_cluster[c-1] += 1
        n_block_in_friend_cluster[d-1] += 1

ans = [len(uf.members(i)) - n_friend[i] -n_block_in_friend_cluster[i] - 1 for i in range(N)]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


class UnionFind:
    def __init__(self, nodes):
        self.sets = {n: None for n in nodes}
        self.sizes = {n: 1 for n in nodes}

    def find(self, a):
        curr = a
        path = []
        while self.sets[curr] is not None:
            path.append(curr)
            curr = self.sets[curr]

        for node in path:
            self.sets[node] = curr
        return curr

    def connected(self, a, b):
        return self.find(a) == self.find(b)

    def union(self, a, b):
        rootA = self.find(a)
        rootB = self.find(b)

        if rootA != rootB:
            self.sets[rootB] = rootA
            self.sizes[rootA] += self.sizes[rootB]

    def size(self, a):
        root = self.find(a)
        return self.sizes[root]


if __name__ == '__main__':
    n, m, k = tuple([int(s) for s in input().split()])
    users = [i for i in range(1, n + 1)]
    uf = UnionFind(users)

    friendships = defaultdict(set)
    blockships = defaultdict(set)

    for i in range(m):
        a, b = tuple([int(s) for s in input().split()])
        friendships[a].add(b)
        friendships[b].add(a)
        uf.union(a, b)
    for i in range(k):
        a, b = tuple([int(s) for s in input().split()])
        blockships[a].add(b)
        blockships[b].add(a)

    res = [0] * n
    for i in range(n - 1):
        for j in range(i + 1, n):
            a = i + 1
            b = j + 1
            if uf.connected(a, b) and b not in friendships[a] and b not in blockships[a]:
                res[i] += 1
                res[j] += 1

    print(" ".join([str(u) for u in res]))

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int , input().split())
dif = set([i for i in range(1, n+1)])
m_list = [[] for _ in range(n+1)]
uni = [[i,1] for i in range(n+1)]
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]
for i in range(m):
    a, b = ab[i]
    m_list[a].append(b)
    m_list[b].append(a)
    if uni[a][0] != uni[b][0]:
        a, b = sorted([uni[a][0], uni[b][0]])
        uni[a][1] += uni[b][1]
        for j in range(1, n+1):
            if uni[j][0] == b:
                uni[j][0] = a
        uni[b][0] = uni[a][0]

k_list = [[] for _ in range(n+1)]
for i in range(k):
    a, b = cd[i]
    if uni[a][0] == uni[b][0]:
        m_list[b].append(a)
        m_list[a].append(b)

result = []
for i in range(1, n+1):
    result.append(uni[uni[i][0]][1]-len(m_list[i])-1)

print(*result)

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int , input().split())
dif = set([i for i in range(1, n+1)])
m_list = [[] for _ in range(n+1)]
uni = [[i,1] for i in range(n+1)]
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]
for i in range(m):
    a, b = ab[i]
    m_list[a].append(b)
    m_list[b].append(a)
    if uni[a][0] != uni[b][0]:
        a, b = sorted([uni[a][0], uni[b][0]])
        uni[a][1] += uni[b][1]
        for j in range(1, n+1):
            if uni[j][0] == b:
                uni[j][0] = a
        uni[b][0] = uni[a][0]

k_list = [[] for _ in range(n+1)]
for i in range(k):
    a, b = cd[i]
    if uni[a][0] == uni[b][0]:
        m_list[b].append(a)
        m_list[a].append(b)

result = []
for i in range(1, n+1):
    r = set(m_list[i])
    result.append(uni[uni[i][0]][1]-len(r)-1)

print(*result)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from sys import setrecursionlimit


def dfs(node: int):
    if node in checked:
        return

    checked.add(node)
    chain.add(node)
    for n in friends[node]-checked:
        dfs(n)


def solve(*args: str) -> str:
    setrecursionlimit(2 * 10 ** 9)
    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])]

    global checked
    checked = set()

    global friends
    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):
        if a in checked:
            continue

        global chain
        chain = set()
        dfs(a)
        for i in chain:
            ret[i] += len(chain-friends[i]-blocked[i]) - 1

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


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy

N, M, K = map(int, input().split())
SNS = [[0 for _ in range(N+1)] for __ in range(N+1)]
Follow = [deque() for __ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  SNS[a][b] = 1
  SNS[b][a] = 1
  Follow[a].append(b)
  Follow[b].append(a)
for _ in range(K):
  a, b = map(int, input().split())
  SNS[a][b] = -1
  SNS[b][a] = -1

Chains = []
seen = [False]*(N+1)
i = 1
while i <= N:
  if not seen[i]:
    seen[i] = True
    chain = deque()
    q = deque(Follow[i])
    memo = [False]*(N+1)
    while q:
      j = q.pop()
      if not memo[j]:
        memo[j] = True
        seen[j] = True
        chain.append(j)
        q += Follow[j]
    Chains.append(deepcopy(chain))
  i += 1
ans = [0] * (N+1)

for chain in Chains:
  l = len(chain)
  for hito in chain:
    n = 0
    for aite in chain:
      n += 0 if SNS[hito][aite] == 0 else 1
    ans[hito] = l - n -1
print(" ".join([str(a) for a in ans[1:]]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


class UnionFind:
    def __init__(self, nodes):
        self.sets = {n: None for n in nodes}

    def find(self, a):
        curr = a
        while self.sets[curr] is not None:
            curr = self.sets[curr]
        return curr

    def connected(self, a, b):
        return self.find(a) == self.find(b)

    def union(self, a, b):
        rootA = self.find(a)
        rootB = self.find(b)

        if rootA != rootB:
            self.sets[rootB] = rootA


if __name__ == '__main__':
    n, m, k = tuple([int(s) for s in input().split()])
    users = [i for i in range(1, n + 1)]
    uf = UnionFind(users)

    friendships = defaultdict(set)
    blockships = defaultdict(set)

    for i in range(m):
        a, b = tuple([int(s) for s in input().split()])
        friendships[a].add(b)
        friendships[b].add(a)
        uf.union(a, b)
    for i in range(k):
        a, b = tuple([int(s) for s in input().split()])
        blockships[a].add(b)
        blockships[b].add(a)

    res = [0] * n
    for i in range(n - 1):
        for j in range(i + 1, n):
            a = i + 1
            b = j + 1

            if uf.connected(a, b) and b not in friendships[a] and b not in blockships[a]:
                res[i] += 1
                res[j] += 1

    print(" ".join([str(u) for u in res]))

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 = list(map(int, input().split()))
from collections import defaultdict

fr = defaultdict(set)
bl = defaultdict(set)
kouho = defaultdict(set)
al = set(range(1, n+1))
ans = [0] * n
uf = UnionFind(n+1)


for _ in range(1, m+1):
    a, b = list(map(int, input().split()))
    fr[a].add(b)
    fr[b].add(a)
    uf.union(a, b)
for _ in range(1, k+1):
    c, d = list(map(int, input().split()))
    bl[c].add(d)
    bl[d].add(c)

for i in range(1, n+1):
    kouho[i] = al - (fr[i] | bl[i]) - {i}

# print(kouho)
# print(uf)

for k, v in kouho.items():

    if len(v) == 0:
        # print(f"{k}は友達候補なし")
        continue
    # print(f"{k}は　候補が{v}")
    rel = set()
    while(len(v) > 0):
        kk = v.pop()
        if uf.same(k, kk):
            ans[k-1] += 1
            # print(f"{k}の友達候補確定：{kk}")





print(" ".join([str(i) for i in ans]))

Submission status: Time Limit Exceeded

Solution code:
# https://note.nkmk.me/python-union-find/
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())
uf = UnionFind(N)

friend = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)

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

ans = [len(set(uf.members(i)) - set(friend[i]) - set(block[i])) - 1 for i in range(N)]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited


if __name__ == "__main__":
    n, m, k = map(int, input().split())
    AB = [map(int, input().split()) for _ in range(m)]
    CD = [map(int, input().split()) for _ in range(k)]

    graph_f = defaultdict(set)
    graph_b = defaultdict(set)

    for a, b in AB:
        graph_f[a - 1].add(b - 1)
        graph_f[b - 1].add(a - 1)

    for c, d in CD:
        graph_b[c - 1].add(d - 1)
        graph_b[d - 1].add(c - 1)

    visited = set()
    conns = {}
    for i in range(n):
        if i not in visited:
            conn = dfs(graph_f, i)
            visited |= {i} | conn
            conns.update({i: conn})
            for j in conn:
                conns.update({j: conn})

    print(' '.join([str(len(conns[i] - graph_f[i] - graph_b[i]) - 1) for i in range(n)]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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


friend = [set() for _ in range(N)]
block = [set() for _ in range(N)]

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

A = [0 for _ in range(N)]


for a, b in AB:
  friend[a-1].add(b)
  friend[b-1].add(a)

for c, d in CD:
  block[c-1].add(d)
  block[d-1].add(c)

def search(root, fs, check):
  for f in fs:
    if check[f-1] != 0 or f == root:
      continue
    else:
      check[f-1] = 1
    search(root, friend[f-1], check)
    answer[root-1].add(f)

for i in range(N):
  search(i+1, friend[i], [0 for _ in range(N)])

for i in range(N):
  A[i] = len(answer[i] - friend[i] - block[i])

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

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)
    checked = set()
    for a in range(1, n+1):
        if a in checked:
            continue

        chain = set()
        stack = list(friends[a])
        while stack:
            b = stack.pop()
            if b in checked:
                continue

            checked.add(b)
            chain.add(b)
            stack.extend(friends[b]-checked)
        for i in chain:
            ret[i] += len(chain-friends[i]-blocked[i]) - 1

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


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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited


if __name__ == "__main__":
    n, m, k = map(int, input().split())
    AB = [map(int, input().split()) for _ in range(m)]
    CD = [map(int, input().split()) for _ in range(k)]

    graph_f = defaultdict(set)
    graph_b = defaultdict(set)

    for a, b in AB:
        graph_f[a - 1].add(b - 1)
        graph_f[b - 1].add(a - 1)

    for c, d in CD:
        graph_b[c - 1].add(d - 1)
        graph_b[d - 1].add(c - 1)

    visited = set()
    conns = {}
    for i in range(n):
        if i not in visited:
            conn = dfs(graph_f, i)
            visited |= {i} | conn
            for j in conn:
                conns.update({j: conn})

    print(' '.join([str(len(conns[i] - graph_f[i] - graph_b[i]) - 1) for i in range(n)]))

Submission status: Time Limit Exceeded

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

friend = [[] for _ in range(n)]
block = [[] for _ in range(n)]

for _ in range(m):
  a, b = map(int, input().split())
  friend[a-1].append(b-1)
  friend[b-1].append(a-1)
  
for _ in range(k):
  c, d = map(int, input().split())
  block[c-1].append(d-1)
  block[d-1].append(c-1)
  
groups = [0] * n
g_size = []
active = [True] * n
g = 0
while any(active):
  idx = active.index(True)
  groups[idx] = g
  active[idx] = False
  size = 1
  stack = [idx]
  while stack:
    v = stack.pop()
    for i in friend[v]:
      if active[i]:
        stack.append(i)
        groups[i] = g
        active[i] = False
        size += 1
  g += 1
  g_size.append(size)
  
for i in range(n):
  size = g_size[groups[i]] - 1 - len(friend[i])
  for j in block[i]:
    if groups[i] == groups[j]:
      size -= 1
  print(size, end=' ')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque
import sys
sys.setrecursionlimit(700000)

NIL = -1
N, M, K = map(int, input().split())
friends = [deque() for i in range(N)]
block = [deque() for i in range(N)]
prefriends = [deque() for i in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    friends[A].append(B)
    friends[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)


def dfs(x, y):
    for i in friends[y]:
        if check[i]:
            #print(i)
            prefriends[x].append(i)
            #print(set(prefriends[x]))
            check[i] = False
            dfs(x, i)
ans = [0]*N
#print(prefriends)
for j in range(N):
    #print(prefriends[j])
    check = [True]*N
    check[j] = False
    dfs(j, j)
    #print(set(prefriends[j]))
    #print(set(friends[j]))
    #print(set(block[j]))
    #print((set(prefriends[j]) - set(friends[j])) - set(block[j]))
    
    ans[j] = (set(prefriends[j]) - set(friends[j])) - set(block[j])
    #print(ans[j])
    #print()
ans = [len(ans[i]) for i in range(N)]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy
N, M, K = map(int, input().split())
SNS = [[0 for _ in range(N+1)] for __ in range(N+1)]
Follow = [deque() for __ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  SNS[a][b] = 1
  SNS[b][a] = 1
  Follow[a].append(b)
  Follow[b].append(a)
for _ in range(K):
  a, b = map(int, input().split())
  SNS[a][b] = -1
  SNS[b][a] = -1
Chains = []
seen = [False]*(N+1)
i = 1
while i <= N:
  if not seen[i]:
    seen[i] = True
    chain = deque()
    q = deque(deepcopy(Follow[i]))
    memo = [False]*(N+1)
    while q:
      j = q.pop()
      if not memo[j]:
        memo[j] = True
        seen[j] = True
        chain.append(j)
        for k in Follow[j]:
          q.append(k)
    Chains.append(deepcopy(chain))
  i += 1
ans = [0] * (N+1)
for chain in Chains:
  l = len(chain)
  for hito in chain:
    n = 0
    for aite in chain:
      n += 0 if SNS[hito][aite] == 0 else 1
    ans[hito] = l - n -1
s = ""
i = 1
while i <= N:
  s += "%d "%ans[i]
  i += 1
print(s)