题目空降

Description

有n个字符串，给这些字符串分组，使得每个字符串属于且仅属于一个组。
对于一个合法的分组，至少满足以下两个条件种的一个：
1. 所有字符串的k前缀相同(即前k个字母相同)
2. 所有字符串的k后缀相同(即后k个字母相同)
你需要给这些字符串分组，使得所分的组数最少。

Input

第一行两个整数n,k(1≤n≤5000,1≤k≤550)，分别表示字符串的数量以及题述中的参数k。
接下来有n行，每行一个字符串，字符串的长度至少为k，且不会超过550。

Output

第一行一个整数m，表示最少的分组数目。
接下来m行，每行的第一个整数ti表示第i个分组的字符串数量，接下来有ti个整数，表示第i个分组中的字符串编号，编号对应字符串的输入顺序。数字之间用一个空格隔开。
如果分组方案不唯一，输出任意一种即可。

Analysis

比赛时丝毫没有头绪。
只知道要构二分图，最大流，但答案是什么？？？（手动黑人问号）
嗯这个图是这样的。

有人可能问，这神马意思。
其实是这样的。
我们将前缀相同的集合看做左集中的点，后缀相同的集合看做右集中的点，每个字符串看做左右集间的边。
∵所有字符串在且只在一个集合中
∴所以这就转换为一个

最小边覆盖问题。

新建超级源、超级汇。
超级源连向左集，右集连向超级汇，流量为1。
字符串化作的边流量为+∞
跑一遍流，即为最少的集合数。
∵所有边在且只在一个集合中
∴$在残余网络中，从源点遍历，左集没有被遍历与右集被遍历的点则必须被选。
至此，问题得解。