Problem K
Team Up
In online games, players form teams so they can cover each others’ weakness with different skills (e.g. healing, buffing, teleporting). There are $n$ types of skills in the game, labelled from $1$ to $n$. To form a team, every skill must be covered by at least one player in the team.
The skills each player has depend on the character class (e.g. warrior, thief, wizard) of the player. There are $m$ character classes in the game, and the $i$th class ($1 \leq i \leq m$) possesses skills $S_ i \subseteq \{ 1,2, \dots , n\} $. For every $i \neq j$, we have $S_ i \neq S_ j$. Moreover, for every $i \neq j$, exactly one of the following properties holds:
-
$S_ i \subset S_ j$
-
$S_ j \subset S_ i$
-
$S_ i$ and $S_ j$ are disjoint $(S_ i \cap S_ j = \emptyset )$
There are $p$ players, labelled form $1$ to $p$. Each player can belong to at most one team. Given the character class of each player, compute the maximum number of teams they can form and output the teaming.
Input
-
The first line contains three integers $n, m, p$ ($1 \leq n \leq 100\, 000$, $1 \leq m,p \leq 300\, 000$).
-
The next $m$ lines each describes the skills that each character class possesses. The $i$th line of these $m$ lines contains $|S_ i|+1$ integers separated by a space. The first integer will be $|S_ i|$ ($1 \leq |S_ i| \leq n$), and the following $|S_ i|$ integers describe the elements in $S_ i$. It is guaranteed that $|S_1| + \dots + |S_ m|$ is at most $500\, 000$.
-
The last line contains $p$ space-separated integers, each ranging from $1$ to $m$. The $i$th integer denotes the character class of the $i$-th player.
Output
-
Output an integer on the first line representing the maximum number of teams that can be formed.
-
For every team, output a line containing space-separated integers to describe the players in the team: the first integer represents the size of the team, the following integers represent the labels of the players. You can output the label in any order without duplication.
If there is more than one optimal solution, output any one of them.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 4 7 1 1 1 2 2 1 2 1 3 1 2 2 3 4 4 2 |
2 3 1 3 5 2 4 6 |
