P4960 Platelets and Coagulation Factors

To repair the wound as soon as possible, the platelets are carrying coagulation factors. They (nothing wrong) are discussing how to distribute them. Since they are so cute, you are asked to solve this problem. 

The platelets have two different types of containers. In the first type, each container can hold only one kind of coagulation factor. In the second type, in each container, each kind of coagulation factor can appear at most once. For convenience, the platelets want to use **only one** type of container to hold all coagulation factors. In other words, partition $n$ positive integers $a_1$ ~ $a_n$ into some disjoint sets $S_1$ ~ $S_m$, satisfying **one** of the following two conditions: 1. $\forall a_i,\ a_j\in S_k,\ k\in [1,\ m]$, we have $a_i=a_j$. 2. $\forall a_i,\ a_j\in S_k,\ k\in [1,\ m],\ i\neq j$, we have $a_i\neq a_j$. Since there are not many platelets, you need to put all coagulation factors into as few containers as possible. They want to know how to partition them so that the total number of containers is minimized.

The first line contains a positive integer $n$, the number of coagulation factors. The second line contains $n$ positive integers $a_i$, each representing the type of a coagulation factor.

The first line contains two positive integers. The first is the minimum number of containers $m$, and the second is the type of container used ($1$ or $2$). In the next $m$ lines, in each line, the first positive integer $c_i$ represents the number of coagulation factors in this container, followed by $c_i$ integers representing the type of each coagulation factor in this container. Output any valid optimal solution. The output order does not matter.

Constraints: $1\le n\le 1000,\ \ 1\le a_i\le 10^9$。 # Input Format # Output Format # Hint Translated by ChatGPT 5