시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB36181753.125%

문제

Olav has some electronic keyboards and would like to play a tune. Unfortunately all of Olav’s keyboards are broken so each of them can only play some of the notes. By switching which instrument he is using he will be able to play the whole tune, but moving keyboards around is annoying so he would like to minimize the amount of times he has to switch. Can you help Olav figure out the minimum number of keyboard switches needed to play the entire song?

입력

The first line of input is two space separated integers; n (1 ≤ n ≤ 1 000) the number of instruments, and m (1 ≤ m ≤ 1 000), the number of notes in the tune. This is followed by n lines, each starting with an integer ki (1 ≤ ki ≤ 1 000), the number of notes playable by instrument i, followed by ki pairwise distinct integers ℓ1, ℓ2, . . . , ℓki , the notes that instrument i can play (0 ≤ ℓj ≤ 1 000). Finally, there is a line with m space-separated integers – the notes of the tune in order.

출력

The minimum number of times Olav needs to switch the instrument he is using during the tune.

예제 입력 1

2 10
2 1 2
2 2 3
1 2 1 2 3 3 2 3 1 3

예제 출력 1

3

출처

Contest > Bergen Open > Bergen Open 2018 K번