题目描述

一个社交网络服务(SNS)有$N$个用户，依次编号为$1，2，…，N$。

在这个用户之间，存在一些关系，包括$M$个双向的好友关系和$K$个双向的屏蔽关系。

对于每个$i = 1,2,…·,M$，编号为$A_i$的用户和编号为$B_i$的用户是好友关系。

对于每个$i = 1,2,···,K$，编号为$C_i$,的用户和编号为$D_i$的用户是屏蔽关系。

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

用户$a$与用户$b$之间不存在好友关系

用户$a$与用户$b$之间不存在屏蔽关系，

存在一串整数构成的序列$c_0,c_1,c_2,……,c_L$，其中$c_0=a，c_L =b$，且对于每个$i=0,1,…·,L-1$，用户$c_i$和用户$c_{i+1}$之间存在好友关系。

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

输入格式

第一行输入三个正整数 $N,M,K$；

接下来 $M$ 行，每行两个正整数 $A_i,B_i$，表示一对互相关注的用户；

再接下来 $K$ 行，每行两个正整数 $C_i,D_i$，表示一对互相拉黑的用户。

输出格式

输出用空格隔开的 $N$ 个整数，第 $i$ 个数表示用户 $i$ 的“推荐用户”的数量。

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

提示

• $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)$