#P1810. 集合分组【征集 spj】

集合分组【征集 spj】

题目描述

现有 kk 个整数集合,第 ii 个集合有 sis_i 个元素。

集合中的数都为正数,且不大于 nn。现定义集合 AA 与集合 BB 相似,当且仅当满足如下条件之一:

  1. BBAA 相似;
  2. AA 集合删去一个元素,或更改一个元素的值之后 AA 集合与 BB 集合相等。

现要将 KK 个集合分成至多 MM 组(M>NM>N),使得每一组内的集合互不相似。要求你给出一种合法的方案。如果无解请输出 impossible

输入格式

输入文件第一行有三个数 n,k,mn, k, m,意义如题目所述。

接下来有 kk 行,每行第一数 sis_i 表示序列长度。之后 sis_i 个数为些集合的元素。

输出格式

如果存在合法方案,输出 kk 个数,表示每个集合(按输入顺序)被分到的组的编号(1m1\sim m)。否则,若不存在合法方案则输出 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

提示

数据范围及约定

  • 对于 30%30\% 的数据满足 n10n \le 10m2m \le 2k10k \le 10
  • 对于 100%100\% 的数据满足 1n1001\le n \le 1001m1001\le m \le 1001k500001\le k \le 500001si1001\le s_i \le 100