E - Dislike Foods 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

AtCoderレストランでは 1 から N までの番号がつけられている N 種類の食材を扱っています。

また、AtCoderレストランでは 1 から M までの番号がつけられている M 個の料理を提供しています。料理 i には K_i 種類の食材が使われており、食材 A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} が使われています。

すぬけくんは現在 N 種類の食材がすべて苦手です。また、すぬけ君は苦手な食材が 1 種類でも使われている料理を食べることができず、苦手な食材が 1 種類も使われていない料理を食べることができます。

すぬけ君はこれから N 日間かけて苦手な食材を克服しようとしています。 すぬけ君は i 日目に食材 B_i を克服し、それ以降苦手な食材でなくなります。

i=1,2,\ldots,N について以下の値を求めてください。

  • i 日目にすぬけ君が食材 B_i を克服した直後、すぬけ君が食べることができるAtCoderレストランの料理の個数

制約

  • 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

以下のようにすぬけ君は苦手な食材を克服します。

  • 1 日目: 食材 1 を克服する。このとき、どの料理にも苦手な食材が使われているため 0 を出力する。
  • 2 日目: 食材 3 を克服する。このとき、料理 4 は苦手な食材が使われなくなるため食べられるようになる。料理 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

Score : 300 points

Problem Statement

The AtCoder Restaurant uses N types of ingredients numbered from 1 to N.

The restaurant offers M dishes numbered from 1 to M. Dish i uses K_i types of ingredients, namely A_{i,1}, A_{i,2}, \ldots, A_{i,K_i}.

Snuke currently dislikes all N ingredients. He cannot eat any dish that uses one or more ingredients he dislikes, and he can eat a dish that uses none of the disliked ingredients.

Over the next N days, he will overcome his dislikes one ingredient per day. On day i, he overcomes ingredient B_i, and from then on he no longer dislikes it.

For each i=1,2,\ldots,N, find:

  • the number of dishes at the AtCoder Restaurant that he can eat immediately after overcoming ingredient B_i on day i.

Constraints

  • 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)
  • The sum of K_i is at most 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 )
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print N lines. The k-th line should contain the answer for i=k.

Sample Input 1

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

Sample Output 1

0
1
2
3
4

Snuke overcomes his disliked ingredients as follows:

  • Day 1: He overcomes ingredient 1. At this time, every dish still uses a disliked ingredient, so print 0.
  • Day 2: He overcomes ingredient 3. Dish 4 no longer uses any disliked ingredient and becomes edible; all other dishes still use disliked ingredients, so print 1.
  • Day 3: He overcomes ingredient 2. Dish 1 no longer uses any disliked ingredient and becomes edible; all dishes except 1 and 4 still use disliked ingredients, so print 2.
  • Day 4: He overcomes ingredient 5. Dish 3 no longer uses any disliked ingredient and becomes edible; all dishes except 1, 3, and 4 still use disliked ingredients, so print 3.
  • Day 5: He overcomes ingredient 4. Dish 2 no longer uses any disliked ingredient and becomes edible; now all dishes have no disliked ingredients, so print 4.

Sample Input 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

Sample Output 2

0
0
1
1
1
2
4
6
8