题目描述

某平台上有 $N$ 名用户，其中，有 $M$ 对用户是互相关注的，有 $K$ 对用户是互相拉黑的。

当用户 $i$ 和用户 $j$ 满足以下条件时，用户 $j$ 就是用户 $i$ 的“推荐用户”：

• 用户 $i$ 可以与 用户 $j$ 通过若干对用户的互相关注关系连接起来。（比如用户 1 与用户 2，用户 2 与用户 3 都互相关注，则用户 1 和 用户 3 就可以通过他们的关系连接起来）
• 用户 $i$ 与用户 $j$ 没有互相关注或互相拉黑。

求每位用户的“推荐用户”的数量。

数据保证不会存在一对用户既互相关注又互相拉黑。

输入格式

第一行输入三个正整数 $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

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 \le N \le 10^5, 0 \le M,K \le 10^5$。