该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

智能推荐

题目背景

在育华学校的算法训练体系中，T2之王面临着“智能推荐做题”的挑战。系统会按特定规则每日推荐题目，只有完成前置题目才能解锁后续推荐。T2之王需要规划做题顺序，以最快速度完成目标题目K。

题目描述

现有N道题，天数从0开始计数。每天可完成若干道题，但仅能做之前推荐过或当天推荐的题（每道题仅能做一次）。具体规则如下：

1. 初始推荐：第0天（第一天）系统推荐p道题；
2. 后续推荐：对第i道题，若存在推荐规则集合s_i，当且仅当满足以下两个条件时，第i道题会在下一天被推荐：
   • 已完成s_i中所有题目；
   • s_i中至少有一道题是当天完成的。

T2之王的目标是完成第K道题，需计算最少在第几天能达成目标；若无法完成，则输出-1。

输入格式

1. 第一行：三个整数N、K、p，分别表示总题数、目标题序号、第0天推荐题数；
2. 第二行：p个整数，代表第0天推荐的题的序号；
3. 第三行：一个整数R，表示推荐规则的数量；
4. 接下来R行：每行描述一条推荐规则，格式为「v_i s_i p_1 p_2 ... p_{s_i}」，其中：
   • v_i：待推荐的题的序号；
   • s_i：解锁v_i所需完成的题目数量；
   • p_1~p_{s_i}：解锁v_i必须完成的所有题目（即集合s_i）。

输出格式

输出一个整数，代表完成第K道题的最少天数；若无法完成，输出-1。

样例

样例输入1

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

样例输出1

3

样例解释1

• 第0天：推荐题1、2，完成这两道题；
• 因完成1、2（且当天完成），触发规则1，第1天推荐题3；
• 第1天：完成题3，触发规则2（完成1、2、3且当天完成3），第2天推荐题4；
• 第2天：完成题4，触发规则3（完成1、3、4且当天完成4），第3天推荐题5；
• 第3天：完成目标题5，故最少天数为3。

样例输入2

1 1 1
1
0

样例输出2

0

样例解释2

第0天推荐的题就是目标题1，当天即可完成，故天数为0。

样例输入3

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

样例输出3

-1

样例解释3

推荐规则仅能解锁题3和6，无法触发题7的推荐，故无法完成目标题7。

数据规模与测试点（共20个测试点，育华学校专项）

注：所有测试点均满足：

• 1≤K,s_i,p_i,v_i≤N，0≤R≤5×10³；
• |s_i|（规则中所需完成题数）互不相同，且同一|s_i|对应的p_i、v_i互不相同。