ZOJ Problem Set - 2601
The company where Jerry works owns a number of warehouses that can be used to store various goods. For each warehouse the types of goods that can be stored in this warehouse are known. To avoid problems with taxes, each warehouse must store only one type of goods, and each type of goods must be stored in at most one warehouse.
Jerry is planning to receive a new lot of goods in a couple of days and he must store the goods in the warehouses. However there are some goods in some warehouses already and Jerry wants to move as few of them as possible.
Help him to find the maximal number of types of goods that he can store in the warehouses and the minimal number of goods he must move in order to do that.
The input contains multiple test cases. The first line of the input is a single integer T (1 <= T <= 40) which is the number of test cases. T test cases follow, each preceded by a single blank line.
The first line of each test case contains integer numbers m and n (2 <= m, n <= 200) - the number of warehouses and the number of types of goods respectively.
The following m lines describe warehouses. Each line contains ki - the number of various types of goods that can be stored in this warehouse (remember, only one type of goods can be stored in a warehouse at a time), followed by ki integer numbers - the types of goods that can be stored.
The last line contains m integer numbers - for each warehouse either 0 is provided if there is no goods in this warehouse, or the type of goods that is currently stored in this warehouse if there is one. It is guaranteed that the initial configuration is correct, that is, each warehouse stores the goods it can store, and no type of goods is stored in more than one warehouse.
For each case, on the first line print p - the maximal number of types of goods that can be stored in the warehouses, and q - the minimal number of goods that need to be moved in order to do that. After that output m integer numbers - for each warehouse output the type of goods that must be stored in this warehouse, or 0 if none must be.
Remember that you may only move goods that are already stored in some houses to other ones, you are not allowed to dispose them.
Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.
2 4 5 3 1 2 3 2 1 2 2 1 2 3 1 4 5 0 2 0 1 2 2 1 1 1 2 0 0
4 1 3 2 1 4 2 0 1 2
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #6