Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss Home ProblemSet Status Ranklist 4 Contest LoginRegister Exam
Problem 1093. -- The Problem With the Problem Setter

The Problem With the Problem Setter

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 6  Solved: 0
[Submit][Status][Discuss]

Description

So many students are interested in participating in this year's regional programming contest that we have decided to arrange a screening test to identify the most promising candidates. This test may include as many as 100 problems drawn 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 given a pool of about 1,000 problems divided into appropriate categories. After getting the problems, however, I discovered that the original authors often wrote down multiple category-names in the category fields. Since no problem can used in more than one category and the number of problems needed for each category is fixed, assigning problems for the test is not so easy.

Input

The input file may contain multiple test cases, each of which begins with a line containing two integers,nk and np, where nk is the number of categories and is the number of problems in the pool. There will be between 2 and 20 categories and at most 1,000 problems in the pool. The second line contains nk positive integers, where the ith integer specifies the number of problems to be included in category i ( 1<=i<=nk) of the test. You may assume that the sum of these nk integers will never exceed 100. The jth ( 1<=j<=np) of the next np lines contains the category information of the jth problem in the pool. Each such problem category specification starts with a positive integer specifying the number of categories in which this problem can be included, followed by the actual category numbers. A test case containing two zeros for nk and np terminates the input.

Output

For each test case, print a line reporting whether problems can be successfully selected from the pool under the given restrictions, with 1 for success and 0 for failure. In case of successful selection, print nk additional lines where the ith line contains the problem numbers that can be included in category i. Problem numbers are positive integers not greater then np and each two problem numbers must be separated by a single space. Any successful selection will be accepted.

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

HINT

Source

[Submit][Status][Discuss]

HOME Back

한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin