Friend Suggestions

题目描述

一个 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$，它有多少个可能成为好友的人？

输入格式

输入从标准输入按如下格式给出： $N$ $M$ $K$ $A_1$ $B_1$ $\vdots$ $A_M$ $B_M$ $C_1$ $D_1$ $\vdots$ $C_K$ $D_K$

输出格式

按顺序输出答案，之间用空格隔开。

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

0 1 0 1

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

0 0 0 0 0

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

1 3 5 4 3 3 3 3 1 0

提示

输入中的所有数值均为整数。 $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)$用户 $2$ 与 $3$ 之间有友谊，$3$ 与 $4$ 之间也有友谊。此外，用户 $2$ 与 $4$ 之间既没有友谊也没有拉黑关系。因此，用户 $4$ 是用户 $2$ 的一个可能成为好友的人。 然而，用户 $1$ 和 $3$ 都不是用户 $2$ 的可能成为好友的人，所以用户 $2$ 有一个可能成为好友的人。
每个人都是互为好友且没有可能成为好友的人。

标签: AtCoder|abc157D

来源

AtCoder|abc157D