#P1903. Jurassic Remains
Jurassic Remains
西伯利亚的古生物学家最近发现了一批侏罗纪时期的恐龙骨架碎片。他们决定将这些碎片运往古生物博物馆。不幸的是,这只恐龙体型极为庞大,没有任何箱子能装下所有碎片,因此他们决定把骨架碎片拆分成独立的骨头,分别运到博物馆后再进行重组。为了方便重组,骨头之间分离的关节处都用特殊标签做了标记。与此同时,在打包好碎片后,他们又发现了一些新的骨头,于是决定将这些新骨头与主要碎片一起运送,因此这些新骨头也被放入包裹并寄往了博物馆。
然而,当包裹到达博物馆时,出现了一些问题。首先,并非所有标记关节的标签都是唯一的。标签使用了从'A'到'Z'的字母,需要相互连接的两个关节会被标记上相同的字母,但可能有多对关节使用相同的字母。此外,新增的骨头也使用了相同类型的标签来标记某些关节,因此可能存在一些骨头的关节不需要与其他骨头连接的情况。不过,每块骨头上同一特定字母的标签最多只出现一次,这让问题稍微得到了缓解。
你的任务是帮助博物馆工作人员复原可能的恐龙骨架碎片。也就是说,你需要找出这样一组骨头,它们可以相互连接,并且满足以下条件:
- 如果某个关节与另一个关节相连,那么它们的标签相同。
- 对于这组骨头中的每一块,每个标记有标签的关节都必须与其他某个关节相连。
- 使用的骨头数量尽可能多。
请注意,两块骨头可能通过多个关节相连。
输入的第一行包含整数(),表示骨头的数量。接下来的行包含每块骨头的描述:每行是一个由不同大写字母组成的非空序列,表示对应骨头的关节所标记的标签。
第一行输出,即能够用来复原骨架碎片的最大骨头数量。然后在接下来的一行中按升序输出个整数,表示所使用的骨头编号。骨头的编号从1开始,按照输入的顺序排列。
输入数据
6
ABD
EG
GE
ABE
AC
BCD
输出数据
5
1 2 3 5 6