[顾研NOIP]项链

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 necklaced.in 输出文件 necklaced.out
项链
necklaced
【问题描述】
Henryy岛是个度假胜地,每年吸引着数以万计的游客到来。岛上有着有多精品店,不过大多数精品店出售的是一种可以DIY的项链。这种项链是一些奇怪的海洋生物的外壳,把他们串起来好看又小巧。但是串这些外壳也是有技巧的,要做到好看又小巧真的不容易。
假设每个外壳有好几个可以用来连接其他外壳的连接点,每个连接点我们用大写英文字母A-Z表示(不会有同一种连接点多次出现在一个外壳上)。两个外壳可以连接,当且仅当他们有公共的连接点。而且每个连接点最多与另外一个连接点相连接。如果所有被串起来的外壳,没有多余的连接点(也就是说不可能再串一个外壳),这样串起来的所有外壳,我们叫做“外壳串”。而项链将由这些的“外壳串”再次串起来。项链的串法就没有这么复杂了,它直接用绳子串起来就可以拉。
现在的问题是,在众多的外壳中,应该如何选择才可以串出一个最为庞大的项链(外壳要最多)。
【输入文件】
第一行是一个整数N(0<=N<=26),表示有N个外壳。接下来有N行,每行是一个以A-Z字母组成的字串,表示一个外壳。
【输出文件】
输出最多可以由多少个外壳串出一串项链。
【样例输入】
6
ABD
AB
BA
ABE
AC
BCD
【样例输出】
5
【样例说明】
使用ABD、AB、BA、AC和BCD,其中ABD和BCD串剩A和C,分别于AB和AC连接后剩下的与BA连接即可。