/ 
Time Limit: 2 sec / Memory Limit: 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