题目描述

An SNS has $N$ users - User $1$, User $2$, $\cdots$, User $N$.

Between these $N$ users, there are some relationships - $M$ friendships and $K$ blockships.

For each $i = 1, 2, \cdots, M$, there is a bidirectional friendship between User $A_i$ and User $B_i$.

For each $i = 1, 2, \cdots, K$, there is a bidirectional blockship between User $C_i$ and User $D_i$.

We define User $a$ to be a friend candidate for User $b$ when all of the following four conditions are satisfied:

• $a \neq b$.
• There is not a friendship between User $a$ and User $b$.
• There is not a blockship between User $a$ and User $b$.
• There exists a sequence $c_0, c_1, c_2, \cdots, c_L$ consisting of integers between $1$ and $N$ (inclusive) such that $c_0 = a$, $c_L = b$, and there is a friendship between User $c_i$ and $c_{i+1}$ for each $i = 0, 1, \cdots, L - 1$.

For each user $i = 1, 2, ... N$, how many friend candidates does it have?

一个 SNS 有 $N$ 个用户--用户 $1$ 、用户 $2$ 、 $\cdots$ 、用户 $N$ 。

这些 $N$ 用户之间存在一些关系-- $M$ _朋友关系和{5295748}_朋友关系。好友关系和 $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$ 、用户 $c_i$ 和 $c_{i+1}$ 之间的每个 $i = 0, 1, \cdots, L - 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$

输出格式

按顺序打印答案，中间留出空格。

样例 #1

样例输入 #1

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

样例输出 #1

0 1 0 1

样例 #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

样例输出 #2

0 0 0 0 0

样例 #3

样例输入 #3

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

样例输出 #3

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

样例 $1$ 解释

用户 $2$ 和 $3$ 之间、用户 $3$ 和 $4$ 之间存在好友关系。另外，用户 $2$ 和 $4$ 之间不存在好友关系或屏蔽关系。因此，用户 $4$ 是用户 $2$ 的候选好友。

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

样例 $2$ 解释

每个人都是其他人的朋友，没有候选朋友。