Chemical Reactions

Interview

Time limit1sMemory limit512 MB

Summary

Count unowned compounds that become producible by repeatedly firing reactions whose substrates are all available.

Level: Medium5 of 10
Topics: BFS, Graph, Queue
Solved: No attempts yet

Problem

Bajtek has recently taken up chemistry and become fascinated by it, so he built his own laboratory. He already owns a set of chemical compounds along with the tools needed to run various reactions. Now he wants to grow his collection, and he is curious how many different compounds that he does not yet own he could produce from what he has.

Assume every compound Bajtek already owns is available in unlimited supply. A reaction can be carried out whenever Bajtek owns all of its substrates; carrying it out gives him all of its products, which he may then use in further reactions.

Write a program that reads the compounds Bajtek owns and the reactions he can perform, then determines how many compounds he does not yet own but is able to produce.

Input

The first line contains three integers $n$ , $k$ , and $r$ ( $1 \le n \le 10^6$ , $1 \le k \le n$ , $1 \le r \le 10^5$ ), separated by single spaces: the number of compounds known to Bajtek, the number of compounds he owns, and the number of reactions he can perform.

The second line contains $k$ distinct integers $a_i$ ( $1 \le a_i \le n$ ), the numbers of the compounds Bajtek owns.

Each of the next $r$ lines describes one reaction. A description starts with an integer $s_j$ ( $1 \le s_j \le 10$ ), the number of substrates, followed by the $s_j$ substrate compound numbers. It then continues with an integer $p_j$ ( $1 \le p_j \le 10$ ), the number of products, followed by the $p_j$ product compound numbers. Every compound number is between $1$ and $n$ . The substrate numbers of a reaction are pairwise distinct, and so are its product numbers, but a compound may appear as both a substrate and a product of the same reaction (acting as a catalyst). All numbers describing one reaction are separated by single spaces.

Output

Output a single integer: the number of compounds Bajtek does not yet own but can produce from the compounds he owns by carrying out the reactions.

Hint

In the sample the four reactions are:

$1 + 2 \to 3 + 4$
$4 + 1 \to 3$
$2 + 3 \to 2 + 1 + 5$
$5 + 6 \to 1 + 8 + 2$

Bajtek starts with compounds $1$ and $2$ . Reaction 1 lets him obtain $3$ and $4$ , and then reaction 3 produces $5$ . He cannot obtain compounds $6$ , $7$ , or $8$ . Hence he can make $3$ new compounds ( $3$ , $4$ , and $5$ ).

Examples3

Example 1

Input

8 2 4
2 1
2 1 2 2 3 4
2 4 1 1 3
2 2 3 3 2 1 5
2 5 6 3 1 8 2

Expected output

Example 2
Input
```
3 1 1
1
1 1 2 2 3
```
Expected output
```
2
```

Example 3

Input

Expected output