分数: 300 点
问题陈述
AtCoder 餐厅使用 N 成分类型编号为 1 to N.
餐厅优惠 M 菜肴编号为 1 to M。盘子 i 使用 K_i 成分类型,即 A_{i,1}, A_{i,2}, \ldots, A_{i,K_i}.
Snuke 目前不喜欢所有 N 成分。他不能吃任何使用一种或多种他不喜欢的食材的菜肴,并且他可以吃不使用任何不喜欢的食材的菜肴。
下一个 N 天,他每天都会克服一种成分的不喜欢。当天 i,他克服了成分 B_i,从此他不再讨厌它了。
对于每个 i=1,2,\ldots,N,找到:
- 克服食材后在AtCoder餐厅可以立即吃的菜品数量 B_i 当天 i.
约束
- 1 \leq N \leq 3 \times 10^{5}
- 1 \leq M \leq 3 \times 10^{5}
- 1 \leq K_i \leq N (1 \leq i \leq M)
- 总和 K_i 最多是 3 \times 10^{5}.
- 1 \leq A_{i,j} \leq N (1 \leq i \leq M, 1 \leq j \leq K_i)
- A_{i,j} \neq A_{i,k} (1 \leq i \leq M, j \neq k)
- 1 \leq B_i \leq N (1 \leq i \leq N)
- B_i \neq B_j (i \neq j )
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M
K_1 A_{1,1} A_{1,2} \ldots A_{1,K_1}
K_2 A_{2,1} A_{2,2} \ldots A_{2,K_2}
\vdots
K_M A_{M,1} A_{M,2} \ldots A_{M,K_M}
B_1 B_2 \ldots B_N
输出
打印 N 行。的 k- 第行应包含以下问题的答案 i=k.
示例输入 1
5 4 2 1 2 3 3 4 5 3 1 2 5 1 3 1 3 2 5 4
示例输出 1
0 1 2 3 4
Snuke克服了他不喜欢的成分,如下:
- 天 1:他克服成分 1。这时候每道菜还是用了不喜欢的食材,所以打印 0.
- 天 2:他克服成分 3。盘子 4 不再使用任何不喜欢的成分并变得可食用;所有其他菜肴仍然使用不喜欢的成分,所以打印 1.
- 天 3:他克服成分 2。盘子 1 不再使用任何不喜欢的成分并变得可食用;所有菜肴,除了 1 和 4 仍然使用不喜欢的成分,所以打印 2.
- 天 4:他克服成分 5。盘子 3 不再使用任何不喜欢的成分并变得可食用;所有菜肴,除了 1, 3,和 4 仍然使用不喜欢的成分,所以打印 3.
- 天 5:他克服成分 4。盘子 2 不再使用任何不喜欢的成分并变得可食用;现在所有菜肴都没有不喜欢的成分,所以打印 4.
示例输入 2
9 8 1 4 5 6 9 7 4 3 4 2 4 1 3 1 1 5 7 9 8 1 5 2 9 8 1 2 1 1 6 5 2 7 8 4 1 9 3
示例输出 2
0 0 1 1 1 2 4 6 8