UVA1327 King's Quest
题目描述
很久很久以前,有一个国王,他有 $N$ 个儿子。在他的国度里还有 $N$ 位美丽的女孩,当然国王也知道他的每个儿子喜欢哪些女孩。他的儿子们年轻气盛头脑灵活,所以可能一个儿子会喜欢多个女孩。
于是国王就问他的魔法师,能不能找到一个方案使得每个儿子都能迎娶一位他喜欢的女孩。这个魔法师做到了——方案是合法的,即每个儿子迎娶的女孩都是他喜欢的,而且一个女孩只会嫁给一位儿子。
然而国王看了眼方案说:“我非常喜欢这个方案,但是我没有完全满意。对于我的每个儿子,我要知道他可能迎娶哪些女孩。当然,在他迎娶某位女孩后,其他儿子必须也能迎娶一位他喜欢的女孩。”
这个任务对于魔法师来说太难了,你需要帮助他解决这个问题。
输入格式
输入包含多组数据。
对于每组数据:
第一行包含一个数 $N$,表示国王儿子的数量和女孩的数量。
接下来 $N$ 行,首先是一个数 $K_i$ 表示第 $i$ 位儿子喜欢的女孩的数量,然后是 $K_i$ 个数,分别是他喜欢的女孩的编号。
最后一行是魔法师的原方案,包含 $N$ 个数,表示每位儿子将迎娶的女孩编号。保证是正确的。
输出格式
对于每组数据:
输出 $N$ 行。
第 $i$ 行先输出一个数 $L_i$,表示第 $i$ 位儿子共有几个喜欢的女孩可以娶。接下来 $L_i$ 个数是这些女孩的编号,从小到大排列。
说明/提示
$1\le N\le 2000$。
$\sum K_i\le 200000$