D - 好友推荐

得分：$400$分

问题描述

一个社交网络服务（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$之间不存在屏蔽关系。
• 存在一串整数构成的序列$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,\cdots,N$，它有多少个好友候选？

约束

• 输入中的所有值都是整数。
• $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)$

输入

从标准输入读入数据，具体格式如下：

$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之间既不存在好友关系，也不存在屏蔽关系。因此，用户2是用户4的好友候选。

然而，用户1和用户3都不是用户2的好友候选，所以用户2只有一个好友候选。

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