ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1107. Warehouse Problem

Time limit: 1.0 second
Memory limit: 64 MB
The are N different types of goods at the warehouse. Types are numbered by numbers 1…N. Employees of this warehouse made K different sets of these goods. We'll say that two sets are “similar” if one of them is obtained by deleting one good from the second set or by replacing one good to another.
E.g. Set “1 2 3 4” is similar to sets “3 2 1”, “1 2 5 3 4”, “1 2 3 4 2” and “1 5 4 3” and is not similar to “1 2”, “1 1 2 2 3 4” and “4 5 3 6”.
This warehouse serves M shops (0 < N < M < 101), sending them sets of goods. Every two sets sent to the shop should not be similar. It is possible not to send any set to one or more shops.
You are to write program that determines how to distribute all K sets to these M shops.

Input

The first line contains numbers N, K, M. Then K lines describing every set of goods follow, K ≤ 50000. Each of these lines is started with the number of goods in the set, then numbers of goods are written. Number of goods in any set is more than 0 and less than 101. All numbers in these lines are separated by exactly one space.

Output

The first line of the output should contain word YES if the solution exists or NO contrary. If the answer is YES write the numbers of the shops where sets should be sent to. In the second line you have to write number of the shop where the first set should be sent to, the third — for the second set, etc. If there are more than one solution exist you may find any of them.

Sample

inputoutput
8 20 12
5 1 3 5 6 4
5 1 3 5 6 3
4 5 6 3 3
4 5 6 3 4
4 4 6 5 8
4 7 7 7 7
3 7 7 7
2 2 2
3 2 2 7
3 1 2 3
3 1 2 4
10 1 2 3 4 5 6 7 8 7 6
10 8 7 6 5 4 3 2 1 2 1
20 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 3 5 7
5 4 6 4 6 4
5 6 4 6 4 6
6 6 6 6 6 6 6
3 6 6 6
1 1
1 2
YES
2
1
9
1
6
2
4
5
3
7
8
5
4
8
7
9
1
1
2
3
Problem Author: Dmitry Filimonenkov
Problem Source: Tetrahedron Team Contest May 2001