Problem AQ
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?
Input
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 ($0 \leq \ell _ j \leq 1\, 000$). Finally, there is a line with $m$ space-separated integers – the notes of the tune in order.
Output
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 |
3 |
