Laffey 最近学习了有机化学。他感到烷烃是个很好玩的东西,于是自己画出了一堆烷烃开始试着找出最长链来给它们系统命名。但是玩了一会之后他感到这太简单了,于是打算找出氢原子数最多的一条碳链。这可难住了他,现在他向你请求帮助。
给定一个有 N 个碳原子的烷烃,请你找出其中直接连接氢原子最多的一条碳链,并输出这条碳链所直接连接的氢原子总数。为了方便起见,输入时仅输入碳原子之间的相连关系。
看不懂题意吗?嘛,大慈大悲的我可以给你几个数据自己推。比如对于异丁烷,你给出的答案应是 7 ;对于新戊烷,你给出的答案应是 6 ;以此类推(逃
第一行有两个整数 N, M ,表示输入的烷烃中的碳原子数和碳碳单键数目。
接下来 M 行每行有两个整数 X, Y ,表示这两个碳原子间有单键相连。
仅一个整数,表示这个烷烃中直接连接氢原子最多的碳链所直接连接的氢原子总数。
异戊烷(不是
5 4 4 5 1 5 2 1 1 3
9
在 \texttt{subtask #1} 中:
对于 20\% 的数据,有 0 \leq N \leq 100 ;
对于 40\% 的数据,有 0 \leq N \leq 1000 ;
对于 100\% 的数据,有 0 \leq N \leq 5000 ,并保证给出的图符合烷烃的结构特征。
在 \texttt{subtask #2} 中:
对于 100\% 的数据,有 0 \leq N \leq 10^5 ,并保证给出的图符合烷烃的结构特征。
说明:
\texttt{subtask #2} 的数据更新于 2022.5.5。
2022.5.5
单个子任务的数据由其中所有测试点的分数相乘得出。即只有所有测试点都得分时,该子任务才会得分;如果有任一测试点不得分,则该子任务也不得分。
\texttt{subtask #2} 数据 By @Star