← 返回题目列表

AtCoder · abc402_c

F. 不喜欢食物

中文机器翻译题面 查看原题

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