Problem Background

Data has been strengthened.

Problem Description

There are $N$ problems.

Day numbers start from $0$. Each day, you can solve several problems. You can only solve problems that have been recommended before or are recommended on the same day (each problem can only be solved once). On the first day, the smart recommendation system will recommend $p$ problems.

The recommendation rules are as follows:

For the $i$-th problem, if it is possible to be recommended, there will be a set of problems $s_i$. The $i$-th problem will be recommended the next day if and only if you have solved every problem in $s_i$ and at least one of them was solved on the same day.

You want to solve the $K$-th problem. What is the minimum day on which you can fulfill your wish?

Input Format

The first line contains three integers $N, K, p$, as described in the problem.

The second line contains $p$ integers, representing the problem numbers recommended on the first day.

The third line contains an integer $R$, indicating the number of recommendation rules.

The next $R$ lines, each containing a rule, are formatted as follows:

An integer $v_i$, representing the problem number to be recommended. Then an integer $s_i$, indicating the number of problems that need to be solved for this problem to be recommended. Following are $s_i$ integers $p_i$, representing each problem that needs to be solved.

Output Format

An integer representing the minimum day on which you can fulfill your wish.

If it is impossible to complete the $K$-th problem under any circumstances, output -1.

Sample Input and Output

Sample Input #1

5 5 2
1 2
3
3 2 1 2
4 3 1 2 3
5 3 1 3 4

Sample Output #1

3

Sample Input #2

1 1 1
1
0

Sample Output #2

0

Sample Input #3

7 7 2
1 2
2
3 2 1 2
6 2 1 2

Sample Output #3

-1

Sample Input #4

See the attached file rec4.in

Sample Output #4

See the attached file rec4.ans

Notes

[Sample Explanation #1]

On day $0$, problems $1$ and $2$ are recommended and solved.

On day $1$, problem $3$ is recommended and solved.

On day $2$, problem $4$ is recommended and solved.

On day $3$, problem $5$, which is the $K$-th problem, is recommended and solved.

The $K$-th problem can be completed on day $3$.

[Sample Explanation #2]

On day $0$, problem $1$, which is the $K$-th problem, is recommended and solved.

The $K$-th problem is completed on day $0$.

[Data Range]

Let $\left| s_i \right|$ denote the number of problems in the $i$-th rule that need to be solved for $v_i$ to be recommended.

For $30\%$ of the data, $1 \leq N \leq 100$.

For $50\%$ of the data, there are no cycles.

For $100\%$ of the data, $1 \le K, s_i, p_i, v_i \le N \le 5 \times 10^3$, $0 \leq R \leq 5 \times 10^3$. $\left| s_i \right|$ are distinct, and for each $\left| s_i \right|$, $p_i$ are distinct, and $v_i$ are distinct.

见题面 Input 部分

见题面 Output 部分