TLE '17 Contest 4 P3 - Fax's Christmas Dish

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Python 3.0s
Memory limit: 256M
Python 512M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Presentation could be improved, but it was pretty tasty!

Fax McClad, Croneria's most meticulous bounty hunter, is going to prepare a dish for Christmas!

There are different food items, numbered from to . There are different recipes. A recipe consists of a non-empty list of items that need to be combined to produce a target item. Only one unit of each item in the list is required, and the target item will not be in the list. Additionally, no two recipes will have the same target item, each item in the list has a greater number than the target item's number, item is the target item in exactly one recipe, and items to appear in exactly one recipe's list.

Fax wants to have one unit of item as his dish. He will receive item on each of the next days. On the day, he will receive item .

What is the earliest day that Fax can obtain item ?

110
210
330
450None

Input Specification

The first line will contain integers , , and .

Each of the next lines will contain one recipe. A recipe is one line long and follows this format:

• The first integer is the target item.
• The second integer is the number of required items.
• The remaining integers are the required items.

The last line will contain integers. The integer in this line is .

Output Specification

If Fax cannot obtain item after all days, output -1. Otherwise, output the earliest day that Fax can obtain item .

Sample Input 1

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

Sample Output 1

6

Explanation for Sample Output 1

After days, Fax has these items: 3 3 6 3 5 4. Fax can follow the first recipe to get 2 3 3 5 4, then the third recipe to get 1 3 3 5.

Sample Input 2

4 1 7
1 3 2 3 4
2 2 3 3 2 3 3

Sample Output 2

-1