#P1810. 集合分组【征集 spj】
集合分组【征集 spj】
题目描述
现有 个整数集合,第 个集合有 个元素。
集合中的数都为正数,且不大于 。现定义集合 与集合 相似,当且仅当满足如下条件之一:
- 与 相似;
- 将 集合删去一个元素,或更改一个元素的值之后 集合与 集合相等。
现要将 个集合分成至多 组(),使得每一组内的集合互不相似。要求你给出一种合法的方案。如果无解请输出 impossible
。
输入格式
输入文件第一行有三个数 ,意义如题目所述。
接下来有 行,每行第一数 表示序列长度。之后 个数为些集合的元素。
输出格式
如果存在合法方案,输出 个数,表示每个集合(按输入顺序)被分到的组的编号()。否则,若不存在合法方案则输出 impossible
。
8 20 12
5 1 3 5 6 4
5 1 3 5 6 3
4 5 6 3 3
4 5 6 3 4
4 4 6 5 8
4 7 7 7 7
3 7 7 7
2 2 2
3 2 2 7
3 1 2 3
3 1 2 4
10 1 2 3 4 5 6 7 8 7 6
10 8 7 6 5 4 3 2 1 2 1
20 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 3 5 7
5 4 6 4 6 4
5 6 4 6 4 6
6 6 6 6 6 6 6
3 6 6 6
1 1
1 2
2
1
9
1
6
2
4
5
3
7
8
5
4
8
7
9
1
1
2
3
提示
数据范围及约定
- 对于 的数据满足 ,,;
- 对于 的数据满足 ,,,。