配点 : $400$ 点

問題文

とある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$ について、友達候補の数を答えてください。

制約

• 入力は全て整数
• $2 \leq N \leq 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$ は友達関係にもブロック関係にもありませんから, 人 $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