Score : $400$ points

问题描述

一个社交网络服务（SNS）拥有 $N$ 名用户——用户 $1$、用户 $2$、$\cdots$、用户 $N$。

在这 $N$ 名用户之间，存在一些关系——共有 $M$ 条 双向好友关系 和 $K$ 条 双向屏蔽关系。

对于每一条 $i = 1, 2, \cdots, M$ 的好友关系，用户 $A_i$ 和用户 $B_i$ 之间存在一条双向好友关系。

对于每一条 $i = 1, 2, \cdots, K$ 的屏蔽关系，用户 $C_i$ 和用户 $D_i$ 之间存在一条双向屏蔽关系。

我们定义用户 $a$ 是用户 $b$ 的 好友候选人 ，当满足以下四个条件时：

• $a \neq b$。
• 用户 $a$ 和用户 $b$ 之间不存在好友关系。
• 用户 $a$ 和用户 $b$ 之间不存在屏蔽关系。
• 存在由 $1$ 到 $N$ （包含）之间的整数组成的序列 $c_0, c_1, c_2, \cdots, c_L$，使得 $c_0 = a$、$c_L = b$，且对于每个 $i = 0, 1, \cdots, L - 1$，用户 $c_i$ 和 $c_{i+1}$ 之间存在好友关系。

对于每个用户 $i = 1, 2, ..., N$，它有多少个好友候选人？

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 17:14:48