#P9694. 要换换名字

    ID: 6320 传统题 3000ms 512MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>难度分类提高+/省选-动态规划有限候选集缩减图论二分图建模Hopcroft–Karp字符串序列自动机枚举与搜索广度优先搜索Trie排序与序列处理二分答案CF2300

要换换名字

要换换名字

题目描述

有 nn 个小朋友,他们的名字很长,所以决定换名字。每个人的新名字必须是原名字的一个非空子序列,且所有新名字必须两两不同。

请为他们选择新名字,使新名字中的最大长度尽量小。

原名字可以相同,新名字也允许与原名字相同。

输入格式

第一行一个正整数 nn。

接下来 nn 行,每行一个只含小写字母的字符串,表示对应小朋友的原名字。

输出格式

若无解,输出一行 -1。

否则第一行输出新名字长度的最小可能最大值,接下来 nn 行按输入顺序输出各人的新名字。多种最优方案可输出任意一种。

样例 1 输入

4
aw
we
shu
le

样例 1 输出

1
a
w
s
l

样例 2、3

见下发文件。附加样例中只保留了新名字长度的最大值。

数据规模和约定

全部数据满足 2≤n≤3002\le n\le300,每个原名字的长度 1≤length≤3001\le\mathrm{length}\le300。

子任务 分值 限制
1 10 n≤8n\le8,length≤8\mathrm{length}\le8
2 30 数据随机:串长在 [1,300][1,300] 中均匀随机,每个位置在小写字母中均匀随机
3 60 无特殊限制