← 返回题目列表

AtCoder · abc157_d

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 由之间的整数组成 1 和 N (含)使得 c_0 = a, c_L = b,并且用户之间有友谊 c_i 和 c_{i+1} 对于每个 i = 0, 1, \cdots, L - 1.

对于每个用户 i = 1, 2, ... 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

输出

按顺序打印答案,中间留有空格。


示例输入 1

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

示例输出 1

0 1 0 1

用户之间存在友谊 2 和 3,以及之间 3 和 4。此外,用户之间不存在友谊或阻碍 2 和 4。因此,用户 4 是用户的好友候选人 2.

但是,用户都没有 1 or 3 是用户的好友候选人 2,所以用户 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

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