问题 24405. -- chemistryw

24405: chemistryw

时间限制: 1 Sec  内存限制: 128 MB
献花: 52  解决: 12
[献花][花圈]

题目描述

 去年的今天,leve同学舍弃了English出了一道mathagain。今日,在Viaky的一再要求下,终于舍弃了math又出了一道chemistry……

众所舟舟知,ldw当了Viaky两年的头儿,在此期间,他用尽各种方法折磨Viaky,每天上课前5分钟都要Viaky拿作业发作业打开电脑打开投影维持纪律打开幻灯片……现在,他连作业都懒得判了……全部交由Viaky处理。

 

这几天,dw在讲烷烃的命名,Viaky盯着卷子上的烷烃结构式看,竟也真看出了点名堂。她发现,每一个结构式都是一个无环连通图,含有CH两种结点,每个C的度数均为4,每个H的度数均为1。比如下面几个:

                          H

                |

  H H       H H-C-H H H

  | |       |   |   | |

H-C-C-H   H-C---C---C-C-H

  | |       |   |   | |

  H H       H   H   H H

  乙烷       2-甲基丁烷

给烷烃命名的步骤是,首先选取最长的一条碳链(就是只由C构成的最长路径),然后……然后的事与本题无关,我就不说了。 140份的作业全都交由Viaky处理,作为OIer的她想写个程序来解决这些问题。你只要帮她找出最长的碳链就可以了。

问题又来了,需要命名的烷烃中含有上百个原子,如果真的把结构式都写给你看,就太麻烦了。于是,她发明了一种新的表示烷烃结构的方法,随便选一个C原子把它拉起来,于是结构式就变成了……对,一棵树!然后,他把这棵树深度优先遍历一遍,把得到的CH序列交给了你。比如乙烷结构式的CH序列可以是下面几种:CCHHHHHH,CHCHHHHH,CHHCHHHH,CHHHCHHH

输入

 有多组数据,每组一行,为一个CH序列,长度不超过255。输入保证合法。

每个测试点,测试数据组数不超过30.

输出

每行一个整数,为输入中对应行所表示的分子中最长碳链的长度(即路径上C原子的个数)

样例输入

CHHHH
CHCHHHHH
CHHCHHHCHCHHHCHHH

样例输出

1
2
4

提示

 三个CH序列分别表示甲烷、乙烷和2-甲基丁烷,其中最后一组是图中第二个结构式以右数第二个C原子为根的一种深度优先遍历序列。

来源

[献花][花圈]