Background

The testdata has been strengthened.

Problem Description

There are now $N$ problems.

The days are numbered starting from $0$. Each day you may solve several problems. You can only solve problems that have been recommended before or are recommended on that day (each problem can be solved at most once). On day $0$, the intelligent recommendation system will recommend $p$ problems.

The recommendation rules are as follows:

For problem $i$, if it can possibly be recommended, there will be a problem set $s_i$. If and only if you have solved every problem in $s_i$, and among them there is at least one problem solved on the current day, then problem $i$ will be recommended on the next day.

You want to solve problem $K$. What is the earliest day on which you can achieve this?

Input Format

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

The second line contains $p$ integers, indicating the indices of the problems recommended on day $0$.

The third line contains an integer $R$, indicating that there are $R$ recommendation rules.

The next $R$ lines each contain one rule, in the following format:

An integer $v_i$, the index of the problem to be recommended. Then an integer $s_i$, the number of problems that must be solved in order for this problem to be recommended. Then $s_i$ integers $p_i$, representing each problem that must be solved.

Output Format

Output one integer, the minimum day on which you can achieve the goal.

If problem $K$ can never be solved no matter what, output -1.

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

3

1 1 1
1
0

0

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

-1

见文件附件的 rec4.in

见文件附件的 rec4.ans

Hint

[Sample Explanation #1]

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

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

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

On day $3$, problem $5$ was recommended, which is problem $K$, and it was solved.

So problem $K$ can be solved by day $3$.

[Sample Explanation #2]

On day $0$, problem $1$ was recommended, which is problem $K$, and it was solved.
So it was completed on day $0$.

[Constraints]

Let $\left| s_i \right|$ denote, in the $i$-th recommendation rule, the total number of problems that must be solved if $v_i$ is to be recommended.

For $30\%$ of the data, it is guaranteed that $1 \leq N \leq 100$.

For $50\%$ of the data, it is guaranteed that there are no cycles.

For $100\%$ of the data, it is guaranteed that $1 \le K, s_i, p_i, v_i \le N \le 5\times 10^3$, $0 \leq R \leq 5 \times 10^3$. All $|s_i|$ are pairwise distinct, and for each $|s_i|$, all $p_i$ are pairwise distinct, and all $v_i$ are pairwise distinct.

Translated by ChatGPT 5