好友推荐

题目描述

某个 SNS 上注册了人 $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$ 是拉黑关系。该关系是双向的。

当以下 $4$ 个条件都满足时,称人 $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

人 $2$ 和人 $3$ 是朋友关系,人 $3$ 和人 $4$ 是朋友关系,并且人 $2$ 和人 $4$ 既不是朋友关系也没有拉黑关系,因此人 $4$ 是人 $2$ 的好友候选。

人 $1$ 和人 $3$ 不是人 $2$ 的好友候选,因此人 $2$ 的好友候选有 $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

所有人都互相是朋友关系,因此好友候选为 $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 \le N \le 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)$