P16959 [SCCPC 2026] Spirit Battles.

Little $z$ loves playing Roco Kingdom, and especially likes having spirit battles with other players. There are now $n$ types of spirits, numbered from $1$ to $n$. There are counter relationships between spirits. For each type of spirit, it is countered by at most $k$ types of spirits. When Little $z$'s spirit $A$ fights the opponent's spirit $B$, the result is as follows: - If $A$ counters $B$ and $B$ does not counter $A$, then $B$ is knocked down, and $A$ continues fighting. - If $B$ counters $A$ and $A$ does not counter $B$, then $A$ is knocked down, and $B$ continues fighting. - If there is no counter relationship between $A$ and $B$, then they knock each other out. - If $A$ and $B$ counter each other, then Little $z$ can defeat the opponent's spirit with excellent game skills, that is, $B$ is knocked down, and $A$ continues fighting. Little $z$ already knows the opponent's spirit deployment order in advance. It is a sequence of length $m$, and repeated spirits may appear in the sequence. Little $z$ needs to arrange his own spirit deployment order properly to defeat all of the opponent's spirits. During the battle, if the current spirit is not knocked down, it cannot be switched out. Only after the current spirit is knocked down or both sides knock each other out can Little $z$ send out a new spirit. Little $z$ may send out the same type of spirit multiple times. Sending out one spirit costs $1$. Please find the minimum total cost required for Little $z$ to defeat all of the opponent's spirits.

The first line contains three integers $n,m,k$ ($1 \le n,m \le 10^5, 1 \le k \le 30$), representing the number of spirit types, the length of the opponent's deployment sequence, and the maximum number of spirit types that can counter each spirit type. In the next $n$ lines, for the $i$-th line, it first contains an integer $s_i$ ($0 \le s_i \le k$), representing the number of spirit types that counter the $i$-th type of spirit; then it contains $s_i$ integers $x_{i,1},x_{i,2},\ldots,x_{i,s_i}$ ($1 \le x_{i,j} \le n,x_{i,j} \neq i$), representing the spirit IDs that counter the $i$-th type of spirit. The last line contains $m$ integers $a_1,a_2,\ldots,a_m$ ($1 \le a_i \le n$), representing the opponent's spirit deployment sequence. The input guarantees that within each line of counter relationships, all spirit IDs are distinct, and there is no self-counter relationship.

Output one line with one integer, representing the minimum total cost required for Little $z$ to defeat all of the opponent's spirits.

Translated by ChatGPT 5