分数: 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