2018-11-10 10:00 UTC

Bergen Open 2018


2018-11-10 15:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -196 days 3:39:36

Time elapsed


Time remaining


Problem K
Keyboards in Concert

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 \leq n \leq 1\, 000$) the number of instruments, and $m$ ($1 \leq m \leq 1\, 000$), the number of notes in the tune. This is followed by $n$ lines, each starting with an integer $k_ i$ ($1 \leq k_ i \leq 1\, 000$), the number of notes playable by instrument $i$, followed by $k_ i$ pairwise distinct integers $\ell _1, \ell _2, \ldots , \ell _{k_ i}$, the notes that instrument $i$ can play ($1 \leq \ell _ j \leq 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.

Sample Input 1 Sample Output 1
2 10
2 1 2
2 2 3
1 2 1 2 3 3 2 3 1 3