Setting

The number of students interested to participate in this year's Contest of Arbitrary Universality is huge. Since it is very difficult to accommodate such a large number of students in our labs, we have decided to arrange a screening test. The test will be paper-based and may include as many as 100 analytical problems from as many as 20 categories. I have been assigned the job of setting problems for this test.

At first, the job seemed to be very easy since I was told that I would be provided with a pool of about 1000 analytical problems already divided into appropriate categories. But after getting the problems I discovered that for many problems the original authors were not sure about the appropriate categories and so they wrote down multiple category names in the category fields. Since in the screening test a problem cannot be placed under more than one category and the number of problems to be set under each category is fixed, setting problems for this test is not actually easy.

I know that a program can be written that can do the job automatically. But since I don’t like writing programs (and since this is a programming challenge, after all), I seek your help.

Input

The input may contain multiple test cases. Each test case begins with a line containing two integers: \(2 \leq n_k \leq 20\) and \(n_k \leq n_p \leq 1000\), where \(n_k\) is the number of categories and \(n_p\) is the number of problems in the pool. The second line contains \(n_k\) positive integers where the \(i\)-th integer specifies the number of problems to be included in category \(1 \leq i \leq n_k\) of the test. You may assume that the sume of these \(n_k\) integers will never exceed 100. The \(j\)-th of the next \(n_p\) lines contains the category information of the \(j\)-th problem in the pool. A category specification for a problem starts with a positive integer not greater than \(n_k\), specifying the number of categories this problem can be included in, followed by the category numbers. Category numbers are positive integers not greater than \(n_k\).

A test case with \(n_k = n_p = 0\) terminates the input.

Output

For each test case, print a line containing either 1 or 0, depending on whether or not problems can be successfully selected from the pool under the given restrictions.

Sample Input

3 15
3 3 4
2 1 2
1 3
1 3
1 3
1 3
3 1 2 3
2 2 3
2 1 3
1 2
1 2
2 1 2
2 1 3
2 1 2
1 1
3 1 2 3
3 15
7 3 4
2 1 2
1 1
1 2
1 2
1 3
3 1 2 3 2 2 3
2 2 3
1 2
1 2
2 2 3
2 2 3
2 1 2
1 1
3 1 2 3
0 0

Sample Output

1
8 11 12
1 6 7
2 3 4 5
0

This is challenge 10092 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.

Statistics

Difficulty (0 votes)
Average test runtime 0.30
Points (changes over time) 10
Tried by 3 users
Solved by 3 users

Global ranking

# Name Runtime Points worth
1 Dark 0.30 10
2 Skøgland 0.30 10
3 Mac 0.31 10